【链 表】

一级目录

1. 基本概念

在计算机科学里，算法是为解决特定问题而设计的一系列明确且有限的指令。算法分析的核心目标是评估算法的效率与性能，一般从时间和空间两个维度展开。

• 输入：算法运行所需的初始数据。
• 输出：算法处理输入数据后得到的结果。
• 确定性：算法的每个步骤都有明确的定义，不存在歧义。
• 有穷性：算法必须在有限的步骤内结束。
• 有效性：算法的每个步骤都能在有限时间内完成，并且是可行的。

2. 算法分析

2.1 时间复杂度

时间复杂度用于衡量算法执行所花费的时间随输入规模增长而变化的趋势，它不关注具体的执行时间，而是关注算法执行时间与输入规模之间的函数关系通常用大 $O$ 符号来表示。

• 常见时间复杂度
  • 常数时间复杂度 $O(1)$：算法的执行时间不随输入规模的变化而变化。例如，访问数组中的某个元素：

def access_element(arr, index):return arr[index]

- **线性时间复杂度 $O(n)$**：算法的执行时间与输入规模 $n$ 成正比。例如，遍历数组中的每个元素：

def traverse_array(arr):for element in arr:print(element)

- **对数时间复杂度 $O(log n)$**：算法的执行时间随输入规模的对数增长。常见于二分查找算法：

def binary_search(arr, target):left, right = 0, len(arr) - 1while left <= right:mid = (left + right) // 2if arr[mid] == target:return midelif arr[mid] < target:left = mid + 1else:right = mid - 1return -1

- **平方时间复杂度 $O(n^2)$**：算法的执行时间与输入规模的平方成正比。例如，冒泡排序算法：

def bubble_sort(arr):n = len(arr)for i in range(n):for j in range(0, n - i - 1):if arr[j] > arr[j + 1]:arr[j], arr[j + 1] = arr[j + 1], arr[j]return arr

2.2 空间复杂度

空间复杂度用于衡量算法在执行过程中所占用的存储空间随输入规模增长而变化的趋势，同样用大 $O$ 符号表示。

• 常见空间复杂度
  • 常数空间复杂度 $O(1)$：算法执行过程中所占用的存储空间不随输入规模的变化而变化。例如，交换两个变量的值：

def swap(a, b):temp = aa = bb = tempreturn a, b

- **线性空间复杂度 $O(n)$**：算法执行过程中所占用的存储空间与输入规模 $n$ 成正比。例如，创建一个长度为 $n$ 的数组：

def create_array(n):return [0] * n

2.3 时空复杂度互换

在算法设计中，时间复杂度和空间复杂度往往是相互制约的。有时候可以通过增加空间开销来降低时间复杂度，或者通过增加时间开销来减少空间复杂度，这就是时空复杂度互换。

• 以空间换时间
  • 原理：利用额外的存储空间来存储中间结果或数据，从而减少重复计算，降低时间复杂度。
  • 示例：斐波那契数列的计算。传统的递归方法时间复杂度为 $O(2^n)$，但可以使用动态规划的方法，通过一个数组来存储中间结果，将时间复杂度降低到 $O(n)$，空间复杂度为 $O(n)$。

def fibonacci(n):if n == 0 or n == 1:return ndp = [0] * (n + 1)dp[1] = 1for i in range(2, n + 1):dp[i] = dp[i - 1] + dp[i - 2]return dp[n]

• 以时间换空间
  • 原理：减少存储空间的使用，通过重复计算或其他方式来弥补空间的不足，从而增加时间复杂度。
  • 示例：在某些情况下，如果不使用额外的数组来存储中间结果，而是在每次需要时重新计算，就可以减少空间开销，但会增加时间开销。例如，在计算斐波那契数列时，可以使用迭代方法，只使用常数级的额外空间，但时间复杂度仍然是 $O(n)$。

def fibonacci_iterative(n):if n == 0 or n == 1:return na, b = 0, 1for i in range(2, n + 1):a, b = b, a + breturn b

综上所述，算法分析中的时间复杂度、空间复杂度以及时空复杂度互换是设计和评估算法的重要概念，需要根据具体的问题和场景来选择合适的算法和策略。

线性表的概念

