Go 链表详解

初始化

在 Go 语言中，container/list 包提供了对双向链表的支持。我可以通过以下几种方式来初始化一个链表：

package main

import (
	"container/list"
)

func main() {
	// 方法一：直接声明一个链表变量
	var linkedList list.List

	// 方法二：使用 new 函数并调用 Init 方法
	linkedList2 := new(list.List).Init()

	// 方法三：使用 list 包的 New 函数
	linkedList3 := list.New()
}

链表的结构

链表中的每个元素都是一个 Element 类型，其结构如下所示：

type Element struct {
	// Next 和 Prev 指向链表中下一个和上一个元素
	Next, Prev *Element

	// List 指向链表本身，用于维护链表结构
	List *List

	// Value 存储节点的实际值，类型为 interface{}
	Value interface{}
}

操作链表

我将演示如何对链表进行基本的操作。

package main

import (
	"container/list"
	"fmt"
)

func main() {
	var linkedList list.List

	// 在链表末尾添加元素 "go"
	linkedList.PushBack("go")

	// 在链表开头添加元素 "sumingcheng"
	linkedList.PushFront("sumingcheng")

	// 再次在链表末尾添加元素 "python"
	linkedList.PushBack("python")

	// 打印链表长度
	fmt.Println("链表长度", linkedList.Len())

	// 遍历并打印链表元素
	for element := linkedList.Front(); element != nil; element = element.Next() {
		fmt.Println(element.Value)
	}

	// 从后向前遍历并打印链表元素
	for element := linkedList.Back(); element != nil; element = element.Prev() {
		fmt.Println(element.Value)
	}

	// 获取并打印链表的第一个和最后一个元素
	fmt.Println("第一个元素", linkedList.Front().Value)
	fmt.Println("最后一个元素", linkedList.Back().Value)
}

链表的方法

链表提供了一些常用的方法：

方法	描述
PushBack(v interface) *Element	在链表末尾插入一个新元素，返回新元素的引用
PushFront(v interface) *Element	在链表开头插入一个新元素，返回新元素的引用
Front() *Element	返回链表的第一个元素，如果链表为空则返回 nil
Back() *Element	返回链表的最后一个元素，如果链表为空则返回 nil
Len() int	返回链表中元素的数量

链表的移动

我可以通过以下方式移动链表中的元素，例如将最后一个元素移动到链表的前面。

package main

import (
	"container/list"
	"fmt"
)

func moveLastToFront(ll *list.List) {
	if ll.Len() > 1 {
		lastElement := ll.Back()
		ll.MoveToFront(lastElement)
	}
}

func printList(ll *list.List) {
	for element := ll.Front(); element != nil; element = element.Next() {
		fmt.Println(element.Value)
	}
}

func main() {
	linkedList := list.New()
	linkedList.PushBack("sumingcheng")
	linkedList.PushBack("go")
	linkedList.PushBack("python")

	moveLastToFront(linkedList)
	printList(linkedList)
}

链表的追加

我可以向链表中添加元素：

package main

import (
	"container/list"
)

func main() {
	linkedList := list.New()
	linkedList.PushBack(1)
	linkedList.PushBack(2)
	linkedList.PushBack(3)
}

两个链表的连接

可以将一个链表追加到另一个链表的末尾：

package main

import (
	"container/list"
)

func linkListsDirectly(l1, l2 *list.List) {
	if l2.Len() > 0 {
		l1.PushBackList(l2)
	}
}

func main() {
	list1 := list.New()
	list1.PushBack(1)
	list1.PushBack(2)
	list1.PushBack(3)

	list2 := list.New()
	list2.PushBack(4)
	list2.PushBack(5)
	list2.PushBack(6)

	linkListsDirectly(list1, list2)
}

链表的删除

当我需要删除链表中的某个元素时，需要注意以下几点。

当删除链表的一个元素时，该元素被移除，无法再通过该元素访问链表的其他部分。为了安全地继续遍历，需要在删除元素之前获取下一个元素的引用。

func removeElements(ll *list.List, value interface{}) {
	for element := ll.Front(); element != nil; {
		next := element.Next() // 保存下一个元素的引用
		if element.Value == value {
			ll.Remove(element) // 删除当前元素
		}
		element = next // 移动到下一个元素
	}
}

链表的修改

我可以遍历链表，修改特定元素的值：

func updateElements(ll *list.List, oldValue, newValue interface{}) {
	for element := ll.Front(); element != nil; element = element.Next() {
		if element.Value == oldValue {
			element.Value = newValue
		}
	}
}

链表的反转

以下函数可以实现链表的反转。

func reverseList(ll *list.List) *list.List {
	reversed := list.New()
	for element := ll.Front(); element != nil; {
		next := element.Next()              // 保存下一个元素的引用
		ll.Remove(element)                  // 从原链表中移除当前元素
		reversed.PushFront(element.Value)   // 将元素添加到新链表的前端
		element = next
	}
	return reversed
}

注意 📝 当操作链表时，务必注意元素的引用和链表的结构，以避免意外的错误。