列表

一、列表 List

我们又经常听到 列表 List 数据结构，其实这只是更宏观的统称，表示存放数据的队列。

列表 List：可以存放数据的数据结构，数据按顺序排列，可以依次入队和出队，

列表有序号关系，可以取出某个序号的数据。先进先出的 队列 (queue) 和先进后出的 栈（stack） 都是列表。

大家也经常听说一种叫 线性表 的数据结构，表示具有相同特性的数据元素的有限序列，实际上就是 列表 的同义词。

我们一般写算法进行数据计算，数据处理，都需要有个地方来存数据，我们可以使用封装好的数据结构 List。

列表的实现有 顺序表示 或 链式表示。

顺序表示：指的是用一组 地址连续的存储单元 依次存储线性表的数据元素，称为线性表的 顺序存储结构。它以 物理位置相邻 来表示线性表中数据元素间的逻辑关系，可随机存取表中任一元素。顺序表示的又叫 顺序表，也就是用数组来实现的列表。

链式表示：指的是用一组 任意的存储单元 存储线性表中的数据元素，称为线性表的 链式存储结构。它的存储单元可以是连续的，也可以是不连续的。在表示数据元素之间的逻辑关系时，除了存储其本身的信息之外，还需存储一个指示其直接后继的信息，也就是用链表来实现的列表。

我们在前面已经实现过这两种表示的数据结构：先进先出的 队列 (queue) 和先进后出的 栈（stack）。

接下来我们会来实现链表形式的双端列表，也叫双端队列，这个数据结构应用场景更广泛一点。在实际工程应用上，缓存数据库 Redis 的 列表List 基本类型就是用它来实现的。

二、实现双端列表

双端列表，也可以叫双端队列。

我们会用双向链表来实现这个数据结构：

  1. // DoubleList 双端列表，双端队列
  2. type DoubleList struct {
  3.     head *ListNode  // 指向链表头部
  4.     tail *ListNode  // 指向链表尾部
  5.     len  int        // 列表长度
  6.     lock sync.Mutex // 为了进行并发安全pop弹出操作
  7. }
  9. // ListNode 列表节点
  10. type ListNode struct {
  11.     pre   *ListNode // 前驱节点
  12.     next  *ListNode // 后驱节点
  13.     value string    // 值
  14. }

设计结构体 DoubleList 指向队列头部 head 和尾部 tail 的指针字段，方便找到链表最前和最后的节点。

链表节点之间是双向链接的，链表的第一个元素的前驱节点为 nil，最后一个元素的后驱节点也为 nil。如图：

列表 - 图1

我们实现的双端列表和 Golang 标准库 container/list 中实现的不一样，感兴趣的可以阅读标准库的实现。

2.1.列表节点普通操作

  1. // GetValue 获取节点值
  2. func (node *ListNode) GetValue() string {
  3.     return node.value
  4. }
  6. // GetPre 获取节点前驱节点
  7. func (node *ListNode) GetPre() *ListNode {
  8.     return node.pre
  9. }
  11. // GetNext 获取节点后驱节点
  12. func (node *ListNode) GetNext() *ListNode {
  13.     return node.next
  14. }
  16. // HashNext 是否存在后驱节点
  17. func (node *ListNode) HashNext() bool {
  18.     return node.pre != nil
  19. }
  21. // HashPre 是否存在前驱节点
  22. func (node *ListNode) HashPre() bool {
  23.     return node.next != nil
  24. }
  26. // IsNil 是否为空节点
  27. func (node *ListNode) IsNil() bool {
  28.     return node == nil
  29. }
  31. // Len 返回列表长度
  32. func (list *DoubleList) Len() int {
  33.     return list.len
  34. }

以上是对节点结构体 ListNode 的操作，主要判断节点是否为空，有没有后驱和前驱节点，返回值等，时间复杂度都是 O(1)。

2.2.从头部开始某个位置前插入新节点

