goを使ってLRUを実現します

1599 ワード

データ構造を練習するいい問題です.Go文法を練習するために、30分以上繰り返しました.いくつかのピットを踏みました.elseは単独で一行に置くことができません.mapは初期化してから使えます.下記のように実現します. 
双方向チェーンテーブルを構築し、ヘッドノードheadとエンドノードtailを確立しました.
eraseインターフェースとプッシュを実現しました.frontインターフェース
type ListNode struct{
    key int
    val int
    pre*ListNode
    next*ListNode
}
type LRUCache struct {
    vol int
    ma map[int]*ListNode
    head*ListNode//   ,  
    tail*ListNode//   ,  
}
func Constructor(capacity int) LRUCache {
    h:= ListNode{-1,0,nil,nil}
    t:= ListNode{-1,0,nil,nil}
    h.next = &t
    t.pre = &h
    lru:= LRUCache{capacity,make(map[int]*ListNode,capacity),&h,&t}
    return lru
}
func (this*LRUCache) erase(cur*ListNode){
    pre,next:= cur.pre,cur.next
    pre.next,next.pre = next,pre
}
func (this*LRUCache) push_front(cur*ListNode){
    prehead:= this.head.next
    cur.next = prehead
    cur.pre = this.head
    prehead.pre = cur
    this.head.next = cur
}

func (this *LRUCache) Get(key int) int {
    cur,exist:= this.ma[key]
    if(exist){
        this.erase(cur)
        this.push_front(cur)
        return cur.val
    }else{
        return -1
    }
}
func (this *LRUCache) Put(key int, value int)  {
    cur,exist:= this.ma[key]
    if(exist){
        cur.val = value
        this.erase(cur)
        this.push_front(cur)
    }else{
        if(len(this.ma) == this.vol){
            tail:= this.tail.pre
            this.erase(tail)   
            delete(this.ma,tail.key)
        }
        newNode :=ListNode{key,value,nil,nil}
        this.ma[key] = &newNode
        this.push_front(&newNode)
    }
}