container/list 包基本用法

package main

import (
	"container/list"
	"fmt"
)

func main() {
	// 创建新链表
	l := list.New()

	// 在链表尾部添加元素
	l.PushBack("a")
	l.PushBack("b")
	l.PushBack("c")

	// 在链表头部添加元素
	l.PushFront("first")

	// 遍历链表
	for e := l.Front(); e != nil; e = e.Next() {
		fmt.Printf("%v ", e.Value)
	}
	fmt.Println()
}

package main

import (
	"container/list"
	"fmt"
)

func main() {
	l := list.New()
	l.PushBack("a")
	l.PushBack("c")

	// 在 b 之后插入
	b := l.PushBack("b")
	l.InsertAfter("b+", b)

	// 在 b 之前插入
	l.InsertBefore("b-", b)

	// 移动到队首
	l.MoveToFront(b)

	// 移动到队尾
	l.MoveToBack(l.Front())

	// 打印链表
	for e := l.Front(); e != nil; e = e.Next() {
		fmt.Printf("%v -> ", e.Value)
	}
	fmt.Println("nil")
}

package main

import (
	"container/list"
	"fmt"
)

func main() {
	l := list.New()
	elem := l.PushBack("to be deleted")
	l.PushBack("remain")

	fmt.Printf("删除前长度: %d\n", l.Len())

	// 删除元素
	l.Remove(elem)

	fmt.Printf("删除后长度: %d\n", l.Len())

	// 打印剩余元素
	for e := l.Front(); e != nil; e = e.Next() {
		fmt.Printf("%v\n", e.Value)
	}
}

package main

import (
	"container/list"
	"fmt"
)

func main() {
	l := list.New()
	a := l.PushBack("a")
	b := l.PushBack("b")
	c := l.PushBack("c")
	d := l.PushBack("d")

	// 移动 c 到 b 之前
	l.MoveBefore(c, b)

	// 移动 a 到 d 之后
	l.MoveAfter(a, d)

	// 打印结果
	fmt.Print("链表: ")
	for e := l.Front(); e != nil; e = e.Next() {
		fmt.Printf("%v ", e.Value)
	}
	fmt.Println()
}

package main

import (
	"container/list"
	"fmt"
)

// LRUCache 使用 list 实现 LRU 缓存
type LRUCache struct {
	capacity int
	cache    map[string]*list.Element
	order    *list.List
}

type entry struct {
	key   string
	value string
}

func NewLRUCache(capacity int) *LRUCache {
	return &LRUCache{
		capacity: capacity,
		cache:    make(map[string]*list.Element),
		order:    list.New(),
	}
}

func (c *LRUCache) Get(key string) (string, bool) {
	if elem, ok := c.cache[key]; ok {
		// 移动到队首（最近使用）
		c.order.MoveToFront(elem)
		return elem.Value.(*entry).value, true
	}
	return "", false
}

func (c *LRUCache) Put(key, value string) {
	if elem, ok := c.cache[key]; ok {
		// 更新值并移动到队首
		c.order.MoveToFront(elem)
		elem.Value.(*entry).value = value
		return
	}

	// 添加新元素
	elem := c.order.PushFront(&entry{key, value})
	c.cache[key] = elem

	// 如果超出容量，淘汰最久未使用的
	if c.order.Len() > c.capacity {
		oldest := c.order.Back()
		if oldest != nil {
			delete(c.cache, oldest.Value.(*entry).key)
			c.order.Remove(oldest)
		}
	}
}

func main() {
	cache := NewLRUCache(3)

	cache.Put("a", "1")
	cache.Put("b", "2")
	cache.Put("c", "3")
	fmt.Println("添加 a, b, c 后:")
	printCache(cache)

	// 访问 a，使其成为最近使用
	cache.Get("a")

	// 添加 d，应该淘汰 b
	cache.Put("d", "4")
	fmt.Println("访问 a，添加 d 后:")
	printCache(cache)
}

func printCache(c *LRUCache) {
	for e := c.order.Back(); e != nil; e = e.Prev() {
		en := e.Value.(*entry)
		fmt.Printf("%s=%s ", en.key, en.value)
	}
	fmt.Println()
}