双向链表概述

• 双向链表结构如下图

• 双向链表结构中元素在内存中不是紧邻空间，而是每个元素存放上一个元素和后一个元素的地址

第一个元素称为头（head）元素，前连接（前置指针域）为nil

最后一个元素称为尾（foot）元素，后连接（后置指针域）为nil

• 双向链表的优点：

在执行新增元素表或删除元素时效率高，获取任意一个元素，可以方便地在这个元素前后插入元素

充分利用内存空间，实现内存灵活管理

可以实现正序和逆序遍历

头元素或尾元素新增或删除时效率很高

• 双向链表的缺点：

链表增加了元素的指针域，空间开销较大

遍历时跳跃性查找内容，大量数据遍历性能低

双向链表容器List

• 在Go语言标准库的container/list包提供了双向链表List
• List结构体定义如下

root表示根元素

len表示链表中有多少个元素

package main

import (
   "container/list"
)

func main() {
   type List struct {
      root Element  //报错？List.Element
      len int
   }
}

• 其中Element结构体定义如下

next表示下一个元素，使用Next()可以获取到

prev表示上一个元素，使用Prev()可以获取到

list表示元素属于哪个链表

Value表示元素的值，interface()在Go语言中表示任意类型

// Element is an element of a linked list.
type Element struct {
   // Next and previous pointers in the doubly-linked list of elements.
   // To simplify the implementation, internally a list l is implemented
   // as a ring, such that &l.root is both the next element of the last
   // list element (l.Back()) and the previous element of the first list
   // element (l.Front()).
   next, prev *Element

   // The list to which this element belongs.
   list *List

   // The value stored with this element.
   Value interface{}
}

双向链表代码演示

• 创建链表：

直接使用container/list包下的New()新建一个空的List

package main

import (
   "container/list"  
   "fmt"
)

//上述部分在接下来的代码中省略

func main() {
   mylist := list.New()
   fmt.Println(mylist) //输出list中内容：&{{0xc000070330 0xc000070330 <nil> <nil>} 0}
   fmt.Println(mylist.Len())//输出链表中元素的个数：0
   fmt.Printf("%p", mylist) //输出地址：0xc000070330
}

• Go语言标准库中提供了很多向双向链表中添加元素的函数

func main() {
   mylist := list.New()
   fmt.Println(mylist) //输出list中内容：&{{0xc000070330 0xc000070330 <nil> <nil>} 0}
   fmt.Println(mylist.Len())//输出链表中元素的个数：0
   fmt.Printf("%p\n", mylist) //输出地址：0xc000070330

   //添加到最后，list["a"]
   mylist.PushBack("a")
   fmt.Println(mylist) //输出：&{{0xc0000b8360 0xc0000b8360 <nil> <nil>} 1}
   //添加到最前面list["b", "a"]
   mylist.PushFront("b")
   fmt.Println(mylist) //输出：&{{0xc0000703f0 0xc000070390 <nil> <nil>} 2}
   mylist.InsertAfter("c", mylist.Front())
   fmt.Println(mylist)//输出：&{{0xc0000703f0 0xc000070390 <nil> <nil>} 3}
   mylist.InsertBefore("d", mylist.Back())
   fmt.Println(mylist)//输出：&{{0xc0000703f0 0xc000070390 <nil> <nil>} 4}
}

• 取出链表中的元素

func main() {    
   //取出最后一个元素的值
   fmt.Println(mylist.Back().Value) //输出：a
   //取出第一个元素的值
   fmt.Println(mylist.Front().Value) //输出：b

   //只能从头向后找，或者从后向前找，获取元素内容
   n := 2 //取出第几个元素的值
   if n > 0 && n < mylist.Len() {
      for i := 0; i < n; i++ {
         fmt.Println(mylist.Front().Next().Value) //输出两行c
      }
   }

   //遍历所有值
   for e := mylist.Front(); e != nil; e = e.Next(){
      fmt.Println(e.Value)   //依次换行输出b/c/d/a
   }
}

• 移动元素顺序

func main() {
   //移动元素的顺序
   mylist.MoveToBack(mylist.Front()) //把第一个移动到后面
   mylist.MoveToFront(mylist.Back()) //把最后一个移动到前面
   mylist.MoveAfter(mylist.Front(),mylist.Back()) //把第一个元素移动到第二个元素后面
   mylist.MoveBefore(mylist.Front(), mylist.Back()) //把第一个参数元素，移动到第二个参数
}

• 删除元素

func main() {
   //删除元素
   fmt.Println("=============================")
   fmt.Println(mylist.Front())//&{0xc000070390 0xc000070330 0xc000070330 d}
   mylist.Remove(mylist.Front())
   fmt.Println(mylist.Front())//&{0xc000070450 0xc000070330 0xc000070330 a}
}

双向循环链表

• 循环链表特定是没有节点的指针域为nil，通过任何一个元素都可以找到其它元素
• 环形链表结构如下

• 双向循环链表和双向链表区别

1、双向循环链表没有严格意义上的头元素和尾元素

2、没有元素的前连接和后连接为nil

3、一个长度为n的双向循环链表，通过某个元素向某个方向移动，在查找最多n-1次后一定会找到另一个元素

Go语言中的双向循环链表

• 在container/ring包下结构体Ring源码如下

1、官方明确说明了Ring是循环链表的元素，又是环形链表

2、实际使用时Ring遍历就是环形链表第一个元素

type Ring struct {
   next, prev *Ring
   Value      interface{} // for use by client; untouched by this library
}

• Go语言标准库中对container/ring包提供的API如下

双向循环链表代码演示

• 实例化、赋值、遍历

func main() {
   //代表整个循环链表，又代表第一个元素
   r := ring.New(5)
   r.Value=0
   r.Next().Value=1
   r.Next().Next().Value=2
   //r.Next().Next().Next().Value=3
   //r.Next().Next().Next().Next().Value=4

   r.Prev().Value=1
   r.Prev().Prev().Value=3

   //循环链表有几个元素，func执行几次，i代表当前执行元素的内容
   r.Do(func(i interface{}){
      fmt.Println(i)
   })
   /*
   0
   1
   2
   3
   1
   */
}