main.go

package main

import (
	"fmt"
)

type doublyLinkedNode struct {
	prev, next * doublyLinkedNode
	key, val int
}

type LRUCache struct {
	len, cap int
	first, last * doublyLinkedNode
	nodes map[int] * doublyLinkedNode
}


func Constructor(capacity int) LRUCache {
	return LRUCache {
		cap: capacity,
		nodes: make(map[int] * doublyLinkedNode, capacity),
	}
}

func(c * LRUCache) Get(key int) int {
	if node, ok:= c.nodes[key];
	ok {
		c.moveToFirst(node)
		return node.val
	}
	return -1
}


func(c * LRUCache) Put(key int, value int) {
	node, ok:= c.nodes[key]
	if ok {
		node.val = value
		c.moveToFirst(node)
	} else {
		if c.len == c.cap {

			delete(c.nodes, c.last.key)
			c.removeLast()
		} else {
			c.len++
		}
		node = & doublyLinkedNode {
			key: key,
			val: value,
		}
		c.nodes[key] = node
		c.insertToFirst(node)
	}
}

func(c * LRUCache) removeLast() {
	if c.last.prev != nil {
		c.last.prev.next = nil
	} else {
		c.first = nil
	}
	c.last = c.last.prev
}

func(c * LRUCache) moveToFirst(node * doublyLinkedNode) {
	switch node {
	case c.first:
		return
	case c.last:
		c.removeLast()
	default:
		node.prev.next = node.next
		node.next.prev = node.prev
	}
	c.insertToFirst(node)
}

func(c * LRUCache) insertToFirst(node * doublyLinkedNode) {
	if c.last == nil {
		c.last = node
	} else {
		node.next = c.first
		c.first.prev = node
	}

	c.first = node
}


func(c * LRUCache) Display() {
	i:= c.first;
	for (i != nil) {
		fmt.Printf("%d\t", i.val)
		i = i.next
	}
	fmt.Printf("\n")
}

func main() {

	obj:= Constructor(5);
	// Insert 5 elements
	obj.Put(1, 1);
	obj.Put(2, 2);
	obj.Put(3, 3);
	obj.Put(4, 4);
	obj.Put(5, 5);

	obj.Display();

	// Access 3 elements
	fmt.Println(obj.Get(5));
	obj.Display();
	fmt.Println(obj.Get(4));
	obj.Display();
	fmt.Println(obj.Get(3));
	obj.Display();

	// Add 3 more elements
	obj.Put(6, 6);
	obj.Display();
	obj.Put(7, 7);
	obj.Display();
	obj.Put(8, 8);
	obj.Display();
}