线性表（Linear List）是一种最基本、最简单的数据结构，它是由 $n$ （$n\ge 0$）个数据元素（节点）组成的有限序列。

其中，除第一个元素外，每个元素都有且仅有一个直接前驱；除最后一个元素外，每个元素都有且仅有一个直接后继。数据元素之间呈现出一对一的线性关系。

线性表的举例

• 学生信息表：假设要管理一个班级学生的信息，每个学生信息包含学号、姓名、年龄等。可以将每个学生的信息看作一个数据元素，这些学生信息按一定顺序排列就构成了一个线性表。例如，按照学号从小到大的顺序排列所有学生信息。
• 图书列表：在图书馆管理系统中，每本图书的信息（如书名、作者、ISBN 号等）是一个数据元素，所有图书信息组成的列表就是一个线性表。

顺序表的基本概念

顺序表（Sequential List）是线性表的一种顺序存储结构，它是用一组地址连续的存储单元依次存储线性表中的各个数据元素，使得逻辑上相邻的数据元素在物理位置上也相邻。在高级编程语言中，通常使用数组来实现顺序表。

顺序表的基本操作

1. 初始化

创建一个空的顺序表，通常需要分配一定的存储空间。以下是 Python 代码示例：

class SeqList:def __init__(self, max_size=100):self.max_size = max_sizeself.data = [None] * max_sizeself.length = 0

2. 插入操作

在顺序表的指定位置插入一个新的数据元素。插入操作可能需要移动元素以腾出插入位置。以下是插入操作的代码示例：

    def insert(self, index, value):if index < 0 or index > self.length:return Falseif self.length >= self.max_size:return Falsefor i in range(self.length, index, -1):self.data[i] = self.data[i - 1]self.data[index] = valueself.length += 1return True

3. 删除操作

删除顺序表中指定位置的数据元素。删除操作后，需要将后续元素前移以填补空缺。以下是删除操作的代码示例：

    def delete(self, index):if index < 0 or index >= self.length:return Falsefor i in range(index, self.length - 1):self.data[i] = self.data[i + 1]self.length -= 1return True

4. 查找操作

根据给定的值或位置查找顺序表中的数据元素。以下是按值查找的代码示例：

    def search(self, value):for i in range(self.length):if self.data[i] == value:return ireturn -1

5. 遍历操作

依次访问顺序表中的每个数据元素。以下是遍历操作的代码示例：

    def traverse(self):for i in range(self.length):print(self.data[i], end=" ")print()

顺序表的优缺点总结

优点

• 随机访问效率高：由于顺序表使用数组存储，通过数组下标可以直接访问任意位置的元素，时间复杂度为 $O(1)$。例如，要访问顺序表中第 $i$ 个元素，直接通过数组下标 $i$ 即可快速定位。
• 存储密度大：顺序表中只存储数据元素本身，不需要额外的指针来表示元素之间的逻辑关系，因此存储密度为 1，空间利用率高。

缺点

**

• 插入和删除操作效率低：在顺序表中进行插入和删除操作时，通常需要移动大量元素，平均时间复杂度为 $O(n)$。例如，在顺序表的开头插入一个元素，需要将后面的所有元素依次后移一位。
• 空间分配不灵活：顺序表在初始化时需要预先分配一定的存储空间，如果预先分配的空间过大，会造成空间浪费；如果预先分配的空间过小，又可能导致数据溢出。并且，在运行过程中难以动态调整存储空间的大小。

**

树形结构

- **概念**：非线性数据结构，由节点和边组成，有根节点，除根外每个节点有一个父节点，可有多子节点，无环。
- **特点**：层次分明，呈一对多关系。
- **常见类型**：二叉树、二叉搜索树、AVL 树、红黑树、B 树和 B + 树等。
- **应用**：用于文件系统组织、数据库索引、编译原理中的语法分析等。

图形结构

- **概念**：比树形结构复杂的非线性结构，由顶点和边构成，边可有无方向、可带权重。
- **特点**：顶点关系多对多，可能存在环。
- **常见类型**：无向图、有向图、带权图。
- **应用**：适用于社交网络分析、交通网络路径规划、电路设计等。 

单链表基本概念

