[数据结构与算法]LRU go实现

思路

1. 用列表实现，有head和tail
   • 为什么需要tail？
   • 为什么node节点需要key？
2. 当get值的时候，用map查找
   • 找不到返回-1
   • 能找到将node调整到表头
3. 当put值的时候
   • 如果key已经存在则需要更新val，同时将node调整到表头
   • 如果key不存在则新建node，将其调整到表头

代码

package main

import "fmt"

type LRUCache struct {
    cap int
    num int
    head *LRUMem
    tail *LRUMem
    values map[int]*LRUMem

}

type LRUMem struct {
    pre *LRUMem
    next *LRUMem
    val int
    key int
}

func Constructor(capacity int) LRUCache {
    return LRUCache {
        cap: capacity,
        num: 0,
        head: nil,
        tail: nil,
        values: make(map[int]*LRUMem, capacity),
    }
}


func (this *LRUCache) Get(key int) int {
	v, ok := this.values[key]
	if !ok {
		return -1
	}
 
    if v == this.head {
        //this.Print();
		return v.val
	}

    //make v neighbors ready
    if v.pre != nil {
    	v.pre.next = v.next
    	if v.next == nil {
    		this.tail = v.pre
    	}
    	
    }
    
    if v.next != nil {
    	v.next.pre = v.pre
    }
    

    v.pre = nil
    v.next = this.head

    // make old head ready
    this.head.pre = v
    

    // make head ready
    this.head = v
  
    //this.Print();
	return v.val
}


func (this *LRUCache) Put(key int, value int)  {
	if this.cap == 0 {
		return 
	}

    _, ok := this.values[key]
	if ok {
		this.values[key].val = value
        this.Get(key)
        //this.Print();
		return 
	}
    
    this.num = this.num+1

	newMem := &LRUMem {
		pre: nil,
		next: nil,
		val: value,
		key: key,
	}

	newMem.next = this.head
    if this.head != nil {
        this.head.pre = newMem
    }
	
    // init tail
	if this.num == 1 {
		this.tail = newMem
	}
	if this.num == 2 {
		this.tail = this.head
	}

	this.head = newMem

	if this.num == this.cap+1 {
		// delete old tail
		if this.tail != nil {
			needDel := this.tail
			//fmt.Println("need delete ", this.values[needDel.key].val)
			if needDel.pre != nil {
				needDel.pre.next = nil
				this.tail = needDel.pre
				this.tail.next = nil
			}
			delete(this.values, needDel.key)
			this.num = this.num-1
			//fmt.Println("finish delete ", this.values[needDel.key])
		}
	}

	this.values[key] = newMem
    //this.Print();
}

func (this *LRUCache) Print() {
	if this.head != nil {
		fmt.Println("head:", this.head.key)
	}

	if this.tail != nil {
		fmt.Println("tail:", this.tail.key)
	}
	for node:= this.head; node!= nil ;node= node.next {
		fmt.Println(node.key, node.val)
	}
	fmt.Println("********************")
}

func main() {
	lRUCache := Constructor(3);

	lRUCache.Put(1, 1); 
    lRUCache.Put(2, 2);
	lRUCache.Put(3, 3); 
	lRUCache.Put(4, 4); 

	lRUCache.Get(4);    
	lRUCache.Get(3);   
	lRUCache.Put(5, 5); 
}

创作打卡挑战赛

赢取流量/现金/CSDN周边激励大奖