今天发现一个开发中很少使用的自带包 container/list，这个包实现了双线链表的数据结构。跟 Slice 相比，双向链表的插入和删除的时间复杂度为O(1)，Slice 为O(n)。
关于链表的基础知识：https://blog.csdn.net/weixin_42117918/article/details/81838498
golang 中为了实现双向链表创建了两个结构体：Element，List：
// 节点结构体
type Element struct {
// 前后节点指针
next, prev *Element
// 链表指针，用于标识该节点属于哪一个链表，链表插入和删除时会根据此字段进行判断
list *List
// 节点的值
Value interface{}
}
// 链表结构体
type List struct {
// 相当于头节点，go 中使用 root 属性将整个链表首尾连接起来，使其可以快速向链表首尾进行操作，可参考向首尾插入方法
root Element
// 链表长度
len int
}
网友评论