学习 Go 语言数据结构：实现双链表（下）

扩展功能

可以为双链表扩展其他功能，读者可以思考如何实现

链表长度

func size(head *Node) int {
  if head == nil {
    fmt.Println("-> Empty list!")
    return 0
  }
  count := 0
  for head != nil {
    count++
    head = head.Next
  }
  return count
}

运行程序：

$ go run main.go
1 <-> 2 <-> 3 <-> 4 <-> 5 
双链表的长度:  5

插入

一个新节点可以很容易地插入到双向链表中。我们只需要设置指针 prev_node 和 next_node 小心地将 prev_node 和 next_node 节点与适当的指针链接起来。

如果要在节点 n1 和 n3 之间插入节点 n2，则应将 n2 的指针 prev_node 设置为 n1，将 n2 的指针 next_node 设置为 n3。

双向链表中的插入可以通过多种方式完成：

1. 在节点之间插入
   
2. 在双链表开头插入
   
3. 插入一个空链表
   
4. 在双链表末尾插入
   

删除

在双向链表中可以很容易地删除节点。我们只需要将指针 prev_node 和 next_node 逻辑设置为节点。可以通过以下方式删除节点：

1. 删除最后的节点
   
2. 删除第一个节点
   
3. 在节点之间删除
   

反转双链表

假设我们有四个节点 n1、n2、n3 和 n4

反转的步骤如下：

1. 指针 head 指向最后一个节点 n4
   
2. 由于 n4 现在是第一个节点，它的 prev_node 指针必须为 NULL
   
3. 节点 n1 是最后一个节点，因此它的 next_node 必须为 NULL
   
4. n4 的指针 next_node 指向 n3，n3 的 next_node 指向 n2，n2 的 next_node 指向 n1
   
5. n1 的指针 prev_node 指向 n2，n2 的 prev_node 指向 n3，n3 的 prev_node 指向 n4
   

总结

与单链表相比，双链表具有多样性，可以从任何方向遍历双向链表，从而更方便的插入和删除元素。

但是为了维护每个节点的指针，会多一些额外的开销。