您的位置 首页 golang

如何优雅的操作链表


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);       // 返回  1cache.put(3, 3);    // 该操作会使得密钥 2 作废cache.get(2);       // 返回 -1 (未找到)cache.put(4, 4);    // 该操作会使得密钥 1 作废cache.get(1);       // 返回 -1 (未找到)cache.get(3);       // 返回  3cache.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 1Set 2Get 1 return 1Set 3Get 2 return -1Set 4Get 1 return -1Get 3 return 3Get 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


文章来源:智云一二三科技

文章标题:如何优雅的操作链表

文章地址:https://www.zhihuclub.com/7216.shtml

关于作者: 智云科技

热门文章

网站地图