go container/list 双向链表

笔记算法刷题 Go

Go container/list 包的方法一览 📜🛠️

太棒了！了解一个库有哪些方法是掌握它如何使用的关键一步。container/list 包为我们提供了一系列操作双向链表的方法。下面，我将这些方法分类并详细列出，希望能帮助您更清晰地理解它们的作用：

`list.List` 类型的方法

container/list 包的核心是 List 类型，它代表了一个双向链表。所有操作链表的方法都是 List 类型的方法（method）。

1. 链表初始化与创建

func New() *List
- 描述：创建一个新的、空的 List（链表）。这是创建 List 实例的推荐方式。
- 返回：一个指向新创建的 List 结构的指针。
func (l *List) Init() *List
- 描述：初始化或重新初始化链表 l。将链表清空并使其准备好再次使用。如果 l 为 nil，Init 会创建一个新的链表并返回。
- 返回：链表 l 本身（经过初始化后）。
- 注意：通常我们直接使用 list.New() 来创建新链表。Init() 更多用于重置一个已存在的链表。

2. 获取链表信息

func (l *List) Len() int
- 描述：返回链表中元素的数量。
- 返回：链表的当前长度（整型）。

3. 元素添加

这些方法都会返回一个 *list.Element 指针，代表新添加的元素。*list.Element 是链表中的一个节点，它包含 Value 字段（存储数据）、Next() 和 Prev() 方法（用于遍历）。

func (l *List) PushFront(v interface{}) *Element
- 描述：在链表 l 的头部（最前面）添加一个值为 v 的元素。
- 参数：v，要添加的值，可以是任何类型（interface{}）。
- 返回：新创建的 *Element。
func (l *List) PushBack(v interface{}) *Element
- 描述：在链表 l 的尾部（最后面）添加一个值为 v 的元素。
- 参数：v，要添加的值。
- 返回：新创建的 *Element。
func (l *List) InsertBefore(v interface{}, mark *Element) *Element
- 描述：在链表 l 中，指定元素 mark 的前面插入一个值为 v 的新元素。mark 必须是链表 l 中的一个有效元素。
- 参数：
  - v：要插入的值。
  - mark：作为参照的链表元素。
- 返回：新创建的 *Element。
func (l *List) InsertAfter(v interface{}, mark *Element) *Element
- 描述：在链表 l 中，指定元素 mark 的后面插入一个值为 v 的新元素。mark 必须是链表 l 中的一个有效元素。
- 参数：
  - v：要插入的值。
  - mark：作为参照的链表元素。
- 返回：新创建的 *Element。

4. 元素移除

func (l *List) Remove(e *Element) interface{}
- 描述：从链表 l 中移除指定的元素 e。e 必须是链表 l 中的一个有效元素。
- 参数：e，要移除的链表元素。
- 返回：被移除元素的值。

5. 元素访问（不移除）

func (l *List) Front() *Element
- 描述：返回链表的头部元素。
- 返回：如果链表为空，则返回 nil；否则返回第一个 *Element。
func (l *List) Back() *Element
- 描述：返回链表的尾部元素。
- 返回：如果链表为空，则返回 nil；否则返回最后一个 *Element。

6. 元素移动

这些方法用于改变链表中现有元素的相对位置。

func (l *List) MoveToFront(e *Element)
- 描述：将链表 l 中的元素 e 移动到链表的头部。e 必须是链表 l 中的一个有效元素。
func (l *List) MoveToBack(e *Element)
- 描述：将链表 l 中的元素 e 移动到链表的尾部。e 必须是链表 l 中的一个有效元素。
func (l *List) MoveBefore(e, mark *Element)
- 描述：将链表 l 中的元素 e 移动到另一个元素 mark 的前面。e 和 mark 都必须是链表 l 中的有效元素。如果 e 或 mark 为 nil，或者 e 等于 mark，此操作不执行任何操作。
func (l *List) MoveAfter(e, mark *Element)
- 描述：将链表 l 中的元素 e 移动到另一个元素 mark 的后面。e 和 mark 都必须是链表 l 中的有效元素。如果 e 或 mark 为 nil，或者 e 等于 mark，此操作不执行任何操作。

7. 链表合并

func (l *List) PushBackList(other *List)
- 描述：将另一个链表 other 中的所有元素（按顺序）追加到链表 l 的尾部。操作后 other 链表将变为空。
- 参数：other，要合并到 l 后面的链表。
func (l *List) PushFrontList(other *List)
- 描述：将另一个链表 other 中的所有元素（按顺序）插入到链表 l 的头部。操作后 other 链表将变为空。
- 参数：other，要合并到 l 前面的链表。

`list.Element` 类型的方法和字段

除了 List 类型的方法外，container/list 还定义了 Element 类型，代表链表中的一个节点。

type Element struct
- Value interface{}：这是一个公共字段，存储了该节点实际的值。您可以直接访问 element.Value 来获取节点存储的数据。
- func (e *Element) Next() *Element：
  - 描述：返回当前元素的下一个元素。
  - 返回：如果当前元素是链表的最后一个元素，或者 e 为 nil，则返回 nil；否则返回下一个 *Element。
- func (e *Element) Prev() *Element：
  - 描述：返回当前元素的上一个元素。
  - 返回：如果当前元素是链表的第一个元素，或者 e 为 nil，则返回 nil；否则返回上一个 *Element。

总结

container/list 提供了一整套丰富且高效的方法来操作双向链表，包括元素的增、删、改、查、移动以及链表之间的合并。理解这些方法签名和它们的作用，就能灵活地利用这个包来实现各种需要链表数据结构的应用。

list.Element 详解 🧩🔗

