一、列表 List

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

列表 List:存放数据,数据按顺序排列,可以依次入队和出队,有序号关系,可以取出某序号的数据。先进先出的 队列 (queue) 和先进后出的 栈(stack) 都是列表。大家也经常听说一种叫 线性表 的数据结构,表示具有相同特性的数据元素的有限序列,实际上就是 列表 的同义词。

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

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

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

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

我们在前面已经实现过这两种表示的数据结构:先进先出的 队列 (queue) 和先进后出的 栈(stack)。接下来我们会来实现链表形式的双端列表,也叫双端队列,这个数据结构应用场景更广泛一点。在实际工程应用上,缓存数据库 Redis列表List 基本类型就是用它来实现的。

二、实现双端列表

双端列表,也可以叫双端队列

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

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

设计结构体 DoubleList 指向队列头部 head 和尾部 tail 的指针字段,方便找到链表最前和最后的节点,并且链表节点之间是双向链接的,链表的第一个元素的前驱节点为 nil,最后一个元素的后驱节点也为 nil。如图:

列表 - 图1

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

2.1.列表节点普通操作

  1. // 获取节点值
  2. func (node *ListNode) GetValue() string {
  3. return node.value
  4. }
  5. // 获取节点前驱节点
  6. func (node *ListNode) GetPre() *ListNode {
  7. return node.pre
  8. }
  9. // 获取节点后驱节点
  10. func (node *ListNode) GetNext() *ListNode {
  11. return node.next
  12. }
  13. // 是否存在后驱节点
  14. func (node *ListNode) HashNext() bool {
  15. return node.pre != nil
  16. }
  17. // 是否存在前驱节点
  18. func (node *ListNode) HashPre() bool {
  19. return node.next != nil
  20. }
  21. // 是否为空节点
  22. func (node *ListNode) IsNil() bool {
  23. return node == nil
  24. }

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

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

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

首先加锁实现并发安全。然后判断索引是否超出列表长度:

  1. // 索引超过列表长度,一定找不到,panic
  2. if n > list.len {
  3. panic("index out")
  4. }

如果 n=0 表示新节点想成为新的链表头部,n=1 表示插入到链表头部数起第二个节点之前,新节点成为第二个节点,以此类推。

首先,找出头部:node := list.head,然后往后面遍历,定位到索引指定的节点 node

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

接着初始化新节点:newNode := new(ListNode)

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

列表 - 图2

判断定位到的节点 node 是否为空,如果为空,表明列表没有元素,将新节点设置为新头部和新尾部。

否则找到定位到的节点的前驱节点:pre := node.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
  4. // 定位到的节点链接到新节点之后
  5. newNode.next = node
  6. node.pre = newNode

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

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

最后,链表长度加一。

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

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

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

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

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

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

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

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

时间复杂度为:O(n)

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

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

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

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

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

首先加并发锁实现并发安全。先判断索引是否超出列表长度:n >= list.len,如果超出直接返回空指针。

获取头部,然后遍历定位到第 N+1 个位置的元素:node = node.next

定位到的并要移除的节点有三种情况发生:

列表 - 图3

查看要移除的节点的前驱和后驱:

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

如果前驱和后驱都为空:pre.IsNil() && next.IsNil(),那么要移除的节点是链表中唯一的节点,直接将列表头部和尾部置空即可。

如果前驱节点为空: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

最后,列表长度减一。

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

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

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

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