单链表是一种常见的线性数据结构，它由一系列节点组成。每个节点包含两部分：数据域和指针域。数据域用于存储实际的数据，指针域存储指向下一个节点的指针（地址）。链表的第一个节点称为头节点，最后一个节点的指针域通常指向空（NULL 或 None），以此表示链表的结束。

链表的分类

• 单链表：节点只有一个指向下一个节点的指针，只能单向遍历。
• 双向链表：每个节点除了有指向下一个节点的指针外，还有一个指向前一个节点的指针，可双向遍历。
• 循环链表：单链表或双向链表的最后一个节点的指针域指向头节点，形成一个环。
  

单链表节点设置

以下是用 Python 和 C++ 实现单链表节点的示例：

Python 实现

class Node:def __init__(self, data):self.data = data  # 数据域self.next = None  # 指针域，初始化为 None

C++ 实现

#include <iostream>struct Node {int data;  // 数据域Node* next;  // 指针域Node(int value) : data(value), next(nullptr) {}  // 构造函数
};

单链表初始化

初始化一个单链表通常是创建一个头节点，其数据域可以不存储实际数据，仅作为链表的起始标识。

Python 实现

class LinkedList:def __init__(self):self.head = None  # 初始化头节点为 None

C++ 实现

class LinkedList {
private:Node* head;
public:LinkedList() : head(nullptr) {}  // 构造函数，初始化头节点为 nullptr
};

单链表增加节点

尾部插入

在链表尾部添加新节点。

Python 实现

class LinkedList:def __init__(self):self.head = Nonedef append(self, data):new_node = Node(data)if not self.head:self.head = new_nodereturnlast_node = self.headwhile last_node.next:last_node = last_node.nextlast_node.next = new_node

C++ 实现

class LinkedList {
private:Node* head;
public:LinkedList() : head(nullptr) {}void append(int data) {Node* new_node = new Node(data);if (!head) {head = new_node;return;}Node* last_node = head;while (last_node->next) {last_node = last_node->next;}last_node->next = new_node;}
};

单链表的遍历

依次访问链表中的每个节点并处理其数据。

Python 实现

class LinkedList:# ... 前面的代码 ...def traverse(self):current_node = self.headwhile current_node:print(current_node.data)current_node = current_node.next

C++ 实现

class LinkedList {// ... 前面的代码 ...void traverse() {Node* current_node = head;while (current_node) {std::cout << current_node->data << std::endl;current_node = current_node->next;}}
};

单链表的销毁

释放链表中所有节点占用的内存。

Python 实现

class LinkedList:# ... 前面的代码 ...def destroy(self):current_node = self.headwhile current_node:next_node = current_node.nextdel current_nodecurrent_node = next_nodeself.head = None

C++ 实现

class LinkedList {// ... 前面的代码 ...~LinkedList() {Node* current_node = head;while (current_node) {Node* next_node = current_node->next;delete current_node;current_node = next_node;}head = nullptr;}
};

链表的优缺点

优点

• 动态内存分配：链表可以在运行时动态分配和释放内存，不需要预先分配固定大小的空间，适合存储数量不确定的数据。
• 插入和删除效率高：在链表中插入或删除节点，只需要修改指针，时间复杂度为 $O(1)$（前提是已知要操作的节点位置）。

缺点

• 随机访问效率低：链表不支持随机访问，要访问链表中的某个节点，必须从头节点开始依次遍历，时间复杂度为 $O(n)$。
• 额外的指针开销：每个节点需要额外的指针域来存储指向下一个节点的地址，增加了内存开销。

循环链表

循环链表是一种特殊的链表，它的最后一个节点的指针域指向头节点，形成一个环。与单链表相比，循环链表可以从任意节点开始遍历整个链表。

循环链表节点设置与单链表相同，以下是循环链表初始化和尾部插入的 Python 示例：

class Node:def __init__(self, data):self.data = dataself.next = Noneclass CircularLinkedList:def __init__(self):self.head = Nonedef append(self, data):new_node = Node(data)if not self.head:self.head = new_nodenew_node.next = self.headreturnlast_node = self.headwhile last_node.next != self.head:last_node = last_node.nextlast_node.next = new_nodenew_node.next = self.head