好的，我们来深入了解一下 container/list 包中的核心构件之一：list.Element。

在 container/list 构建的双向链表中，List 本身只像是一个“骨架”或者说“容器”，它维护着链表的头部和尾部。而真正存储数据、构成链表“肉身”的，就是一个个 list.Element 结构体。

`list.Element` 是什么？

list.Element 代表了链表中的一个节点 (node)。您可以把它想象成火车上的一节节车厢。每一节车厢（Element）都装载着乘客（Value），并且通过连接器（内部指针）与前一节和后一节车厢连接起来。

`list.Element` 的内部结构 (您能直接访问的部分)

list.Element 是一个结构体，它最重要的一个字段是：

Value interface{}
- 作用：这是 list.Element 真正存储数据的地方。interface{} 表示它可以存储任何类型的数据。这意味着您可以往链表中放入整数、字符串、自定义结构体等等。
- 如何访问：当您从链表中获取到一个 *list.Element 指针时，可以直接通过 .Value 字段来获取它所存储的数据。例如：myElement.Value。
- 类型断言：由于 Value 是 interface{}, 当您取出它时，通常需要进行类型断言（Type Assertion）来将其转换回原始类型，以便进行具体操作。
```
// 假设 element 存储了一个字符串
strVal := element.Value.(string) // 类型断言：将 interface{} 转换为 string
fmt.Println(strVal)
```
或者，如果您存储的是一个自定义结构体：
```
type Person struct {
    Name string
    Age  int
}
// ...
// 假设 element 存储了一个 Person 结构体
personVal := element.Value.(Person) // 类型断言：将 interface{} 转换为 Person
fmt.Printf("Name: %s, Age: %d\n", personVal.Name, personVal.Age)
```

`list.Element` 的核心方法 (用于遍历)

虽然 list.Element 内部也维护着指向前后节点的指针，但这些指针是包私有的，我们无法直接访问。container/list 包提供了两个方法来安全地遍历链表：

func (e *Element) Next() *Element
- 作用：返回当前 Element 的下一个元素。这是您向链表尾部（从前到后）遍历的关键。
- 返回值：如果当前 Element 是链表的最后一个元素，或者 e 本身是 nil，它将返回 nil。否则，它会返回下一个 *list.Element 指针。
func (e *Element) Prev() *Element
- 作用：返回当前 Element 的上一个元素。这是您向链表头部（从后到前）遍历的关键。
- 返回值：如果当前 Element 是链表的第一个元素，或者 e 本身是 nil，它将返回 nil。否则，它会返回上一个 *list.Element 指针。

为什么需要 `list.Element`？

解耦数据与结构：Element 将实际存储的数据 (Value) 与链表结构本身（如何连接前后节点）解耦。这意味着您可以存储任何数据类型，而无需改变链表的底层实现。
高效插入与删除：因为 PushFront、PushBack、InsertBefore、InsertAfter 等操作返回的是 *list.Element，并且 Remove 方法也接受 *list.Element 作为参数。这使得在已知某个节点（Element）的情况下，在其前后插入或删除操作都非常高效 (O(1) 时间复杂度)，因为您不需要遍历整个链表去查找位置。
遍历能力：Next() 和 Prev() 方法使得您可以轻松地从链表的任何一点开始，向前或向后遍历整个链表。

示例：如何使用 `list.Element`

package main

import (
	"container/list"
	"fmt"
)

func main() {
	l := list.New() // 创建一个新的链表

	// 添加一些元素
	l.PushBack("Hello")
	l.PushFront(123)
	l.PushBack(3.14)

	// 获取头部元素
	frontElement := l.Front()
	if frontElement != nil {
		fmt.Printf("头部元素的值: %v (类型: %T)\n", frontElement.Value, frontElement.Value)
		// 如果我们知道它是 int，可以进行类型断言
		if val, ok := frontElement.Value.(int); ok {
			fmt.Printf("  类型断言为 int: %d\n", val)
		}
	}

	// 获取尾部元素
	backElement := l.Back()
	if backElement != nil {
		fmt.Printf("尾部元素的值: %v (类型: %T)\n", backElement.Value, backElement.Value)
		// 如果我们知道它是 float64，可以进行类型断言
		if val, ok := backElement.Value.(float64); ok {
			fmt.Printf("  类型断言为 float64: %.2f\n", val)
		}
	}

	fmt.Println("\n正向遍历链表:")
	// 正向遍历链表 (从头到尾)
	for e := l.Front(); e != nil; e = e.Next() {
		fmt.Printf("  元素值: %v\n", e.Value)
	}

	fmt.Println("\n反向遍历链表:")
	// 反向遍历链表 (从尾到头)
	for e := l.Back(); e != nil; e = e.Prev() {
		fmt.Printf("  元素值: %v\n", e.Value)
	}

	// 移除一个元素
	// 首先找到我们想移除的元素（例如，找到值为 "Hello" 的元素）
	var helloElement *list.Element
	for e := l.Front(); e != nil; e = e.Next() {
		if e.Value == "Hello" {
			helloElement = e
			break
		}
	}

	if helloElement != nil {
		removedValue := l.Remove(helloElement)
		fmt.Printf("\n移除了元素: %v\n", removedValue)
	}

	fmt.Println("移除后的链表:")
	for e := l.Front(); e != nil; e = e.Next() {
		fmt.Printf("  元素值: %v\n", e.Value)
	}
}

通过 list.Element，我们可以直接操作链表中的各个节点，实现数据的存储、访问和高效的增删改查。

如果觉得文章对你有用，请随意赞赏

go container/list 双向链表

list.List 类型的方法