package main import( "fmt" ) type Node struct { Key string Val string Pre *Node Next *Node } type DLinkedList struct { Head *Node Tail *Node } func (self *DLinkedList) IsEmpty() bool { if self.Head == nil && self.Tail == nil { return true } else { return false } } func (self *DLinkedList) RemoveLast() { if self.Tail != nil { self.Remove(self.Tail) } } func (self *DLinkedList) Remove(n *Node){ if self.Tail == self.Head { self.Head = nil self.Tail = nil return } if n == self.Head { n.Next.Pre = nil self.Head = n.Next return } if n == self.Tail { n.Pre.Next = nil self.Tail = n.Pre return } n.Pre.Next = n.Next n.Next.Pre = n.Pre } func (self *DLinkedList) AddFirst(n *Node) { if self.Head == nil { self.Head = n self.Tail = n n.Pre = nil n.Next = nil return } n.Next = self.Head self.Head.Pre = n self.Head = n n.Pre = nil } type LRUCache struct { Cap int Size int HashMap map[string]*Node Cache *DLinkedList } func (self *LRUCache) Get(k string) string { if node,ok := self.HashMap[k]; ok { self.Cache.Remove(node) self.Cache.AddFirst(node) return node.Val } else { return "" } } func (self *LRUCache) Set(k,val string ) { if node,ok := self.HashMap[k];ok { self.Cache.Remove(node) node.Val = val self.Cache.AddFirst(node) } else { n := &Node{Key:k,Val:val} self.HashMap[k] = n self.Cache.AddFirst(n) self.Size = self.Size + 1 if self.Size > self.Cap { self.Size = self.Size - 1 delete(self.HashMap,self.Cache.Tail.Key) self.Cache.RemoveLast() } } } func main() { cache := new(LRUCache) cache.Cap = 3 cache.HashMap = make(map[string]*Node,0) cache.Cache = new(DLinkedList) cache.Set("allen","value") cache.Set("a","value") cache.Set("b","value") cache.Set("c","value") test := cache.Get("allen") fmt.Println(test) fmt.Println(cache.HashMap) fmt.Println(cache.Cache) fmt.Println(cache.Size) }
有疑问加站长微信联系(非本文作者)