循环链表在某些场景下很有用，例如实现循环队列、约瑟夫环问题等。

双向链表的概念

双向链表（Doubly Linked List）是一种线性数据结构，它是在单链表的基础上进行扩展。

每个节点除了包含数据域和指向下一个节点的指针（后继指针）外， 还包含一个指向前一个节点的指针（前驱指针）。

这种结构使得双向链表可以从两个方向进行遍历，既可以从链表头开始向后遍历，也可以从链表尾开始向前遍历。

基本操作

双向链表的基本操作包括初始化、插入节点、剔除节点、遍历链表以及销毁链表等。

节点设计

以下是使用 Python 和 C++ 实现双向链表节点的示例：

Python 实现

class Node:def __init__(self, data):self.data = data  # 数据域self.prev = None  # 前驱指针，初始化为 Noneself.next = None  # 后继指针，初始化为 None

C++ 实现

#include <iostream>struct Node {int data;  // 数据域Node* prev;  // 前驱指针Node* next;  // 后继指针Node(int value) : data(value), prev(nullptr), next(nullptr) {}  // 构造函数
};

初始化

初始化双向链表通常是创建一个头节点，该头节点的数据域可以不存储实际数据，仅作为链表的起始标识。

Python 实现

class DoublyLinkedList:def __init__(self):self.head = None  # 初始化头节点为 None

C++ 实现

class DoublyLinkedList {
private:Node* head;
public:DoublyLinkedList() : head(nullptr) {}  // 构造函数，初始化头节点为 nullptr
};

插入节点

插入节点可以分为在链表头部插入、在链表尾部插入和在指定位置插入等情况。以下以在链表尾部插入为例：

Python 实现

class DoublyLinkedList:def __init__(self):self.head = Nonedef append(self, data):new_node = Node(data)if not self.head:self.head = new_nodereturnlast_node = self.headwhile last_node.next:last_node = last_node.nextlast_node.next = new_nodenew_node.prev = last_node

C++ 实现

class DoublyLinkedList {
private:Node* head;
public:DoublyLinkedList() : head(nullptr) {}void append(int data) {Node* new_node = new Node(data);if (!head) {head = new_node;return;}Node* last_node = head;while (last_node->next) {last_node = last_node->next;}last_node->next = new_node;new_node->prev = last_node;}
};

剔除节点

剔除节点时需要处理好前驱和后继指针的关系，以保证链表的连贯性。以下是删除指定值节点的示例：

Python 实现

class DoublyLinkedList:# ... 前面的代码 ...def delete(self, key):current = self.headwhile current:if current.data == key:if current.prev:current.prev.next = current.nextelse:self.head = current.nextif current.next:current.next.prev = current.prevreturncurrent = current.next

C++ 实现

class DoublyLinkedList {// ... 前面的代码 ...void deleteNode(int key) {Node* current = head;while (current) {if (current->data == key) {if (current->prev) {current->prev->next = current->next;} else {head = current->next;}if (current->next) {current->next->prev = current->prev;}delete current;return;}current = current->next;}}
};

链表的遍历

双向链表可以从前往后或从后往前遍历。以下是从前往后遍历的示例：

Python 实现

class DoublyLinkedList:# ... 前面的代码 ...def traverse_forward(self):current = self.headwhile current:print(current.data)current = current.next

C++ 实现

class DoublyLinkedList {// ... 前面的代码 ...void traverseForward() {Node* current = head;while (current) {std::cout << current->data << std::endl;current = current->next;}}
};

销毁链表

释放链表中所有节点占用的内存。

Python 实现

class DoublyLinkedList:# ... 前面的代码 ...def destroy(self):current = self.headwhile current:next_node = current.nextdel currentcurrent = next_nodeself.head = None

C++ 实现

class DoublyLinkedList {// ... 前面的代码 ...~DoublyLinkedList() {Node* current = head;while (current) {Node* next_node = current->next;delete current;current = next_node;}head = nullptr;}
};

适用场合

