package main

import (
    "fmt"
)

// 定義節(jié)點(diǎn)結(jié)構(gòu)體
type node struct {
    key   string
    value string
    next  *node
    prev  *node
}

// 定義lru結(jié)構(gòu)體
type lru struct {
    //緩存最大數(shù)量
    k int
    // 存放節(jié)點(diǎn)數(shù)據(jù)
    cache map[string]*node
    //頭節(jié)點(diǎn)
    head *node
    // 尾節(jié)點(diǎn)
    tail *node
}

// 工廠方法，構(gòu)造一個LRU緩存對象
func NewLRUCache(k int) *lru {
    return &lru{k: k}
}

// 對外開放的Get方法
func (lru *lru) Get(key string) string {
    if lru.cache == nil {
        return ""
    }
    n, ok := lru.cache[key]
    if ok {
        value := n.value
        //更新到頭節(jié)點(diǎn)
        lru.moveNodeToHead(n)
        return value
    } else {
        return ""
    }
}

// 對外開放的Set方法
func (lru *lru) Set(key string, value string) {
    //初始化map
    if lru.cache == nil {
        lru.cache = make(map[string]*node)
    }
    n, ok := lru.cache[key]
    if ok {
        //更新緩存
        n.value = value
    } else {
        //創(chuàng)建新節(jié)點(diǎn)
        n = &node{key: key, value: value}
        // 添加到map中
        lru.cache[key] = n
        //如果超過緩存大小，移除最后一個節(jié)點(diǎn)
        if len(lru.cache) > lru.k {
            lru.removeTail()
        }
    }
    // 更新節(jié)點(diǎn)為頭節(jié)點(diǎn)
    lru.moveNodeToHead(n)
}

//將指定節(jié)點(diǎn)移到頭節(jié)點(diǎn)
func (lru *lru) moveNodeToHead(n *node) {
    //如果頭節(jié)點(diǎn)和尾節(jié)點(diǎn)都是空，說明是第一次添加數(shù)據(jù)
    if lru.head == nil && lru.tail == nil {
        lru.head = n
        lru.tail = n
        return
    }
    // 如果是頭節(jié)點(diǎn)，那么不動
    if lru.head == n {
        return
    }
    nextNode := n.next
    prevNode := n.prev
    // 如果是尾節(jié)點(diǎn)，那么要先與上一個節(jié)點(diǎn)斷開
    if n == lru.tail {
        prevNode.next = nil
        n.prev = nil
    } else if prevNode != nil && nextNode != nil {
        //如果是中間節(jié)點(diǎn)，要與前后節(jié)點(diǎn)都斷開
        nextNode.prev = prevNode
        prevNode.next = nextNode
        n.prev = nil
    }
    //把節(jié)點(diǎn)移到到頭節(jié)點(diǎn)
    n.next = lru.head
    lru.head.prev = n
    lru.head = n
}

//移除最后一個節(jié)點(diǎn)
func (lru *lru) removeTail() {
    // 如果尾節(jié)點(diǎn)wei空，那么清空數(shù)據(jù)直接返回
    if lru.tail == nil {
        lru.cache = nil
        return
    }
    tailPrev := lru.tail.prev
    // 尾節(jié)點(diǎn)與上一個節(jié)點(diǎn)斷開
    lru.tail.prev = nil
    if tailPrev != nil {
        tailPrev.next = nil
    }
    // 把上一個節(jié)點(diǎn)置為尾節(jié)點(diǎn)
    lru.tail = tailPrev
    // 從map中刪除尾節(jié)點(diǎn)數(shù)據(jù)
    delete(lru.cache, lru.tail.key)
}

// 重寫String方法，自定義打印結(jié)果
func (lru *lru) String() string {
    point := lru.head
    result := ""
    flag := "\t"
    for point != nil {
        if len(result) > 0 {
            result = fmt.Sprintf("%v%v[%v:%v]", result, flag, point.key, point.value)
        } else {
            result = fmt.Sprintf("[%v:%v]", point.key, point.value)
        }
        point = point.next
    }
    return result
}

func main() {
    LRUCache := NewLRUCache(5)
    LRUCache.Set("1", "1")
    LRUCache.Set("2", "2")
    LRUCache.Set("3", "3")
    LRUCache.Set("4", "4")
    LRUCache.Set("5", "5")
    //打印緩存數(shù)據(jù)，驗證容量是否起作用
    fmt.Println(LRUCache)
    //設(shè)置超過最大容量的數(shù)據(jù)
    LRUCache.Set("6", "6")
    //打印緩存數(shù)據(jù)，驗證超過容量是否起作用
    fmt.Println(LRUCache)
    //查詢頭節(jié)點(diǎn)數(shù)據(jù)
    fmt.Println(LRUCache.Get("6"))
    //打印緩存數(shù)據(jù)
    fmt.Println(LRUCache)
    //查詢非頭節(jié)點(diǎn)數(shù)據(jù)
    fmt.Println(LRUCache.Get("4"))
    //打印緩存數(shù)據(jù)
    fmt.Println(LRUCache)
    //查詢尾節(jié)點(diǎn)數(shù)據(jù)
    fmt.Println(LRUCache.Get("2"))
    //打印緩存數(shù)據(jù)
    fmt.Println(LRUCache)
}

image.png