。

本文第一部分总结源码包中的方法#xff0c;第二部分展示使用list包的常见示例用法以及刷题时的用法。

食用指南#xff1a;先看第二部分的常用示例用法然后再用到时在第一部…list容器

Go语言中list容器定义在container/list包中实现了一个双向链表。

本文第一部分总结源码包中的方法第二部分展示使用list包的常见示例用法以及刷题时的用法。

食用指南先看第二部分的常用示例用法然后再用到时在第一部分找对应的方法。

更多内容以及其他Go常用数据结构的实现在这里感谢Starhttps://github.com/acezsq/Data_Structure_Golang

文章目录

方法所属类型作用New()list包函数创建一个listNext()

*ElementElement获取当前结点的下一个结点Prev()

*ElementElement获取当前结点的上一个结点Len()

intList获取链表长度Front()

*ElementList在链表头部插入一个结点PushBack(v

any)

*ElementList在链表末尾插入一个结点insert(e,

*Element)

*ElementList在一个结点之后插入一个新的结点insertValue(v

any,

*ElementList在一个结点之后插入一个新的结点InsertBefore(v

any,

*ElementList在一个结点之前插入一个新的结点InsertAfter(v

any,

*Element)List将一个结点移动到另一个结点后面remove(e

*Element)

*Element)List将一个结点移动到链表头部MoveToBack(e

*Element)List将一个结点移动到链表尾部MoveBefore(e,

mark

*Element)List移动一个结点到另一个结点前面MoveAfter(e,

mark

*List)List将另一个链表复制到当前链表后面PushFrontList(o***r

prev分别表示当前节点指向下一个和上一个节点的指针list表示当前节点属于哪个双向链表而Value则表示当前结点存储的具体的值。

Element

}List类型定义了一个双向链表空的List类型表示一个待使用的空链表。

root是一个Element类型的字段它代表了链表中的哨兵元素哨兵元素是一个特殊的元素它不存储任何实际的值只是作为链表的起始和结束标记。

len是一个整型字段表示链表中当前的元素数量不包括哨兵元素。

List

}实现对List类型的延迟初始化。

具体来说它用于在第一次访问List对象时检查是否已经进行了初始化如果没有则执行初始化操作。

lazyInit

}在一个结点之后插入一个新的结点输入是结点类型对象。

另外需要修改指针以及新节点归属的链表以及链表的长度。

insert

在链表尾部添加元素l.PushBack(1)l.PushBack(2)l.PushBack(3)//

遍历链表并打印元素值for

l.Front().Next()l.Remove(elementToRemove)//

在指定元素之前插入元素elementToInsertBefore

在指定元素之后插入元素elementToInsertAfter

遍历链表并打印元素值for

从下面Element类型的定义中可以看到Value的类型时any类型也就是空接口类型。

所以在获取到结点的Value时需要通过反射获取具体的值类型用于后续任务。

Element

node.Value.(*entry)这行代码通过反射获取到结点值的具体的类型这样才能使得后续使用e时是*entry类型。

type

map[int]*list.ElementfreqToList

map[int]*list.List

map[int]*list.Element{},freqToList:

}func

c.freqToList[e.freq].PushFront(e)

}func

c.freqToList[e.freq]lst.Remove(node)if

lst.Len()0

{c.minFreq}}e.freqc.pushfront(e)return

}func

c.freqToList[c.minFreq]delete(c.keyToNode,lst.Remove(lst.Back()).(*entry).key)if

lst.Len()0

{delete(c.freqToList,c.minFreq)}}c.pushfront(entry{key,value,1})c.minFreq

}/***