Documentation ¶
Index ¶
Constants ¶
This section is empty.
Variables ¶
This section is empty.
Functions ¶
This section is empty.
Types ¶
type LRUCache ¶
type LRUCache struct {
// contains filtered or unexported fields
}
LRUCache contains a hash map and a doubly linked list
func (*LRUCache) Get ¶
Get a list node from the hash map.
func (c *LRUCache) Get(key int) int { // check if list node exists if node, ok := c.m[key]; ok { val := node.Value.(*list.Element).Value.(Pair).value // move node to front c.l.MoveToFront(node) return val } return -1 }
// Put key and value in the LRUCache
func (c *LRUCache) Put(key int, value int) { // check if list node exists if node, ok := c.m[key]; ok { // move the node to front c.l.MoveToFront(node) // update the value of a list node node.Value.(*list.Element).Value = Pair{key: key, value: value} } else { // delete the last list node if the list is full if c.l.Len() == c.cap { // get the key that we want to delete idx := c.l.Back().Value.(*list.Element).Value.(Pair).key // delete the node pointer in the hash map by key delete(c.m, idx) // remove the last list node c.l.Remove(c.l.Back()) } // initialize a list node node := &list.Element{ Value: Pair{ key: key, value: value, }, } // push the new list node into the list ptr := c.l.PushFront(node) // save the node pointer in the hash map c.m[key] = ptr } }
Click to show internal directories.
Click to hide internal directories.