数据结构之链表

1. 简介
2. 链表分类

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: 恋水无意