双向循环链表的实现

package main

import "fmt"

// Node 节点结构体
type Node struct {
   data string // 节点数据
   prev *Node  // 前驱节点指针
   next *Node  // 后继节点指针
}

// DoublyLinkedList 双向循环链表结构体
type DoublyLinkedList struct {
   head *Node // 头节点指针
   tail *Node // 尾节点指针
}

// InsertAtHead
// @description 在双向循环链表的头节点插入新节点
// @param data string 新节点数据
func (dll *DoublyLinkedList) InsertAtHead(data string) {
   node := &Node{data: data} // 被插入的新节点

   if dll.head == nil {
      // 如果头节点为nil说明为空链表，被插入的新节点既是头节点也是尾节点
      dll.head = node
      dll.tail = node
      node.next = node
      node.prev = node
   } else {
      // ========== 在头节点插入（被插入节点将成为新的头节点） ========== //
      //   ↓←←←←←↑
      //   ↓          ↑
      // 节点5(新)     ↑
      //   ↓          ↑
      // 节点0(头)     ↑
      //   ↓          ↑
      // 节点1         ↑
      //   ↓          ↑
      // 节点2         ↑
      //   ↓          ↑
      // 节点3         ↑
      //   ↓          ↑
      // 节点4(尾)     ↑
      //   ↓          ↑
      //   ↓→→→→→↑
      node.prev = dll.tail // 新节点前驱指针 指向 尾节点
      node.next = dll.head // 新节点后继指针 指向 头节点
      dll.head.prev = node // 头节点前驱指针 指向 新节点
      dll.tail.next = node // 尾节点后继指针 指向 新节点
      dll.head = node      // 被插入的节点成为新的头节点
   }
}

// InsertAtTail
// @description 在双向循环链表的尾节点插入新节点
// @param data string 新节点数据
func (dll *DoublyLinkedList) InsertAtTail(data string) {
   node := &Node{data: data} // 被插入的新节点

   if dll.head == nil {
      // 如果头节点为nil说明为空链表，被插入的新节点既是头节点也是尾节点
      dll.head = node
      dll.tail = node
      node.next = node
      node.prev = node
   } else {
      // ========== 在尾节点插入（被插入节点将成为新的尾节点） ========== //
      //   ↓←←←←←↑
      //   ↓          ↑
      // 节点0(头)     ↑
      //   ↓          ↑
      // 节点1         ↑
      //   ↓          ↑
      // 节点2         ↑
      //   ↓          ↑
      // 节点3         ↑
      //   ↓          ↑
      // 节点4(尾)     ↑
      //   ↓          ↑
      // 节点5(新)     ↑
      //   ↓          ↑
      //   ↓→→→→→↑
      node.prev = dll.tail // 新节点前驱指针 指向 尾节点
      node.next = dll.head // 新节点后继指针 指向 头节点
      dll.head.prev = node // 头节点前驱指针 指向 新节点
      dll.tail.next = node // 尾节点后继指针 指向 新节点
      dll.tail = node      // 被插入的节点成为新的尾节点
   }
}

// Iterator
// @description 遍历双向循环链表
func (dll *DoublyLinkedList) Iterator() {
   // 获取头节点，从头节点开始遍历链表
   node := dll.head
   for node != nil {
      fmt.Printf("%s ", node.data)

      node = node.next // 获取下一个节点

      // 检查下一个节点是否为头节点，若为头节点说明已经遍历一圈可以终止循环
      if node == dll.head {
         break
      }
   }

   fmt.Println()
}

func main() {
   dll := &DoublyLinkedList{}

   dll.InsertAtTail("张三")
   dll.Iterator() // 张三

   dll.InsertAtTail("李四")
   dll.Iterator() // 张三 李四

   dll.InsertAtTail("王五")
   dll.Iterator() // 张三 李四 王五

   dll.InsertAtHead("陈二")
   dll.Iterator() // 陈二 张三 李四 王五

   dll.InsertAtHead("刘一")
   dll.Iterator() // 刘一 陈二 张三 李四 王五
}

package main

import (
   "container/list"
   "fmt"
)

// Iterator
// @description 遍历双向循环链表
// @param l *list.List 双向循环链表
func Iterator(l *list.List) {
   for element := l.Front(); element != nil; element = element.Next() {
      fmt.Printf("%s ", element.Value)
   }

   fmt.Println()
}

func main() {
   l := list.New() // 创建双向循环链表

   element3 := l.PushBack("张三")
   Iterator(l) // 张三

   l.PushBack("李四")
   Iterator(l) // 张三 李四

   l.PushBack("王五")
   Iterator(l) // 张三 李四 王五

   l.PushFront("陈二")
   Iterator(l) // 陈二 张三 李四 王五

   l.PushFront("刘一")
   Iterator(l) // 刘一 陈二 张三 李四 王五

   l.Remove(element3)
   Iterator(l) // 刘一 陈二 李四 王五
}