我们参考数组下标，下标从0开始。从双端列表的头部，插入新的节点。

  1. // AddNodeFromHead 从头部开始，添加节点到第N+1个元素之前，
  2. // N=0表示添加到第一个元素之前，表示新节点成为新的头部，
  3. // N=1表示添加到第二个元素之前，以此类推
  4. func (list *DoubleList) AddNodeFromHead(n int, v string) {
  5.     // 加并发锁
  6.     list.lock.Lock()
  7.     defer list.lock.Unlock()
  9.     // 如果索引超过或等于列表长度，一定找不到，直接panic
  10.     if n != 0 && n >= list.len {
  11.         panic("index out")
  12.     }
  14.     // 先找出头部
  15.     node := list.head
  17.     // 往后遍历拿到第 N+1 个位置的元素
  18.     for i := 1; i <= n; i++ {
  19.         node = node.next
  20.     }
  22.     // 新节点
  23.     newNode := new(ListNode)
  24.     newNode.value = v
  26.     // 如果定位到的节点为空，表示列表为空，将新节点设置为新头部和新尾部
  27.     if node.IsNil() {
  28.         list.head = newNode
  29.         list.tail = newNode
  30.     } else {
  31.         // 定位到的节点，它的前驱
  32.         pre := node.pre
  34.         // 如果定位到的节点前驱为nil，那么定位到的节点为链表头部，需要换头部
  35.         if pre.IsNil() {
  36.             // 将新节点链接在老头部之前
  37.             newNode.next = node
  38.             node.pre = newNode
  39.             // 新节点成为头部
  40.             list.head = newNode
  41.         } else {
  42.             // 将新节点插入到定位到的节点之前
  43.             // 定位到的节点的前驱节点 pre 现在链接到新节点上
  44.             pre.next = newNode
  45.             newNode.pre = pre
  47.             // 定位到的节点的后驱节点 node.next 现在链接到新节点上
  48.             node.next.pre = newNode
  49.             newNode.next = node.next
  51.         }
  53.     }
  55.     // 列表长度+1
  56.     list.len = list.len + 1
  57. }

首先加锁实现并发安全：

  1.     // 加并发锁
  2.     list.lock.Lock()
  3.     defer list.lock.Unlock()

然后判断索引是否超出列表长度，其中 n=0 表示要成为新的头部节点，我们放过它：

  1.     // 如果索引超过或等于列表长度，一定找不到，直接panic
  2.     if n != 0 && n >= list.len {
  3.         panic("index out")
  4.     }

如果 n=0 表示要插入到第一个节点之前，也就是新节点想成为新的链表头部。

如果 n=1 表示要插入到第二个节点之前，新节点成为第二个节点，以此类推。

首先，找出列表的头部：

  1.     node := list.head

然后往后面遍历，定位到索引 n 指定的节点 node，我们要在这个节点之前插入新的节点：

  1.     // 往后遍历拿到第 N+1 个位置的元素
  2.     for i := 1; i <= n; i++ {
  3.         node = node.next
  4.     }

接着初始化新节点：

  1.     newNode := new(ListNode)

定位到的节点有三种情况，我们需要在该节点之前插入新节点：

列表 - 图2

第一种情况，判断定位到的节点 node 是否为空，如果为空，表明列表没有元素，将新节点设置为新头部和新尾部即可：

  1.     // 如果定位到的节点为空，表示列表为空，将新节点设置为新头部和新尾部
  2.     if node.IsNil() {
  3.         list.head = newNode
  4.         list.tail = newNode
  5.     }

否则，我们要插入新的节点到非空的列表上。 我们找到定位到的节点的前驱节点：pre := node.pre，我们要把新节点变成定位到的节点的前驱节点，之前的前驱节点 pre 要往前顺延。

第二种情况，如果前驱节点为空：pre.IsNil()，表明定位到的节点 node 为头部，那么新节点要取代它，成为新的头部：

  1.         if pre.IsNil() {
  2.             // 将新节点链接在老头部之前
  3.             newNode.next = node
  4.             node.pre = newNode
  5.             // 新节点成为头部
  6.             list.head = newNode
  7.         }

