2.9 Go 双向链表
- Go container/list包

2.9 Go 双向链表

双向链表也叫双链表，是链表的一种，它的每个数据结点中都有两个指针，分别指向直接后继和直接前驱。所以，从双向链表中的任意一个结点开始，都可以很方便地访问它的前驱结点和后继结点，相对于单链表来讲：往前往后遍历都很方便。

相对于单向链表优势：

可以双向遍历

插入删除不需要移动元素外，可以原地插入删除效率更高，当然这也是以牺牲存储空间为代价。

插入数据

删除数据

Go container/list包

实现了基本的双向链表功能，包括元素的插入、删除、移动功能

package main
import (
   "container/list"
   "fmt"
)
func main() {
   l := list.New()
   //末尾插入值为1的元素，并返回该元素。
   v1 := l.PushBack(1)
   //首部插入值为2的元素，并返回该元素
   v2 := l.PushFront(2)
   //在元素v1前插入3
   l.InsertBefore(3, v2)
   //在元素v1后插入4
   l.InsertAfter(4, v1)
   fmt.Printf("len: %v\n", l.Len())
   fmt.Printf("first: %#v\n", l.Front())
   fmt.Printf("second: %#v\n", l.Front().Next())
   // 遍历列表并打印其内容。
   for e := l.Front(); e != nil; e = e.Next() {
      fmt.Println(e.Value)
   }
}

类型元素

func (e Element) Next() Element //返回该元素的下一个元素，如果没有下一个元素则返回nil。 func (e Element) Prev() Element//返回该元素的前一个元素，如果没有前一个元素则返回nil。

类型列表

func New() List //返回一个初始化的list func (l List) Back() Element //获取list l的最后一个元素 func (l List) Front() Element //获取list l的第一个元素 func (l List) Init() List //list l初始化或者清除list l func (l List) InsertAfter(v interface{}, mark Element) Element //在list l中元素mark之后插入一个值为v的元素，并返回该元素，如果mark不是list中元素，则list不改变。 func (l List) InsertBefore(v interface{}, mark Element) Element//在list l中元素mark之前插入一个值为v的元素，并返回该元素，如果mark不是list中元素，则list不改变。 func (l List) Len() int //获取list l的长度 func (l List) MoveAfter(e, mark Element) //将元素e移动到元素mark之后，如果元素e或者mark不属于list l，或者e==mark，则list l不改变。 func (l List) MoveBefore(e, mark Element)//将元素e移动到元素mark之前，如果元素e或者mark不属于list l，或者e==mark，则list l不改变。 func (l List) MoveToBack(e Element)//将元素e移动到list l的末尾，如果e不属于list l，则list不改变。 func (l List) MoveToFront(e Element)//将元素e移动到list l的首部，如果e不属于list l，则list不改变。 func (l List) PushBack(v interface{}) Element//在list l的末尾插入值为v的元素，并返回该元素。 func (l List) PushBackList(other List)//在list l的尾部插入另外一个list，其中l和other可以相等。 func (l List) PushFront(v interface{}) Element//在list l的首部插入值为v的元素，并返回该元素。 func (l List) PushFrontList(other List)//在list l的首部插入另外一个list，其中l和other可以相等。

详见： container/list

小结：

由于container/list不是并发安全的，可以通过加锁（sync.Mutex）来解决。

双向链表的优点在于快速插入和删除，适用于频繁插入、删除的场景。和slice、数组比，slice、数组的优势在于查询和遍历，适用于频发查询、遍历的场景。

links