数据结构之链表
1. 簡介
鏈表（Linked List）是一種基本的數據結構，用于表示一組元素，這些元素按順序排列，每個元素都與下一個元素連接。與數組不同，鏈表的元素不是在內存中連續存儲的，而是通過指針來連接的。鏈表由節點（Node）組成，每個節點包含兩個主要部分：數據和指向下一個節點（或上一個節點，如果是雙向鏈表）的引用（指針）。鏈表可以分為單向鏈表、雙向鏈表和循環鏈表等不同類型。
以下是鏈表的主要特點和屬性：
特點和屬性：
- 有序集合： 鏈表中的元素是按順序排列的，每個元素都有一個位置。
- 節點包含數據： 每個節點包含數據（元素的值）。
- 節點之間通過引用連接： 鏈表中的節點通過指針或引用相互連接。單向鏈表只有一個指向下一個節點的引用，雙向鏈表有兩個引用，分別指向下一個節點和上一個節點。
- 靈活的大小： 鏈表的大小可以動態增長或縮小，而不需要提前指定大小。
- 插入和刪除元素高效： 插入和刪除元素通常是鏈表的強項，因為只需要更新指針，而不需要移動大量元素。
鏈表的常見操作包括：
- 插入（Insertion）： 在鏈表中插入一個新節點。
- 刪除（Deletion）： 從鏈表中刪除一個節點。
- 搜索（Search）： 查找鏈表中特定元素。
- 遍歷（Traversal）： 遍歷鏈表中的所有節點。
鏈表在許多編程場景中都有用，特別是在需要頻繁插入和刪除操作的情況下。它們通常比數組更靈活。然而，鏈表也有一些缺點，例如訪問元素需要從頭節點開始遍歷，因此在訪問元素方面效率較低。
2. 鏈表分類
常見的鏈表分類有：單向鏈表、雙向鏈表、循環鏈表、帶頭鏈表和跳表等，每種鏈表類型都適合不同的使用場景和問題。根據具體需求和性能要求，可以選擇適當類型的鏈表來解決問題。鏈表是計算機科學中常見的數據結構，對于處理動態數據集非常有用。
2.1 單向鏈表
單向鏈表（Singly Linked List）是一種鏈表數據結構，其中每個節點包含數據元素和一個指向下一個節點的引用。鏈表的頭節點用來表示鏈表的起始點，而尾節點的下一個節點通常為空（nil）。
以下是單向鏈表的主要特點和屬性：
特點和屬性：
- 每個節點包含兩個部分：數據元素和指向下一個節點的引用。
- 節點之間的連接是單向的，只能從頭節點開始遍歷鏈表。
- 插入和刪除節點操作在單向鏈表中非常高效，因為只需更新指針，而不需要移動大量元素。
- 鏈表的大小可以動態增長或縮小，不需要提前指定大小。
單向鏈表通常用于需要頻繁插入和刪除操作的情況，因為這些操作相對容易實現。然而，訪問鏈表中的特定元素需要從頭節點開始遍歷，效率較低。
下面是一個簡單的示例，展示了如何在Go語言中實現單向鏈表：
package main
import "fmt"
// 定義鏈表節點結構
type Node struct {
data int
next *Node
}
func main() {
// 創建鏈表頭節點
head := &Node{data: 1}
// 插入新節點到鏈表
newNode := &Node{data: 2}
head.next = newNode
// 遍歷鏈表并打印節點的數據
current := head
for current != nil {
fmt.Printf("%d -> ", current.data)
current = current.next
}
fmt.Println("nil")
}
在這個示例中，我們定義了一個Node結構來表示鏈表的節點，每個節點包含一個整數數據元素和一個指向下一個節點的引用。然后，我們創建一個鏈表頭節點，插入一個新節點，并遍歷鏈表并打印節點的數據。
這個示例只展示了鏈表的基本操作，包括創建、插入和遍歷。單向鏈表還支持其他操作，如刪除節點、查找節點等，具體操作可以根據需要自行擴展。
2.2 雙向鏈表
雙向鏈表（Doubly Linked List）是一種鏈表數據結構，其中每個節點包含數據元素、一個指向下一個節點的引用和一個指向前一個節點的引用。相對于單向鏈表，雙向鏈表提供了更多的靈活性，因為它可以在前向和后向兩個方向上遍歷鏈表。
以下是雙向鏈表的主要特點和屬性：
特點和屬性：
- 每個節點包含三個部分：數據元素、指向下一個節點的引用（通常稱為
next），和指向前一個節點的引用（通常稱為prev）。 - 節點之間的連接是雙向的，可以從頭節點向后遍歷，也可以從尾節點向前遍歷。
- 插入和刪除節點操作在雙向鏈表中仍然高效，因為只需更新相鄰節點的引用。
- 鏈表的大小可以動態增長或縮小，不需要提前指定大小。
雙向鏈表通常用于需要前向和后向遍歷的情況，或者在需要頻繁插入和刪除節點的情況下。相對于單向鏈表，雙向鏈表提供了更多的靈活性，但也需要額外的空間來存儲前向引用。
下面是一個簡單的示例，展示了如何在Go語言中實現雙向鏈表：
package main
import "fmt"
// 定義雙向鏈表節點結構
type Node struct {
data int
next *Node
prev *Node
}
func main() {
// 創建鏈表頭節點
head := &Node{data: 1}
tail := head
// 插入新節點到鏈表
newNode := &Node{data: 2, prev: tail}
tail.next = newNode
tail = newNode
// 遍歷鏈表并打印節點的數據（前向遍歷）
current := head
for current != nil {
fmt.Printf("%d -> ", current.data)
current = current.next
}
fmt.Println("nil")
// 遍歷鏈表并打印節點的數據（后向遍歷）
current = tail
for current != nil {
fmt.Printf("%d -> ", current.data)
current = current.prev
}
fmt.Println("nil")
}
在這個示例中，我們定義了一個Node結構來表示雙向鏈表的節點，每個節點包含一個整數數據元素、一個指向下一個節點的引用和一個指向前一個節點的引用。我們創建了鏈表的頭節點和尾節點，并插入一個新節點。然后，我們展示了如何在前向和后向兩個方向上遍歷鏈表并打印節點的數據。
雙向鏈表的實現可以根據需要進行擴展，包括插入、刪除、查找節點等操作。雙向鏈表的前向和后向遍歷功能增加了訪問靈活性，但也需要額外的內存來存儲前向引用。
2.3 循環鏈表
循環鏈表（Circular Linked List）是一種鏈表數據結構，與常規鏈表不同的是，循環鏈表的最后一個節點指向第一個節點，形成一個環狀結構。這意味著你可以無限地遍歷鏈表，因為在鏈表的末尾沒有終止標志，可以一直繞著環遍歷下去。
以下是循環鏈表的主要特點和屬性：
特點和屬性：
- 每個節點包含兩個部分：數據元素和指向下一個節點的引用。
- 節點之間的連接是循環的，最后一個節點的引用指向第一個節點。
- 循環鏈表可以無限遍歷下去，因為沒有明確的終止點。
- 插入和刪除節點操作在循環鏈表中非常高效，因為只需更新相鄰節點的引用。
- 鏈表的大小可以動態增長或縮小，不需要提前指定大小。
循環鏈表通常用于環狀問題的建模，例如循環隊列、約瑟夫問題（Josephus problem）等。它還可以用于實現循環訪問的數據結構，例如輪播圖或周期性任務列表。
以下是一個簡單的示例，展示了如何在Go語言中實現循環鏈表：
package main
import "fmt"
// 定義循環鏈表節點結構
type Node struct {
data int
next *Node
}
func main() {
// 創建鏈表頭節點
head := &Node{data: 1}
tail := head
// 插入新節點到鏈表
newNode := &Node{data: 2}
tail.next = newNode
tail = newNode
tail.next = head // 使鏈表成為循環
// 遍歷循環鏈表并打印節點的數據
current := head
for i := 0; i < 10; i++ { // 遍歷前10個節點
fmt.Printf("%d -> ", current.data)
current = current.next
}
fmt.Println("...")
}
在這個示例中，我們創建了一個循環鏈表，包含兩個節點，然后將鏈表變為循環，使最后一個節點指向第一個節點。然后，我們遍歷前10個節點并打印它們的數據。由于鏈表是循環的，遍歷可以無限繼續，我們在示例中只遍歷了前10個節點。
循環鏈表的實現可以根據需要進行擴展，包括插入、刪除、查找節點等操作。循環鏈表是一種非常有趣的數據結構，可以應用于各種特定的問題和場景。
2.4 帶頭鏈表
帶頭鏈表（Head Linked List），也稱為帶頭節點鏈表或哨兵節點鏈表，是一種鏈表數據結構，其中鏈表的頭部包含一個額外的節點，通常稱為頭節點（Head Node）或哨兵節點（Sentinel Node）。這個額外的節點不包含實際數據，它的主要目的是簡化鏈表操作，確保鏈表不為空，并在插入和刪除節點時提供一致性。
以下是帶頭鏈表的主要特點和屬性：
特點和屬性：
- 鏈表的頭節點包含兩個部分：指向鏈表的第一個實際節點的引用和通常為空的數據元素。
- 鏈表的頭節點使鏈表操作更簡單，因為不需要特殊處理空鏈表的情況。
- 帶頭鏈表可以用于各種鏈表問題，包括單向鏈表、雙向鏈表、循環鏈表等不同類型的鏈表。
帶頭鏈表通常用于簡化鏈表操作，因為它確保鏈表不為空，即使鏈表沒有實際數據節點時，頭節點也存在。這減少了對特殊情況的處理。
以下是一個示例，展示了如何在Go語言中實現帶頭鏈表：
package main
import "fmt"
// 定義鏈表節點結構
type Node struct {
data int
next *Node
}
func main() {
// 創建鏈表頭節點（帶頭鏈表）
head := &Node{}
current := head
// 插入新節點到鏈表
newNode := &Node{data: 1}
current.next = newNode
current = newNode
// 遍歷鏈表并打印節點的數據
current = head.next // 跳過頭節點
for current != nil {
fmt.Printf("%d -> ", current.data)
current = current.next
}
fmt.Println("nil")
}
在這個示例中，我們創建了一個帶頭鏈表，其中鏈表的頭節點不包含實際數據，然后插入一個新節點到鏈表中。在遍歷鏈表時，我們跳過頭節點并打印數據。帶頭鏈表的頭節點不包含實際數據，但確保了鏈表操作的一致性。帶頭鏈表通常用于實現各種鏈表類型，包括單向鏈表和雙向鏈表等。
2.5 跳表
跳表（Skip List）是一種高級數據結構，用于加速元素的查找操作，類似于平衡樹，但實現更加簡單。跳表通過層級結構在鏈表中添加索引層，從而在查找元素時可以跳過部分元素，提高查找效率。跳表通常用于需要快速查找和插入的數據結構，尤其在有序數據集上表現出色。
以下是跳表的主要特點和屬性：
特點和屬性：
- 層級結構： 跳表包含多個層級，每個層級是一個有序鏈表，其中底層鏈表包含所有元素。
- 索引節點： 在每個層級，跳表添加了一些額外的節點，稱為索引節點，以加速查找。
- 快速查找： 查找元素時，跳表可以從頂層開始，根據元素值向右移動，然后下降到下一個層級繼續查找。
- 高效插入和刪除： 插入和刪除元素時，跳表可以利用索引節點快速定位插入或刪除位置。
- 平均查找時間： 在平均情況下，跳表的查找時間復雜度為O(log n)，其中n是元素數量。
- 可變高度： 跳表的高度可以根據需要調整，以適應元素的動態插入和刪除。
跳表是一種強大的數據結構，適用于需要高效查找和插入操作的場景，例如數據庫索引、緩存實現等。
下面是一個簡單的示例，展示了如何在Go語言中實現跳表：
package main
import (
"fmt"
"math"
"math/rand"
)
// 定義跳表節點結構
type Node struct {
data int
next []*Node // 每個節點的下一層節點
}
type SkipList struct {
header *Node
level int
maxNode *Node
}
func NewSkipList() *SkipList {
header := &Node{data: math.MinInt32, next: make([]*Node, 1)}
return &SkipList{header, 1, nil}
}
func (sl *SkipList) Insert(data int) {
update := make([]*Node, sl.level)
x := sl.header
for i := sl.level - 1; i >= 0; i-- {
for x.next[i] != nil && x.next[i].data < data {
x = x.next[i]
}
update[i] = x
}
level := sl.randomLevel()
if level > sl.level {
for i := sl.level; i < level; i++ {
update = append(update, sl.header)
}
sl.level = level
}
x = &Node{data: data, next: make([]*Node, level)}
for i := 0; i < level; i++ {
x.next[i] = update[i].next[i]
update[i].next[i] = x
}
}
func (sl *SkipList) Search(data int) bool {
x := sl.header
for i := sl.level - 1; i >= 0; i-- {
for x.next[i] != nil && x.next[i].data < data {
x = x.next[i]
}
}
x = x.next[0]
return x != nil && x.data == data
}
func (sl *SkipList) randomLevel() int {
level := 1
for rand.Float64() < 0.5 && level < 32 {
level++
}
return level
}
func main() {
sl := NewSkipList()
data := []int{1, 4, 2, 8, 6, 9, 5, 3, 7}
for _, value := range data {
sl.Insert(value)
}
for _, value := range data {
found := sl.Search(value)
fmt.Printf("Searching for %d: %v\n", value, found)
}
}
在這個示例中，我們實現了一個簡單的跳表，用于插入和查找整數數據。跳表包含多個層級，每個節點都包含一個數據元素和一個指向下一個層級的節點數組。我們可以插入數據并搜索數據，以檢查數據是否存在于跳表中。跳表的高度可以根據需要調整，以適應動態插入操作。這個示例展示了跳表的基本工作原理，實際應用中可以根據需求進行更復雜的擴展。
聲明：本作品采用署名-非商業性使用-相同方式共享 4.0 國際 (CC BY-NC-SA 4.0)進行許可，使用時請注明出處。
Author: mengbin
blog: mengbin
Github: mengbin92
cnblogs: 戀水無意
總結
- 上一篇： 喜闻乐见最新的ORM查询BUG，看看有没
- 下一篇： Redis宕机恢复