2.8.完整例子

  1. package main
  2. import (
  3. "fmt"
  4. "sync"
  5. )
  6. // 双端列表,双端队列
  7. type DoubleList struct {
  8. head *ListNode // 指向链表头部
  9. tail *ListNode // 指向链表尾部
  10. len int // 列表长度
  11. lock sync.Mutex // 为了进行并发安全pop操作
  12. }
  13. // 列表节点
  14. type ListNode struct {
  15. pre *ListNode // 前驱节点
  16. next *ListNode // 后驱节点
  17. value string // 值
  18. }
  19. // 获取节点值
  20. func (node *ListNode) GetValue() string {
  21. return node.value
  22. }
  23. // 获取节点前驱节点
  24. func (node *ListNode) GetPre() *ListNode {
  25. return node.pre
  26. }
  27. // 获取节点后驱节点
  28. func (node *ListNode) GetNext() *ListNode {
  29. return node.next
  30. }
  31. // 是否存在后驱节点
  32. func (node *ListNode) HashNext() bool {
  33. return node.pre != nil
  34. }
  35. // 是否存在前驱节点
  36. func (node *ListNode) HashPre() bool {
  37. return node.next != nil
  38. }
  39. // 是否为空节点
  40. func (node *ListNode) IsNil() bool {
  41. return node == nil
  42. }
  43. // 返回列表长度
  44. func (list *DoubleList) Len() int {
  45. return list.len
  46. }
  47. // 添加节点到链表头部的第N个元素之前,N=0表示新节点成为新的头部
  48. func (list *DoubleList) AddNodeFromHead(n int, v string) {
  49. // 加并发锁
  50. list.lock.Lock()
  51. defer list.lock.Unlock()
  52. // 索引超过列表长度,一定找不到,panic
  53. if n > list.len {
  54. panic("index out")
  55. }
  56. // 先找出头部
  57. node := list.head
  58. // 往后遍历拿到第 N+1 个位置的元素
  59. for i := 1; i <= n; i++ {
  60. node = node.next
  61. }
  62. // 新节点
  63. newNode := new(ListNode)
  64. newNode.value = v
  65. // 如果定位到的节点为空,表示列表为空,将新节点设置为新头部和新尾部
  66. if node.IsNil() {
  67. list.head = newNode
  68. list.tail = newNode
  69. } else {
  70. // 定位到的节点,它的前驱
  71. pre := node.pre
  72. // 如果定位到的节点前驱为nil,那么定位到的节点为链表头部,需要换头部
  73. if pre.IsNil() {
  74. // 将新节点链接在老头部之前
  75. newNode.next = node
  76. node.pre = newNode
  77. // 新节点成为头部
  78. list.head = newNode
  79. } else {
  80. // 将新节点插入到定位到的节点之前
  81. // 定位到的节点的前驱节点 pre 现在链接到新节点前
  82. pre.next = newNode
  83. newNode.pre = pre
  84. // 定位到的节点链接到新节点之后
  85. newNode.next = node
  86. node.pre = newNode
  87. }
  88. }
  89. // 列表长度+1
  90. list.len = list.len + 1
  91. }
  92. // 添加节点到链表尾部的第N个元素之后,N=0表示新节点成为新的尾部
  93. func (list *DoubleList) AddNodeFromTail(n int, v string) {
  94. // 加并发锁
  95. list.lock.Lock()
  96. defer list.lock.Unlock()
  97. // 索引超过列表长度,一定找不到,panic
  98. if n > list.len {
  99. panic("index out")
  100. }
  101. // 先找出尾部
  102. node := list.tail
  103. // 往前遍历拿到第 N+1 个位置的元素
  104. for i := 1; i <= n; i++ {
  105. node = node.pre
  106. }
  107. // 新节点
  108. newNode := new(ListNode)
  109. newNode.value = v
  110. // 如果定位到的节点为空,表示列表为空,将新节点设置为新头部和新尾部
  111. if node.IsNil() {
  112. list.head = newNode
  113. list.tail = newNode
  114. } else {
  115. // 定位到的节点,它的后驱
  116. next := node.next
  117. // 如果定位到的节点后驱为nil,那么定位到的节点为链表尾部,需要换尾部
  118. if next.IsNil() {
  119. // 将新节点链接在老尾部之后
  120. node.next = newNode
  121. newNode.pre = node
  122. // 新节点成为尾部
  123. list.tail = newNode
  124. } else {
  125. // 将新节点插入到定位到的节点之后
  126. // 新节点链接到定位到的节点之后
  127. newNode.pre = node
  128. node.next = newNode
  129. // 定位到的节点的后驱节点链接在新节点之后
  130. newNode.next = next
  131. next.pre = newNode
  132. }
  133. }
  134. // 列表长度+1
  135. list.len = list.len + 1
  136. }
  137. // 返回列表链表头结点
  138. func (list *DoubleList) First() *ListNode {
  139. return list.head
  140. }
  141. // 返回列表链表尾结点
  142. func (list *DoubleList) Last() *ListNode {
  143. return list.tail
  144. }
  145. // 从头部开始往后找,获取第N+1个位置的节点,索引从0开始。
  146. func (list *DoubleList) IndexFromHead(n int) *ListNode {
  147. // 索引超过或等于列表长度,一定找不到,返回空指针
  148. if n >= list.len {
  149. return nil
  150. }
  151. // 获取头部节点
  152. node := list.head
  153. // 往后遍历拿到第 N+1 个位置的元素
  154. for i := 1; i <= n; i++ {
  155. node = node.next
  156. }
  157. return node
  158. }
  159. // 从尾部开始往前找,获取第N+1个位置的节点,索引从0开始。
  160. func (list *DoubleList) IndexFromTail(n int) *ListNode {
  161. // 索引超过或等于列表长度,一定找不到,返回空指针
  162. if n >= list.len {
  163. return nil
  164. }
  165. // 获取尾部节点
  166. node := list.tail
  167. // 往前遍历拿到第 N+1 个位置的元素
  168. for i := 1; i <= n; i++ {
  169. node = node.pre
  170. }
  171. return node
  172. }
  173. // 从头部开始往后找,获取第N+1个位置的节点,并移除返回
  174. func (list *DoubleList) PopFromHead(n int) *ListNode {
  175. // 加并发锁
  176. list.lock.Lock()
  177. defer list.lock.Unlock()
  178. // 索引超过或等于列表长度,一定找不到,返回空指针
  179. if n >= list.len {
  180. return nil
  181. }
  182. // 获取头部
  183. node := list.head
  184. // 往后遍历拿到第 N+1 个位置的元素
  185. for i := 1; i <= n; i++ {
  186. node = node.next
  187. }
  188. // 移除的节点的前驱和后驱
  189. pre := node.pre
  190. next := node.next
  191. // 如果前驱和后驱都为nil,那么移除的节点为链表唯一节点
  192. if pre.IsNil() && next.IsNil() {
  193. list.head = nil
  194. list.tail = nil
  195. } else if pre.IsNil() {
  196. // 表示移除的是头部节点,那么下一个节点成为头节点
  197. list.head = next
  198. next.pre = nil
  199. } else if next.IsNil() {
  200. // 表示移除的是尾部节点,那么上一个节点成为尾节点
  201. list.tail = pre
  202. pre.next = nil
  203. } else {
  204. // 移除的是中间节点
  205. pre.next = next
  206. next.pre = pre
  207. }
  208. // 节点减一
  209. list.len = list.len - 1
  210. return node
  211. }
  212. // 从尾部开始往前找,获取第N+1个位置的节点,并移除返回
  213. func (list *DoubleList) PopFromTail(n int) *ListNode {
  214. // 加并发锁
  215. list.lock.Lock()
  216. defer list.lock.Unlock()
  217. // 索引超过或等于列表长度,一定找不到,返回空指针
  218. if n >= list.len {
  219. return nil
  220. }
  221. // 获取尾部
  222. node := list.tail
  223. // 往前遍历拿到第 N+1 个位置的元素
  224. for i := 1; i <= n; i++ {
  225. node = node.pre
  226. }
  227. // 移除的节点的前驱和后驱
  228. pre := node.pre
  229. next := node.next
  230. // 如果前驱和后驱都为nil,那么移除的节点为链表唯一节点
  231. if pre.IsNil() && next.IsNil() {
  232. list.head = nil
  233. list.tail = nil
  234. } else if pre.IsNil() {
  235. // 表示移除的是头部节点,那么下一个节点成为头节点
  236. list.head = next
  237. next.pre = nil
  238. } else if next.IsNil() {
  239. // 表示移除的是尾部节点,那么上一个节点成为尾节点
  240. list.tail = pre
  241. pre.next = nil
  242. } else {
  243. // 移除的是中间节点
  244. pre.next = next
  245. next.pre = pre
  246. }
  247. // 节点减一
  248. list.len = list.len - 1
  249. return node
  250. }
  251. func main() {
  252. list := new(DoubleList)
  253. // 在列表头部插入新元素
  254. list.AddNodeFromHead(0, "I")
  255. list.AddNodeFromHead(0, "love")
  256. list.AddNodeFromHead(0, "you")
  257. // 在列表尾部插入新元素
  258. list.AddNodeFromTail(0, "may")
  259. list.AddNodeFromTail(0, "happy")
  260. // 正常遍历,比较慢
  261. for i := 0; i < list.Len(); i++ {
  262. // 从头部开始索引
  263. node := list.IndexFromHead(i)
  264. // 节点为空不可能,因为list.Len()使得索引不会越界
  265. if !node.IsNil() {
  266. fmt.Println(node.GetValue())
  267. }
  268. }
  269. fmt.Println("----------")
  270. // 正常遍历,特别快
  271. // 先取出第一个元素
  272. first := list.First()
  273. for !first.IsNil() {
  274. // 如果非空就一直遍历
  275. fmt.Println(first.GetValue())
  276. // 接着下一个节点
  277. first = first.GetNext()
  278. }
  279. fmt.Println("----------")
  280. // 元素一个个 POP 出来
  281. for {
  282. node := list.PopFromHead(0)
  283. if node.IsNil() {
  284. // 没有元素了,直接返回
  285. break
  286. }
  287. fmt.Println(node.GetValue())
  288. }
  289. fmt.Println("----------")
  290. fmt.Println("len", list.Len())
  291. }

输出:

  1. you
  2. love
  3. I
  4. may
  5. happy
  6. ----------
  7. you
  8. love
  9. I
  10. may
  11. happy
  12. ----------
  13. you
  14. love
  15. I
  16. may
  17. happy
  18. ----------
  19. len 0

首先,先从列表头部插入三个新元素,然后从尾部插入两个新元素,然后用三种方式进行遍历,两种只是查看元素,一种是遍历移除元素。