如何优雅的操作链表

laughbug · · 361 次点击 · · 开始浏览    
这是一个创建于 的文章,其中的信息可能已经有所发展或是发生改变。

leetcode中的一道题目:

设计和实现一个  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
}

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

to

image.png


有疑问加站长微信联系(非本文作者)

本文来自:Segmentfault

感谢作者:laughbug

查看原文:如何优雅的操作链表

入群交流(和以上内容无关):加入Go大咖交流群,或添加微信:liuxiaoyan-s 备注:入群;或加QQ群:692541889

361 次点击  
加入收藏 微博
暂无回复
添加一条新回复 (您需要 登录 后才能回复 没有账号 ?)
  • 请尽量让自己的回复能够对别人有帮助
  • 支持 Markdown 格式, **粗体**、~~删除线~~、`单行代码`
  • 支持 @ 本站用户;支持表情(输入 : 提示),见 Emoji cheat sheet
  • 图片支持拖拽、截图粘贴等方式上传