链表结构大家都不陌生了，与数组一样都是存储数据用的，形成互补。链表增删快，查询慢，数组查询快，增删慢；两者各有各的应用场景。go语言标准库中实现了双向链表和环形链表两种链表结构
双向链表位于go标准库：container/list
结构（双向链表以结构体实现） type List struct { root Element len int }root 为链表的根元素，len为链表的长度。
创建链表go提供list.New方法创建一个链表，返回一个链表指针。
func New() *List { return new(List).Init() }
package main import ( "container/list" ) func main() { // 返回一个链表指针 l := list.New() log.Println(l.Len()) // 打印 0，新建链表长度为0 }下面介绍链表的各个方法（增删改查）
往链表的头部插入一个元素，返回插入元素的值的指针。 func (l *List) PushFront(v interface{}) *Element元素Element的结构如下：
type Element struct {
next, prev *Element // next为当前元素的下一个元素，prev为当前元素的上一个元素
list *List // list 为当前元素所在链表的指针
Value interface{} // Value为当前元素所存储的值
}
func main() { l := list.New() e := l.PushFront("go") // 插入一个go字符串，返回插入数据的指针 log.Println(l.Len()) // 打印 1 } 往链表的尾部插入一个元素，返回插入元素的值的指针。 func (l *List) PushBack(v interface{}) *Element func main() { l := list.New() l.PushFront("go") l.PushBack("list") log.Println(l.Len()) // 打印 2 // 遍历链表 for e := l.Front(); e != nil; e = e.Next() { log.Print(e.Value) } }运行结果如下
func (l *List) Front() *Element // 返回链表的第一个元素或nil func (l *List) Back() *Element // 返回链表的最后一个元素或nil func main() { l := list.New() l.PushFront("go") l.PushBack("list") log.Println(l.Front().Value) // 获取第一个元素的值 log.Println(l.Back().Value) // 获取最后一个元素的值 }
结果如下：
func (l *List) InsertAfter(v interface{}, mark *Element) *Element // 往mark元素后插入一个元素 func (l *List) InsertBefore(v interface{}, mark *Element) *Element // 往mark元素前插入一个元素 func main() { l := list.New() first := l.PushFront("first") // 插入一个first字符串 end := l.PushBack("end") // 插入一个end字符串 l.InsertBefore("InsertBefore", first) // 在first元素前插入 l.InsertAfter("InsertBefore", end) // 在end元素后插入 for e := l.Front(); e != nil; e = e.Next() { log.Print(e.Value) } }结果如下：
func (l *List) MoveToFront(e *Element) // 将元素移动到链表头部 func (l *List) MoveToBack(e *Element) // 将元素移动到链表尾部 func (l *List) MoveBefore(e, mark *Element) // 将e元素移动到mark元素前面 func (l *List) MoveAfter(e, mark *Element) // 将e元素移动到mark元素后 func main() { l := list.New() a := l.PushBack("A") b := l.PushBack("B") c := l.PushBack("C") d := l.PushBack("D") // 顺序 A B C D l.MoveToBack(a) // a移动到尾部 l.MoveToFront(d) // d移动到头部 l.MoveBefore(b, a) // b移动到a的前面 l.MoveAfter(c, d) // c移动到d后面 for e := l.Front(); e != nil; e = e.Next() { log.Print(e.Value) } }结果如下：
func (l *List) Remove(e *Element) interface{} // 删除e元素
func (l *List) Init() *List // 将链表清空
func main() { l := list.New() a := l.PushBack("A") l.PushBack("B") l.PushBack("C") l.PushBack("D") l.Remove(a) // 移除a元素 log.Println(l.Len()) l.Init() // 清空链表 for e := l.Front(); e != nil; e = e.Next() { log.Print(e.Value) } log.Println(l.Len()) }结果如下：
func (l *List) PushFrontList(other *List) // 将other链表追加到l链表的头部 func (l *List) PushBackList(other *List) // 将other链表追加到l链表的末尾 func main() { l := list.New() l.PushBack("l") l2 := list.New() l2.PushBack("l2") l.PushFrontList(l2) // l2追加到头部 l3 := list.New() l3.PushFront("l3") l.PushBackList(l3) // l3追加到尾部 for e := l.Front(); e != nil; e = e.Next() { log.Print(e.Value) } }结果如下：
至此，list双向链表的api算是介绍完了，还有一个上面没有用到的方法
func (e *Element) Prev() *Element // 返回当前元素的前一个元素，跟Next方法一样，只是顺序不同而已