乐趣区

关于go:LRU算法go版本

package LRU

type LRUCache struct {
    head *Node
    tail *Node
    Map  map[int]*Node
    cap  int
}

type Node struct {
    key   int
    value int
    next  *Node
    prev  *Node
}

func newNode(k, v int) *Node {
    return &Node{
        key:   k,
        value: v,
    }
}

func Constructor(capacity int) LRUCache {
    l := LRUCache{head: newNode(0, 0),
        tail: newNode(0, 0),
        Map:  make(map[int]*Node),
        cap:  capacity,
    }
    l.head.next = l.tail
    l.tail.prev = l.head

    return l
}

func (this *LRUCache) Get(key int) int {v, ok := this.Map[key]
    if !ok {return -1}
    this.moveToTail(v, v.value)
    return v.value
}

func (this *LRUCache) Put(key int, value int) {_, ok := this.Map[key]
    if ok {this.moveToTail(this.Map[key], value)
    } else {if len(this.Map) == this.cap {
            toBeDelete := this.head.next
            this.deleteNode(toBeDelete)

            delete(this.Map, toBeDelete.key)
        }
        node := newNode(key, value)
        this.Map[key] = node
        this.insertToTail(node)
    }
}

func (this *LRUCache) moveToTail(node *Node, newValue int) {this.deleteNode(node)
    node.value = newValue
    this.insertToTail(node)
}

func (this *LRUCache) deleteNode(node *Node) {
    node.prev.next = node.next
    node.next.prev = node.prev
}

func (this *LRUCache) insertToTail(node *Node) {
    this.tail.prev.next = node
    node.prev = this.tail.prev
    node.next = this.tail
    this.tail.prev = node
}
退出移动版