• 需要双向遍历的场景：当需要频繁地从两个方向访问数据时，双向链表非常合适。例如，在文本编辑器中实现撤销和重做功能，双向链表可以方便地记录操作历史，向前遍历可以实现撤销操作，向后遍历可以实现重做操作。
• 需要高效删除节点的场景：在双向链表中删除一个节点时，由于可以直接访问其前驱节点，不需要像单链表那样从头节点开始遍历找到前驱节点，因此删除操作更加高效。例如，在实现
  LRU（Least Recently Used）缓存算法时，双向链表结合哈希表可以高效地实现缓存的淘汰机制。

1. Linux 内核链表概述

Linux 内核链表是一种非常经典且高效的数据结构实现，它采用了一种独特的设计方式，将链表节点嵌入到其他数据结构中，从而实现了链表的通用性和灵活性。这种设计使得链表可以方便地管理各种不同类型的数据，避免了为每种数据类型都单独实现一个链表的繁琐工作。

2. 容器与通用性

容器概念

在 Linux 内核链表中，“容器”指的是包含链表节点的数据结构。链表节点并不是直接存储数据，而是作为一个成员嵌入到其他结构体中。通过这种方式，链表可以将不同类型的数据组织起来，这些包含链表节点的结构体就像是一个个“容器”，链表节点则是连接这些容器的纽带。

通用性体现

由于链表节点不依赖于具体的数据类型，只要在自定义的数据结构中包含 list_head 结构体，就可以将这些数据结构添加到链表中进行管理。这使得内核链表可以用于管理各种不同类型的数据，如进程描述符、文件描述符等，大大提高了代码的复用性和可维护性。

3. 节点的设计

Linux 内核链表的节点由 list_head 结构体表示，其定义位于 <linux/list.h> 头文件中，代码如下：

struct list_head {struct list_head *next, *prev;
};

这个结构体只包含两个指针，分别指向前一个节点和后一个节点，不包含任何数据域。当需要使用链表来管理数据时，只需要在自定义的数据结构中包含一个 list_head 成员即可。例如：

struct my_data {int value;struct list_head list;  // 嵌入链表节点
};

4. 增删操作

初始化链表

在使用链表之前，需要对链表进行初始化。可以使用 INIT_LIST_HEAD 宏来初始化一个链表头：

#include <linux/list.h>struct list_head my_list;
INIT_LIST_HEAD(&my_list);

添加节点

Linux 内核提供了几个宏来实现节点的添加操作，常用的有 list_add 和 list_add_tail。

• list_add：将新节点添加到指定节点之后，通常用于在链表头部插入节点。

struct my_data *new_node = kmalloc(sizeof(struct my_data), GFP_KERNEL);
new_node->value = 10;
list_add(&new_node->list, &my_list);

• list_add_tail：将新节点添加到指定节点之前，通常用于在链表尾部插入节点。

struct my_data *new_node = kmalloc(sizeof(struct my_data), GFP_KERNEL);
new_node->value = 20;
list_add_tail(&new_node->list, &my_list);

删除节点

使用 list_del 宏可以从链表中删除一个节点：

struct my_data *node_to_delete;
// 假设 node_to_delete 指向要删除的节点
list_del(&node_to_delete->list);
kfree(node_to_delete);

5. 查找结点

Linux 内核链表本身并没有提供专门的查找函数，因为链表节点不包含数据域，查找操作通常需要结合具体的数据结构来实现。可以通过遍历链表，比较每个节点所包含的数据来查找符合条件的节点。例如，查找 value 等于某个特定值的节点：

struct my_data *entry;
list_for_each_entry(entry, &my_list, list) {if (entry->value == target_value) {// 找到目标节点break;}
}

6. 遍历链表

Linux 内核提供了几个宏来方便地遍历链表，常用的有 list_for_each 和 list_for_each_entry。

list_for_each

用于遍历链表节点，它只操作 list_head 结构体：

struct list_head *pos;
list_for_each(pos, &my_list) {// 处理节点
}

list_for_each_entry

用于遍历包含链表节点的数据结构，它会根据链表节点的地址计算出包含该节点的数据结构的地址：

struct my_data *entry;
list_for_each_entry(entry, &my_list, list) {printk(KERN_INFO "Value: %d\n", entry->value);
}

综上所述，Linux 内核链表通过巧妙的设计实现了高度的通用性和灵活性，为内核中的数据管理提供了强大而高效的工具。