新节点成为新的头部，需要将新节点的后驱设置为老头部：newNode.next = node，老头部的前驱为新头部：node.pre = newNode，并且新头部变化：list.head = newNode。

第三种情况，如果定位到的节点的前驱节点不为空，表明定位到的节点 node 不是头部节点，那么我们只需将新节点链接到节点 node 之前即可：

  1.             // 定位到的节点的前驱节点 pre 现在链接到新节点前
  2.             pre.next = newNode
  3.             newNode.pre = pre
  5.             // 定位到的节点链接到新节点之后
  6.             newNode.next = node
  7.             node.pre = newNode

先将定位到的节点的前驱节点和新节点绑定，因为现在新节点插在前面了，把定位节点的前驱节点的后驱设置为新节点：pre.next = newNode，新节点的前驱设置为定位节点的前驱节点：newNode.pre = pre。

同时，定位到的节点现在要链接到新节点之后，所以新节点的后驱设置为：newNode.next = node，定位到的节点的前驱设置为：node.pre = newNode。

当然插入新节点的最后，我们要将链表长度加一：

  1.     // 列表长度+1
  2.     list.len = list.len + 1

大部分时间花在遍历位置上，如果 n=0，那么时间复杂度为 O(1)，否则为 O(n)。

2.3.从尾部开始某个位置后插入新节点

  1. // AddNodeFromTail 从尾部开始，添加节点到第N+1个元素之后，N=0表示添加到第一个元素之后，表示新节点成为新的尾部，N=1表示添加到第二个元素之后，以此类推
  2. func (list *DoubleList) AddNodeFromTail(n int, v string) {
  3.     // 加并发锁
  4.     list.lock.Lock()
  5.     defer list.lock.Unlock()
  7.     // 如果索引超过或等于列表长度，一定找不到，直接panic
  8.     if n != 0 && n >= list.len {
  9.         panic("index out")
  10.     }
  12.     // 先找出尾部
  13.     node := list.tail
  15.     // 往前遍历拿到第 N+1 个位置的元素
  16.     for i := 1; i <= n; i++ {
  17.         node = node.pre
  18.     }
  20.     // 新节点
  21.     newNode := new(ListNode)
  22.     newNode.value = v
  24.     // 如果定位到的节点为空，表示列表为空，将新节点设置为新头部和新尾部
  25.     if node.IsNil() {
  26.         list.head = newNode
  27.         list.tail = newNode
  28.     } else {
  29.         // 定位到的节点，它的后驱
  30.         next := node.next
  32.         // 如果定位到的节点后驱为nil，那么定位到的节点为链表尾部，需要换尾部
  33.         if next.IsNil() {
  34.             // 将新节点链接在老尾部之后
  35.             node.next = newNode
  36.             newNode.pre = node
  38.             // 新节点成为尾部
  39.             list.tail = newNode
  40.         } else {
  41.             // 将新节点插入到定位到的节点之后
  42.             // 新节点链接到定位到的节点之后
  43.             newNode.pre = node
  44.             node.next = newNode
  46.             // 定位到的节点的后驱节点链接在新节点之后
  47.             newNode.next = next
  48.             next.pre = newNode
  50.         }
  52.     }
  54.     // 列表长度+1
  55.     list.len = list.len + 1
  56. }

操作和头部插入节点相似，自行分析。

