在 Go 语言中，包提供了一个双向链表的实现。链表是一种常见的数据结构，适用于频繁插入和删除操作的场景。包中的链表是双向的，意味着每个元素都包含指向前一个和后一个元素的指针。
力扣：146. LRU 缓存
力扣算法链接：https://leetcode.cn/problems/lru-cache/?envType=study-plan-v2&envId=top-100-liked
请你设计并实现一个满足 LRU (最近最少使用) 缓存 约束的数据结构。
实现 LRUCache 类：
LRUCache(int capacity) 以 正整数 作为容量 capacity 初始化 LRU 缓存。
int get(int key) 如果关键字 key 存在于缓存中，则返回关键字的值，否则返回 -1 。
void put(int key, int value) 如果关键字 key 已经存在，则变更其数据值 value ；如果不存在，则向缓存中插入该组 key-value 。如果插入操作导致关键字数量超过 capacity ，则应该 逐出 最久未使用的关键字。
函数 get 和 put 必须以 O(1) 的平均时间复杂度运行。
输入- [“LRUCache”, “put”, “put”, “get”, “put”, “get”, “put”, “get”, “get”, “get”][[2], [1, 1], [2, 2], [1], [3, 3], [2], [4, 4], [1], [3], [4]]
- [null, null, null, 1, null, -1, null, -1, 3, 4]
- LRUCache lRUCache = new LRUCache(2);lRUCache.put(1, 1); // 缓存是 {1=1}lRUCache.put(2, 2); // 缓存是 {1=1, 2=2}lRUCache.get(1); // 返回 1lRUCache.put(3, 3); // 该操作会使得关键字 2 作废，缓存是 {1=1, 3=3}lRUCache.get(2); // 返回 -1 (未找到)lRUCache.put(4, 4); // 该操作会使得关键字 1 作废，缓存是 {4=4, 3=3}lRUCache.get(1); // 返回 -1 (未找到)lRUCache.get(3); // 返回 3lRUCache.get(4); // 返回 4
- type Node struct {
- key int
- value int
- }
- type LRUCache struct {
- capacity int
- list *list.List
- mp map[int]*list.Element // 注意1：value是list.Element
- }
- func Constructor(capacity int) LRUCache {
- return LRUCache{
- capacity: capacity,
- list: list.New(),
- mp: make(map[int]*list.Element),
- }
- }
- func (this *LRUCache) Get(key int) int {
- if v, ok := this.mp[key]; ok {
- this.list.MoveToFront(v)
- return v.Value.(*Node).value // 注意2：list.Element里面有一个Value any字段，所以需要断言
- }
- return -1
- }
- func (this *LRUCache) Put(key int, value int) {
- if v, ok := this.mp[key]; ok {
- v.Value.(*Node).value = value
- this.list.MoveToFront(v) // 注意3：需要移动，LRU
- return
- }
- node := &Node{key, value}
- a := this.list.PushFront(node)
- this.mp[key] = a // 注意4：一定把插入链表的kv，也加入到哈希表
- if this.list.Len() > this.capacity { // 注意5：判断是否越界
- tmp := this.list.Back()
- delete(this.mp, tmp.Value.(*Node).key) // 注意6：删除已经淘汰的数据的key
- this.list.Remove(tmp)
- }
- }
List: 表示一个双向链表。- type List struct {
- root Element // sentinel list element, only &root, root.prev, and root.next are used
- len int // current list length excluding (this) sentinel element
- }
- type Element struct {
- next, prev *Element
- list *List
- Value any
- }
1. 初始化链表
使用创建一个新的链表。- func main() {
- l := list.New()
- fmt.Printf("%+v\n",l)
- }
2. 插入元素
- PushBack(value interface{}) *Element: 在链表尾部插入一个元素。
- PushFront(value interface{}) *Element: 在链表头部插入一个元素。
- InsertBefore(value interface{}, mark *Element) *Element: 在指定元素前插入一个元素。
- InsertAfter(value interface{}, mark *Element) *Element: 在指定元素后插入一个元素。
- func main() {
- l := list.New()
- l.PushBack(123)
- l.PushBack("nihao")
- l.PushFront("你好")
- l.PushFront(3.1415926)
- // 遍历
- for e := l.Front(); e != nil; e = e.Next() {
- fmt.Printf("%+v\n", e)
- }
- }
3. 删除元素
Remove(e *Element) interface{}: 删除链表中的指定元素。- func main() {
- l := list.New()
- l.PushBack("nihao")
- a:=l.Remove(l.Back())
- fmt.Println(a)
- }
4. 遍历链表
- Front() *Element: 返回链表的第一个元素。
- Back() *Element: 返回链表的最后一个元素。
- Next() *Element: 返回当前元素的下一个元素。
- Prev() *Element: 返回当前元素的前一个元素。
- func main() {
- l := list.New()
- l.PushBack(1)
- l.PushBack(2)
- l.PushBack(3)
- // 从前往后遍历
- for e := l.Front(); e != nil; e = e.Next() {
- fmt.Println(e.Value)
- }
- // 从后往前遍历
- for e := l.Back(); e != nil; e = e.Prev() {
- fmt.Println(e.Value)
- }
- }
Len() int: 返回链表中元素的个数。- func main() {
- l := list.New()
- l.PushBack(1)
- l.PushBack(2)
- l.PushBack(3)
- fmt.Println(l.Len()) // 输出: 3
- }
- 频繁插入和删除: 链表在插入和删除操作上比数组更高效，尤其是在中间位置。
- 实现队列和栈: 链表可以用来实现队列（FIFO）和栈（LIFO）等数据结构。
- 动态数据存储: 当数据量不确定或需要动态调整时，链表是一个很好的选择。
注意事项
- 内存开销: 链表的每个元素都需要额外的内存来存储前后指针，因此内存开销比数组大。
- 随机访问性能差: 链表不支持随机访问，访问某个元素需要从头或尾开始遍历。
源代码阅读
- // Copyright 2009 The Go Authors. All rights reserved.// Use of this source code is governed by a BSD-style// license that can be found in the LICENSE file.// Package list implements a doubly linked list.//// To iterate over a list (where l is a *List)://// for e := l.Front(); e != nil; e = e.Next() {// // do something with e.Value// }package list// Element is an element of a linked list.type Element struct { //双链表元素中的下一个和上一个指针。 //为了简化实现，在内部实现了列表l //作为一个环，这样&l.root既是最后一个元素的下一个元素 //list元素（l.Back（））和第一个列表的前一个元素 //元素（l.Front（））。 next, prev *Element // The list to which this element belongs. list *List // The value stored with this element. Value any}// Next returns the next list element or nil.func (e *Element) Next() *Element { if p := e.next; e.list != nil && p != &e.list.root { return p } return nil}// Prev returns the previous list element or nil.func (e *Element) Prev() *Element { if p := e.prev; e.list != nil && p != &e.list.root { return p } return nil}// List represents a doubly linked list.// The zero value for List is an empty list ready to use.type List struct {
- root Element // sentinel list element, only &root, root.prev, and root.next are used
- len int // current list length excluding (this) sentinel element
- }// Init initializes or clears list l.func (l *List) Init() *List { l.root.next = &l.root l.root.prev = &l.root l.len = 0 return l}// New returns an initialized list.func New() *List { return new(List).Init() }// Len returns the number of elements of list l.// The complexity is O(1).func (l *List) Len() int { return l.len }// Front returns the first element of list l or nil if the list is empty.func (l *List) Front() *Element { if l.len == 0 { return nil } return l.root.next}// Back returns the last element of list l or nil if the list is empty.func (l *List) Back() *Element { if l.len == 0 { return nil } return l.root.prev}// lazyInit lazily initializes a zero List value.func (l *List) lazyInit() { if l.root.next == nil { l.Init() }}// insert inserts e after at, increments l.len, and returns e.func (l *List) insert(e, at *Element) *Element { e.prev = at e.next = at.next e.prev.next = e e.next.prev = e e.list = l l.len++ return e}// insertValue is a convenience wrapper for insert(&Element{Value: v}, at).func (l *List) insertValue(v any, at *Element) *Element { return l.insert(&Element{Value: v}, at)}// remove removes e from its list, decrements l.lenfunc (l *List) remove(e *Element) { e.prev.next = e.next e.next.prev = e.prev e.next = nil // avoid memory leaks e.prev = nil // avoid memory leaks e.list = nil l.len--}// move moves e to next to at.func (l *List) move(e, at *Element) { if e == at { return } e.prev.next = e.next e.next.prev = e.prev e.prev = at e.next = at.next e.prev.next = e e.next.prev = e}// Remove removes e from l if e is an element of list l.// It returns the element value e.Value.// The element must not be nil.func (l *List) Remove(e *Element) any { if e.list == l { // if e.list == l, l must have been initialized when e was inserted // in l or l == nil (e is a zero Element) and l.remove will crash l.remove(e) } return e.Value}// PushFront inserts a new element e with value v at the front of list l and returns e.func (l *List) PushFront(v any) *Element { l.lazyInit() return l.insertValue(v, &l.root)}// PushBack inserts a new element e with value v at the back of list l and returns e.func (l *List) PushBack(v any) *Element { l.lazyInit() return l.insertValue(v, l.root.prev)}// InsertBefore inserts a new element e with value v immediately before mark and returns e.// If mark is not an element of l, the list is not modified.// The mark must not be nil.func (l *List) InsertBefore(v any, mark *Element) *Element { if mark.list != l { return nil } // see comment in List.Remove about initialization of l return l.insertValue(v, mark.prev)}// InsertAfter inserts a new element e with value v immediately after mark and returns e.// If mark is not an element of l, the list is not modified.// The mark must not be nil.func (l *List) InsertAfter(v any, mark *Element) *Element { if mark.list != l { return nil } // see comment in List.Remove about initialization of l return l.insertValue(v, mark)}// MoveToFront moves element e to the front of list l.// If e is not an element of l, the list is not modified.// The element must not be nil.func (l *List) MoveToFront(e *Element) { if e.list != l || l.root.next == e { return } // see comment in List.Remove about initialization of l l.move(e, &l.root)}// MoveToBack moves element e to the back of list l.// If e is not an element of l, the list is not modified.// The element must not be nil.func (l *List) MoveToBack(e *Element) { if e.list != l || l.root.prev == e { return } // see comment in List.Remove about initialization of l l.move(e, l.root.prev)}// MoveBefore moves element e to its new position before mark.// If e or mark is not an element of l, or e == mark, the list is not modified.// The element and mark must not be nil.func (l *List) MoveBefore(e, mark *Element) { if e.list != l || e == mark || mark.list != l { return } l.move(e, mark.prev)}// MoveAfter moves element e to its new position after mark.// If e or mark is not an element of l, or e == mark, the list is not modified.// The element and mark must not be nil.func (l *List) MoveAfter(e, mark *Element) { if e.list != l || e == mark || mark.list != l { return } l.move(e, mark)}// PushBackList inserts a copy of another list at the back of list l.// The lists l and other may be the same. They must not be nil.func (l *List) PushBackList(other *List) { l.lazyInit() for i, e := other.Len(), other.Front(); i > 0; i, e = i-1, e.Next() { l.insertValue(e.Value, l.root.prev) }}// PushFrontList inserts a copy of another list at the front of list l.// The lists l and other may be the same. They must not be nil.func (l *List) PushFrontList(other *List) { l.lazyInit() for i, e := other.Len(), other.Back(); i > 0; i, e = i-1, e.Prev() { l.insertValue(e.Value, &l.root) }}
来源：互联网
免责声明：如果侵犯了您的权益，请联系站长（1277306191@qq.com），我们会及时删除侵权内容，谢谢合作！ |
Archiver 手机版 小黑屋 福建二哥
( 闽ICP备2022004717号|
闽公网安备35052402000345号 )
微信公众号
添加方式：