双向链表
import ( "container/list" "fmt" )
双向链表的结构：
[ nil | cur | next ]—><—[ prev | cur | next ]—><—[ prev | cur | nil ]
双向链表结构中元素在内存中不是紧邻空间， 而是每个元素中存放上一个元素和后一个元素的【地址】。
1. 第一个元素称为头(head)元素前连接(前置指针域)为nil。 2. 最后一个元素称为尾(foot)元素,后连接(后置指针域)为nil。
双向链表的优点：
1. 在执行新增元素或删除元素时效率高，获取任意一个元素,可以方便的在这个元素前后插入元素。 2. 充分利用内存空间，实现内存灵活管理 3. 可实现正序和逆序遍历 4. 头元素和尾元素 新增 或 删除 时效率较高
双向链表的缺点：
1. 链表增加了元素的指针域，空间开销比较大 2. 遍历时跳跃性查找内容大量数据遍历性能低
双向链表容器List：
在Go语言标准库的container/list包提供了双向链表List
List的使用：
直接使用container/list包下的New()新建一个空的List
linkList := list.New() linkList.PushBack("z") // 添加到最后面 z linkList.PushFront("a") // 添加到最前面 a z linkList.InsertBefore("a-", linkList.Front()) // 向第一个元素后添加元素 a- a z linkList.InsertAfter("z+", linkList.Back()) // 向最后一个元后添加元素 a- a z z+ fmt.Println(linkList.Back().Value) // 取出最后一个元素的值 fmt.Println(linkList.Front().Value) // 取出第一个元素的值 linkList.MoveAfter(linkList.Front(),linkList.Back()) // 将某个元素移动指定元素后面 a z z+ a- linkList.MoveBefore(linkList.Back(),linkList.Front()) // 将某个元素移动指定元素前面 a- a z z+ linkList.MoveToBack(linkList.Front()) // 将某个元素移动到最后 linkList.MoveToFront(linkList.Back()) // 将某个元素移动到最前面 linkList.Remove(linkList.Front()) //删除某个元素 // 遍历所有值 a- a z z+ for head := linkList.Front(); head != nil; head = head.Next() { fmt.Println(head.Value) } // 遍历指定值 a n := 2 var cur *list.Element if n > 0 && n < linkList.Len() { if n == 1 { cur = linkList.Front() } else if n == linkList.Len() { cur = linkList.Back() } else { cur = linkList.Front() for i := 1; i < n; i++ { cur= cur.Next() } } fmt.Println(cur.Value) }