2.4.从头部开始某个位置获取列表节点

  1. // IndexFromHead 从头部开始往后找，获取第N+1个位置的节点，索引从0开始。
  2. func (list *DoubleList) IndexFromHead(n int) *ListNode {
  3.     // 索引超过或等于列表长度，一定找不到，返回空指针
  4.     if n >= list.len {
  5.         return nil
  6.     }
  8.     // 获取头部节点
  9.     node := list.head
  11.     // 往后遍历拿到第 N+1 个位置的元素
  12.     for i := 1; i <= n; i++ {
  13.         node = node.next
  14.     }
  16.     return node
  17. }
  18. `

如果索引超出或等于列表长度，那么找不到节点，返回空。

否则从头部开始遍历，拿到节点。

时间复杂度为：O(n)。

2.5.从尾部开始某个位置获取列表节点

  1. // IndexFromTail 从尾部开始往前找，获取第N+1个位置的节点，索引从0开始。
  2. func (list *DoubleList) IndexFromTail(n int) *ListNode {
  3.     // 索引超过或等于列表长度，一定找不到，返回空指针
  4.     if n >= list.len {
  5.         return nil
  6.     }
  8.     // 获取尾部节点
  9.     node := list.tail
  11.     // 往前遍历拿到第 N+1 个位置的元素
  12.     for i := 1; i <= n; i++ {
  13.         node = node.pre
  14.     }
  16.     return node
  17. }

操作和从头部获取节点一样，请自行分析。

2.6.从头部开始移除并返回某个位置的节点

获取某个位置的元素，并移除它。

  1. // PopFromHead 从头部开始往后找，获取第N+1个位置的节点，并移除返回
  2. func (list *DoubleList) PopFromHead(n int) *ListNode {
  3.     // 加并发锁
  4.     list.lock.Lock()
  5.     defer list.lock.Unlock()
  7.     // 索引超过或等于列表长度，一定找不到，返回空指针
  8.     if n >= list.len {
  9.         return nil
  10.     }
  12.     // 获取头部
  13.     node := list.head
  15.     // 往后遍历拿到第 N+1 个位置的元素
  16.     for i := 1; i <= n; i++ {
  17.         node = node.next
  18.     }
  20.     // 移除的节点的前驱和后驱
  21.     pre := node.pre
  22.     next := node.next
  24.     // 如果前驱和后驱都为nil，那么移除的节点为链表唯一节点
  25.     if pre.IsNil() && next.IsNil() {
  26.         list.head = nil
  27.         list.tail = nil
  28.     } else if pre.IsNil() {
  29.         // 表示移除的是头部节点，那么下一个节点成为头节点
  30.         list.head = next
  31.         next.pre = nil
  32.     } else if next.IsNil() {
  33.         // 表示移除的是尾部节点，那么上一个节点成为尾节点
  34.         list.tail = pre
  35.         pre.next = nil
  36.     } else {
  37.         // 移除的是中间节点
  38.         pre.next = next
  39.         next.pre = pre
  40.     }
  42.     // 节点减一
  43.     list.len = list.len - 1
  44.     return node
  45. }

首先加并发锁实现并发安全:

  1.     // 加并发锁
  2.     list.lock.Lock()
  3.     defer list.lock.Unlock()

先判断索引是否超出列表长度，如果超出直接返回空指针。：

  1.     // 索引超过或等于列表长度，一定找不到，返回空指针
  2.     if n >= list.len {
  3.         return nil
  4.     }

获取头部，然后遍历定位到第 N+1 个位置的元素:

  1.     // 获取头部
  2.     node := list.head
  4.     // 往后遍历拿到第 N+1 个位置的元素
  5.     for i := 1; i <= n; i++ {
  6.         node = node.next
  7.     }

获取要移除的节点的前驱和后驱：

  1.     // 移除的节点的前驱和后驱
  2.     pre := node.pre
  3.     next := node.next

定位到的并要移除的节点有三种情况发生，移除的是头部，尾部或者中间节点：

列表 - 图3

我们这么这里：

如果前驱和后驱都为空：

  1.     // 如果前驱和后驱都为nil，那么移除的节点为链表唯一节点
  2.     if pre.IsNil() && next.IsNil() {
  3.         list.head = nil
  4.         list.tail = nil
  5.     }

那么要移除的节点是链表中唯一的节点，直接将列表头部和尾部置空即可。

如果移除的是头部或尾部节点：

  1.     else if pre.IsNil() {
  2.         // 表示移除的是头部节点，那么下一个节点成为头节点
  3.         list.head = next
  4.         next.pre = nil
  5.     } else if next.IsNil() {
  6.         // 表示移除的是尾部节点，那么上一个节点成为尾节点
  7.         list.tail = pre
  8.         pre.next = nil
  9.     }

当前驱节点为空：pre.IsNil()，表示移除的是头部节点，那么头部节点的下一个节点要成为新的头部：list.head = next，并且这时新的头部前驱要设置为空：next.pre = nil。

同理，当后驱节点为空：next.IsNil()，表示移除的是尾部节点，需要将尾部节点的前一个节点设置为新的尾部：list.tail = pre，并且这时新的尾部后驱要设置为空：pre.next = nil。

如果移除的节点处于两个节点之间，那么将这两个节点链接起来即可:

  1.     // 移除的是中间节点
  2.     pre.next = next
  3.     next.pre = pre

当然，最后列表长度减一：

  1.     // 节点减一
  2.     list.len = list.len - 1

主要的耗时用在定位节点上，其他的操作都是链表链接，可以知道时间复杂度为：O(n)。

2.7.从尾部开始移除并返回某个位置的节点

  1. // PopFromTail 从尾部开始往前找，获取第N+1个位置的节点，并移除返回
  2. func (list *DoubleList) PopFromTail(n int) *ListNode {
  3.     // 加并发锁
  4.     list.lock.Lock()
  5.     defer list.lock.Unlock()
  7.     // 索引超过或等于列表长度，一定找不到，返回空指针
  8.     if n >= list.len {
  9.         return nil
  10.     }
  12.     // 获取尾部
  13.     node := list.tail
  15.     // 往前遍历拿到第 N+1 个位置的元素
  16.     for i := 1; i <= n; i++ {
  17.         node = node.pre
  18.     }
  20.     // 移除的节点的前驱和后驱
  21.     pre := node.pre
  22.     next := node.next
  24.     // 如果前驱和后驱都为nil，那么移除的节点为链表唯一节点
  25.     if pre.IsNil() && next.IsNil() {
  26.         list.head = nil
  27.         list.tail = nil
  28.     } else if pre.IsNil() {
  29.         // 表示移除的是头部节点，那么下一个节点成为头节点
  30.         list.head = next
  31.         next.pre = nil
  32.     } else if next.IsNil() {
  33.         // 表示移除的是尾部节点，那么上一个节点成为尾节点
  34.         list.tail = pre
  35.         pre.next = nil
  36.     } else {
  37.         // 移除的是中间节点
  38.         pre.next = next
  39.         next.pre = pre
  40.     }
  42.     // 节点减一
  43.     list.len = list.len - 1
  44.     return node
  45. }

操作和从头部移除节点相似，请自行分析。

2.8.完整例子

  1. package main
  3. import (
  4.     "fmt"
  5.     "sync"
  6. )
  8. // DoubleList 双端列表，双端队列
  9. type DoubleList struct {
  10.     head *ListNode  // 指向链表头部
  11.     tail *ListNode  // 指向链表尾部
  12.     len  int        // 列表长度
  13.     lock sync.Mutex // 为了进行并发安全pop弹出操作
  14. }
  16. // ListNode 列表节点
  17. type ListNode struct {
  18.     pre   *ListNode // 前驱节点
  19.     next  *ListNode // 后驱节点
  20.     value string    // 值
  21. }
  23. // GetValue 获取节点值
  24. func (node *ListNode) GetValue() string {
  25.     return node.value
  26. }
  28. // GetPre 获取节点前驱节点
  29. func (node *ListNode) GetPre() *ListNode {
  30.     return node.pre
  31. }
  33. // GetNext 获取节点后驱节点
  34. func (node *ListNode) GetNext() *ListNode {
  35.     return node.next
  36. }
  38. // HashNext 是否存在后驱节点
  39. func (node *ListNode) HashNext() bool {
  40.     return node.pre != nil
  41. }
  43. // HashPre 是否存在前驱节点
  44. func (node *ListNode) HashPre() bool {
  45.     return node.next != nil
  46. }
  48. // IsNil 是否为空节点
  49. func (node *ListNode) IsNil() bool {
  50.     return node == nil
  51. }
  53. // Len 返回列表长度
  54. func (list *DoubleList) Len() int {
  55.     return list.len
  56. }
  58. // AddNodeFromHead 从头部开始，添加节点到第N+1个元素之前，N=0表示添加到第一个元素之前，表示新节点成为新的头部，N=1表示添加到第二个元素之前，以此类推
  59. func (list *DoubleList) AddNodeFromHead(n int, v string) {
  60.     // 加并发锁
  61.     list.lock.Lock()
  62.     defer list.lock.Unlock()
  64.     // 如果索引超过或等于列表长度，一定找不到，直接panic
  65.     if n != 0 && n >= list.len {
  66.         panic("index out")
  67.     }
  69.     // 先找出头部
  70.     node := list.head
  72.     // 往后遍历拿到第 N+1 个位置的元素
  73.     for i := 1; i <= n; i++ {
  74.         node = node.next
  75.     }
  77.     // 新节点
  78.     newNode := new(ListNode)
  79.     newNode.value = v
  81.     // 如果定位到的节点为空，表示列表为空，将新节点设置为新头部和新尾部
  82.     if node.IsNil() {
  83.         list.head = newNode
  84.         list.tail = newNode
  85.     } else {
  86.         // 定位到的节点，它的前驱
  87.         pre := node.pre
  89.         // 如果定位到的节点前驱为nil，那么定位到的节点为链表头部，需要换头部
  90.         if pre.IsNil() {
  91.             // 将新节点链接在老头部之前
  92.             newNode.next = node
  93.             node.pre = newNode
  94.             // 新节点成为头部
  95.             list.head = newNode
  96.         } else {
  97.             // 将新节点插入到定位到的节点之前
  98.             // 定位到的节点的前驱节点 pre 现在链接到新节点前
  99.             pre.next = newNode
  100.             newNode.pre = pre
  102.             // 定位到的节点链接到新节点之后
  103.             newNode.next = node
  104.             node.pre = newNode
  105.         }
  107.     }
  109.     // 列表长度+1
  110.     list.len = list.len + 1
  111. }
  113. // AddNodeFromTail 从尾部开始，添加节点到第N+1个元素之后，N=0表示添加到第一个元素之后，表示新节点成为新的尾部，N=1表示添加到第二个元素之后，以此类推
  114. func (list *DoubleList) AddNodeFromTail(n int, v string) {
  115.     // 加并发锁
  116.     list.lock.Lock()
  117.     defer list.lock.Unlock()
  119.     // 如果索引超过或等于列表长度，一定找不到，直接panic
  120.     if n != 0 && n >= list.len {
  121.         panic("index out")
  122.     }
  124.     // 先找出尾部
  125.     node := list.tail
  127.     // 往前遍历拿到第 N+1 个位置的元素
  128.     for i := 1; i <= n; i++ {
  129.         node = node.pre
  130.     }
  132.     // 新节点
  133.     newNode := new(ListNode)
  134.     newNode.value = v
  136.     // 如果定位到的节点为空，表示列表为空，将新节点设置为新头部和新尾部
  137.     if node.IsNil() {
  138.         list.head = newNode
  139.         list.tail = newNode
  140.     } else {
  141.         // 定位到的节点，它的后驱
  142.         next := node.next
  144.         // 如果定位到的节点后驱为nil，那么定位到的节点为链表尾部，需要换尾部
  145.         if next.IsNil() {
  146.             // 将新节点链接在老尾部之后
  147.             node.next = newNode
  148.             newNode.pre = node
  150.             // 新节点成为尾部
  151.             list.tail = newNode
  152.         } else {
  153.             // 将新节点插入到定位到的节点之后
  154.             // 新节点链接到定位到的节点之后
  155.             newNode.pre = node
  156.             node.next = newNode
  158.             // 定位到的节点的后驱节点链接在新节点之后
  159.             newNode.next = next
  160.             next.pre = newNode
  162.         }
  164.     }
  166.     // 列表长度+1
  167.     list.len = list.len + 1
  168. }
  170. // First 返回列表链表头结点
  171. func (list *DoubleList) First() *ListNode {
  172.     return list.head
  173. }
  175. // Last 返回列表链表尾结点
  176. func (list *DoubleList) Last() *ListNode {
  177.     return list.tail
  178. }
  180. // IndexFromHead 从头部开始往后找，获取第N+1个位置的节点，索引从0开始。
  181. func (list *DoubleList) IndexFromHead(n int) *ListNode {
  182.     // 索引超过或等于列表长度，一定找不到，返回空指针
  183.     if n >= list.len {
  184.         return nil
  185.     }
  187.     // 获取头部节点
  188.     node := list.head
  190.     // 往后遍历拿到第 N+1 个位置的元素
  191.     for i := 1; i <= n; i++ {
  192.         node = node.next
  193.     }
  195.     return node
  196. }
  198. // IndexFromTail 从尾部开始往前找，获取第N+1个位置的节点，索引从0开始。
  199. func (list *DoubleList) IndexFromTail(n int) *ListNode {
  200.     // 索引超过或等于列表长度，一定找不到，返回空指针
  201.     if n >= list.len {
  202.         return nil
  203.     }
  205.     // 获取尾部节点
  206.     node := list.tail
  208.     // 往前遍历拿到第 N+1 个位置的元素
  209.     for i := 1; i <= n; i++ {
  210.         node = node.pre
  211.     }
  213.     return node
  214. }
  216. // PopFromHead 从头部开始往后找，获取第N+1个位置的节点，并移除返回
  217. func (list *DoubleList) PopFromHead(n int) *ListNode {
  218.     // 加并发锁
  219.     list.lock.Lock()
  220.     defer list.lock.Unlock()
  222.     // 索引超过或等于列表长度，一定找不到，返回空指针
  223.     if n >= list.len {
  224.         return nil
  225.     }
  227.     // 获取头部
  228.     node := list.head
  230.     // 往后遍历拿到第 N+1 个位置的元素
  231.     for i := 1; i <= n; i++ {
  232.         node = node.next
  233.     }
  235.     // 移除的节点的前驱和后驱
  236.     pre := node.pre
  237.     next := node.next
  239.     // 如果前驱和后驱都为nil，那么移除的节点为链表唯一节点
  240.     if pre.IsNil() && next.IsNil() {
  241.         list.head = nil
  242.         list.tail = nil
  243.     } else if pre.IsNil() {
  244.         // 表示移除的是头部节点，那么下一个节点成为头节点
  245.         list.head = next
  246.         next.pre = nil
  247.     } else if next.IsNil() {
  248.         // 表示移除的是尾部节点，那么上一个节点成为尾节点
  249.         list.tail = pre
  250.         pre.next = nil
  251.     } else {
  252.         // 移除的是中间节点
  253.         pre.next = next
  254.         next.pre = pre
  255.     }
  257.     // 节点减一
  258.     list.len = list.len - 1
  259.     return node
  260. }
  262. // PopFromTail 从尾部开始往前找，获取第N+1个位置的节点，并移除返回
  263. func (list *DoubleList) PopFromTail(n int) *ListNode {
  264.     // 加并发锁
  265.     list.lock.Lock()
  266.     defer list.lock.Unlock()
  268.     // 索引超过或等于列表长度，一定找不到，返回空指针
  269.     if n >= list.len {
  270.         return nil
  271.     }
  273.     // 获取尾部
  274.     node := list.tail
  276.     // 往前遍历拿到第 N+1 个位置的元素
  277.     for i := 1; i <= n; i++ {
  278.         node = node.pre
  279.     }
  281.     // 移除的节点的前驱和后驱
  282.     pre := node.pre
  283.     next := node.next
  285.     // 如果前驱和后驱都为nil，那么移除的节点为链表唯一节点
  286.     if pre.IsNil() && next.IsNil() {
  287.         list.head = nil
  288.         list.tail = nil
  289.     } else if pre.IsNil() {
  290.         // 表示移除的是头部节点，那么下一个节点成为头节点
  291.         list.head = next
  292.         next.pre = nil
  293.     } else if next.IsNil() {
  294.         // 表示移除的是尾部节点，那么上一个节点成为尾节点
  295.         list.tail = pre
  296.         pre.next = nil
  297.     } else {
  298.         // 移除的是中间节点
  299.         pre.next = next
  300.         next.pre = pre
  301.     }
  303.     // 节点减一
  304.     list.len = list.len - 1
  305.     return node
  306. }
  308. func main() {
  309.     list := new(DoubleList)
  311.     // 在列表头部插入新元素
  312.     list.AddNodeFromHead(0, "I")
  313.     list.AddNodeFromHead(0, "love")
  314.     list.AddNodeFromHead(0, "you")
  315.     // 在列表尾部插入新元素
  316.     list.AddNodeFromTail(0, "may")
  317.     list.AddNodeFromTail(0, "happy")
  319.     list.AddNodeFromTail(list.Len()-1, "begin second")
  320.     list.AddNodeFromHead(list.Len()-1, "end second")
  322.     // 正常遍历，比较慢，因为内部会遍历拿到值返回
  323.     for i := 0; i < list.Len(); i++ {
  324.         // 从头部开始索引
  325.         node := list.IndexFromHead(i)
  327.         // 节点为空不可能，因为list.Len()使得索引不会越界
  328.         if !node.IsNil() {
  329.             fmt.Println(node.GetValue())
  330.         }
  331.     }
  333.     fmt.Println("----------")
  335.     // 正常遍历，特别快，因为直接拿到的链表节点
  336.     // 先取出第一个元素
  337.     first := list.First()
  338.     for !first.IsNil() {
  339.         // 如果非空就一直遍历
  340.         fmt.Println(first.GetValue())
  341.         // 接着下一个节点
  342.         first = first.GetNext()
  343.     }
  345.     fmt.Println("----------")
  347.     // 元素一个个 POP 出来
  348.     for {
  349.         node := list.PopFromHead(0)
  350.         if node.IsNil() {
  351.             // 没有元素了，直接返回
  352.             break
  353.         }
  354.         fmt.Println(node.GetValue())
  355.     }
  357.     fmt.Println("----------")
  358.     fmt.Println("len", list.Len())
  359. }

输出：

  1. you
  2. begin second
  3. love
  4. I
  5. may
  6. end second
  7. happy
  8. ----------
  9. you
  10. begin second
  11. love
  12. I
  13. may
  14. end second
  15. happy
  16. ----------
  17. you
  18. begin second
  19. love
  20. I
  21. may
  22. end second
  23. happy
  24. ----------
  25. len 0

首先，先从列表头部插入三个新元素，然后从尾部插入两个新元素，再往头部和尾部插入两个新元素：

  1.     list := new(DoubleList)
  3.     // 在列表头部插入新元素
  4.     list.AddNodeFromHead(0, "I")
  5.     list.AddNodeFromHead(0, "love")
  6.     list.AddNodeFromHead(0, "you")
  7.     // 在列表尾部插入新元素
  8.     list.AddNodeFromTail(0, "may")
  9.     list.AddNodeFromTail(0, "happy")
  11.     list.AddNodeFromTail(list.Len()-1, "begin second")
  12.     list.AddNodeFromHead(list.Len()-1, "end second")

最后用三种方式进行遍历，前两种仅仅是查看元素，后一种是 PopFromHead 遍历后移除元素。

附录

代码下载： https://github.com/hunterhug/goa.c/blob/master/code/double_list/double_list.go 。