如何优雅的操作链表

设计和实现一个 LRU (最近最少使用) 缓存机制。它应该支持以下操作：获取数据 get 和写入数据 put。

获取数据 get(key) – 如果密钥 (key) 存在于缓存中，则获取密钥的值（总是正数），否则返回 -1。

写入数据 put(key, value) – 如果密钥不存在，则写入其数据值。当缓存容量达到上限时，它应该在写入新数据之前删除最近最少使用的数据值，从而为新的数据值留出空间。

进阶:
你是否可以在 O(1) 时间复杂度内完成这两种操作？

示例:

LRUCache cache = new LRUCache(2 /* 缓存容量 */);

cache.put(1, 1);
cache.put(2, 2);
cache.get(1);       // 返回  1
cache.put(3, 3);    // 该操作会使得密钥 2 作废
cache.get(2);       // 返回 -1 (未找到)
cache.put(4, 4);    // 该操作会使得密钥 1 作废
cache.get(1);       // 返回 -1 (未找到)
cache.get(3);       // 返回  3
cache.get(4);       // 返回  4

解题思路不多说了，主要是 hash 加双向链表，具体详见如下代码：

type node struct {
    key   int
    value uint
    pre   *node
    next  *node
}

type LRUcache struct {
    cap    int
    m      map[int]*node
    header *node
    rear   *node
}

func NewLRUcache(len int) *LRUcache {
    if len <= 0 {return nil}

    m := make(map[int]*node, len)

    return &LRUcache{cap: len, m: m}
}

func (c *LRUcache) Get(key int) int {if v, ok := c.m[key]; ok {
        //delete this node
        if v.pre != nil {
            v.pre.next = v.next
            if v.next != nil {v.next.pre = v.pre} else {
                // set new rear
                c.rear = v.pre
            }

            //move to head
            v.next = c.header
            v.pre = nil
            c.header.pre = v
            c.header = v
        }
        //else do nothing
        return int(v.value)
    }

    return -1
}

func (c *LRUcache) Put(key int, value uint) {
    // modify
    if v, ok := c.m[key]; ok {
        //delete this node
        if v.pre != nil {
            v.pre.next = v.next
            if v.next != nil {v.next.pre = v.pre} else {
                // set new rear
                c.rear = v.pre
            }

            //move to head
            v.next = c.header
            v.pre = nil
            c.header.pre = v
            c.header = v
        }
        //else do nothing
        v.value = value
    }

    // check capacity before adding
    if len(c.m) >= c.cap {
        // remove the last
        if c.rear != nil {
            // header == rear while c.rear.pre == nil
            if c.rear.pre != nil {
                c.rear.pre.next = nil
                delete(c.m, c.rear.key)
                c.rear = c.rear.pre
            } else {
                c.rear = nil
                c.header = nil
            }
        }
    }

    // add
    if c.header == nil {c.header = &node{key: key, value: value}
        c.rear = c.header
        c.m[key] = c.header
    } else {newnode := &node{key: key, value: value}
        newnode.next = c.header
        c.header.pre = newnode
        c.header = newnode
        c.m[key] = newnode
    }

    return
}

调试代码：

func main() {obj := NewLRUcache(2)
    if obj == nil {return}

    fmt.Println("Set 1")
    obj.Put(1, 1)

    fmt.Println("Set 2")
    obj.Put(2, 2)

    fmt.Println("Get 1 return", obj.Get(1))

    fmt.Println("Set 3")
    obj.Put(3, 3)

    fmt.Println("Get 2 return", obj.Get(2))

    fmt.Println("Set 4")
    obj.Put(4, 4)

    fmt.Println("Get 1 return", obj.Get(1))
    fmt.Println("Get 3 return", obj.Get(3))
    fmt.Println("Get 4 return", obj.Get(4))
}

输出：

Set 1
Set 2
Get 1 return 1
Set 3
Get 2 return -1
Set 4
Get 1 return -1
Get 3 return 3
Get 4 return 4

编码很容易，调试的时候倒是遇到了几个小问题，各种指针指来指去，很容易出错，还到处判断头指针是否是空，尾指针是否为空等等。。。
想起之前看过 Linux 大神 Linus Torvalds 的代码的品味问题，提到如何优雅的写链表，故重新优化如下：

直接上代码：


type node struct {
    key   int
    value uint
    pre   *node
    next  *node
}

type LRUcache struct {
    cap    int
    m      map[int]*node
    header *node
    rear   *node
}

func NewLRUcache(len int) *LRUcache {
    if len <= 0 {return nil}

    m := make(map[int]*node, len)
    head := &node{}
    tail := &node{}
    head.next = tail
    tail.pre = head

    return &LRUcache{cap: len, m: m, header:head, rear:tail}
}

func (c *LRUcache) Get(key int) int {if v, ok := c.m[key]; ok {
        //remove
        v.pre.next = v.next
        v.next.pre = v.pre

        //add to head
        v.pre = c.header
        v.next = c.header.next
        c.header.next.pre = v
        c.header.next = v

        return int(v.value)
    }

    return -1
}

func (c *LRUcache) Put(key int, value uint) {
    // modify
    if v, ok := c.m[key]; ok {
        //remove
        v.pre.next = v.next
        v.next.pre = v.pre

        //add to head
        v.pre = c.header
        v.next = c.header.next
        c.header.next.pre = v
        c.header.next = v

        v.value = value
    }

    // check capacity before adding
    if len(c.m) >= c.cap {
        // remove the last
        remove := c.rear.pre
        remove.pre.next = remove.next
        remove.next.pre = remove.pre

        //delete from hash
        delete(c.m, remove.key)
    }

    // add
    newnode := &node{key: key, value: value}
    c.header.next.pre = newnode
    newnode.next = c.header.next
    c.header.next = newnode
    newnode.pre = c.header

    c.m[key] = newnode

    return
}

再重新提取公共函数，进一步去优化：


type node struct {
    key   int
    value uint
    pre   *node
    next  *node
}

type LRUcache struct {
    cap    int
    m      map[int]*node
    header *node
    rear   *node
}

func NewLRUcache(len int) *LRUcache {
    if len <= 0 {return nil}

    m := make(map[int]*node, len)
    head := &node{}
    tail := &node{}
    head.next = tail
    tail.pre = head

    return &LRUcache{cap: len, m: m, header:head, rear:tail}
}

func (c *LRUcache) moveToHeader(v *node) {
    //remove
    v.pre.next = v.next
    v.next.pre = v.pre

    //add to head
    v.pre = c.header
    v.next = c.header.next
    c.header.next.pre = v
    c.header.next = v
}

func (c *LRUcache) Get(key int) int {if v, ok := c.m[key]; ok {c.moveToHeader(v)
        return int(v.value)
    }

    return -1
}

func (c *LRUcache) Put(key int, value uint) {
    // modify
    if v, ok := c.m[key]; ok {c.moveToHeader(v)
        v.value = value
    }

    // check capacity before adding
    if len(c.m) >= c.cap {
        // remove the last
        remove := c.rear.pre
        remove.pre.next = remove.next
        remove.next.pre = remove.pre

        //delete from hash
        delete(c.m, remove.key)
    }

    // add
    newnode := &node{key: key, value: value}
    c.header.next.pre = newnode
    newnode.next = c.header.next
    c.header.next = newnode
    newnode.pre = c.header

    c.m[key] = newnode

    return
}

大功告成！！
从代码可以看到，在操作链表的时候已经不需要判断指针是否为空了，因为利用两个空节点来存储头和尾。
即链表变化为：

如何优雅的操作链表

leetcode 中的一道题目：

实现一

实现二