LRU cache using Go

lru_cache.go

package main

import (
	"fmt"
)

// Node is the basic structure to store the key and value. Also store the prev and next node.
type Node struct {
	key      string
	value    string
	previous *Node
	next     *Node
}

// List is the head for the double linked list.
type List struct {
	size int
	head *Node
	tail *Node
}

// NewList return a new double linked list.
func NewList() List {
	return List{}
}

// insert add a new node at the beginning of the list.
func (l *List) insert(node *Node) {
	// If the list is empty, we add the first node
	if l.size == 0 {
		l.head = node
		l.tail = node
		l.size = 1
		return
	}

	// Else we add the new node to the head of the list
	node.next = l.head
	l.head.previous = node
	l.head = node
	l.size++
}

// remove the element from the list
func (l *List) remove(node *Node) {
	if l.size == 1 {
		l.head, l.tail = nil, nil
		l.size = 0
		
		return
	}
	
	prev, next := node.previous, node.next
	node.previous, node.next = nil, nil
	
	if prev != nil {
		prev.next = next
		if next == nil {
			l.tail = prev
		}
	}

	if next != nil {
		next.previous = prev
	}

	l.size--
}

// removeLast removes the last element from the list and return the key.
func (l *List) removeLast() string {
	if l.size == 1 {
		resp := l.head.key
		l.head, l.tail = nil, nil
		l.size = 0

		return resp
	}

	resp := l.tail.key
	l.tail = l.tail.previous
	l.tail.next = nil
	l.size--

	return resp
}

func (l *List) print() {
	current := l.head
	for current != nil {
		fmt.Print(current.value, " ")
		current = current.next
	}
	fmt.Println()
}

type LRU struct {
	mapCache map[string]*Node
	list     *List
	maxSize  int
}

func New(size int) *LRU {
	newList := NewList()
	return &LRU{
		mapCache: make(map[string]*Node),
		list:     &newList,
		maxSize:  size,
	}
}

func (l *LRU) Get(key string) string {
	node, exists := l.mapCache[key]
	if !exists {
		return ""
	}

	if node != l.list.head {
		l.list.remove(node)
		l.list.insert(node)
	}

	return node.value
}

func (l *LRU) Put(key, value string) {
	node, exists := l.mapCache[key]
	if exists {
		node.value = value
		l.list.remove(node)
		l.list.insert(node)
		return
	}

	if l.list.size == l.maxSize {
		keyRemove := l.list.removeLast()
		delete(l.mapCache, keyRemove)
	}

	newNode := &Node{key: key, value: value}
	l.mapCache[key] = newNode
	l.list.insert(newNode)
}

func main() {
	l := New(4)

	l.Put("a", "A") // a
	l.list.print()
	l.Put("b", "B") // b, a
	l.list.print()
	l.Put("c", "C") // c, b, a
	l.list.print()
	l.Put("d", "D") // d, c, b, a
	l.list.print()
	l.Put("e", "E") // e, d, c, b
	l.list.print()
	l.Put("f", "F") // f, e, d, c
	l.list.print()
	l.Put("c", "C2") // c2, f, e, d
	l.list.print()
	l.Get("d") // d, c2, f, e
	l.list.print()
}