线性结构
链表
链表是一种重要的线性数据结构，它由一系列节点组成，这些节点通过指针相互连接，形成一条链。与数组不同，链表的元素在内存中不是连续存储的，链表可以动态调整大小，插入和删除元素非常灵活，但在随机访问上不如数组高效。
链表的基本单元是节点，每个节点包含两部分：
- 数据部分（Data）：存储节点的实际数据，可以是任何类型的数据，如整数、字符串、甚至是对象。
- 指针部分（Pointer）：存储指向下一个节点或上一个节点的指针，用于连接链表中的各个节点。
根据链表指针的链接方式，链表可以分为单链表、双向链表、循环链表三种形式。
单链表
单链表，也称为单向链表（Singly Linked List），每个节点包含数据和指向下一个节点的指针两部分，最后一个节点的指针指向 nullptr。
![[slinklist_01 1.jpeg]]
链表中有一个特殊的指针，称为头指针，它指向链表的第一个节点，如果链表为空，则头指针为 nullptr。
在 C++ 中，通常利用结构体来定义链表，可以像下面这样定义一个单链表的节点结构体：
struct Node { int data; // 数据部分 Node* next; // 指向下一个节点的指针};单链表一般有查找、插入、删除等基本操作
双向链表
- 双向链表（Doubly Linked List）：每个节点包含数据部分和指针部分，指针部分指向前一个节点和下一个节点的指针，头节点的前向指针和尾节点的后向指针指向
nullptr。
循环链表
- 循环链表（Circular Linked List）：链表的最后一个节点的指针指向头节点，形成一个循环结构。可以是单向循环链表，也可以是双向循环链表。
2. 链表的基本操作
2.1 创建链表
创建链表的过程通常包括初始化头指针、动态分配内存以创建新节点，并通过指针将这些节点连接在一起。
以下是创建单向链表的简单示例：
#include <iostream>using namespace std;
struct Node { int data; Node* next;};
int main() { Node* head = nullptr; // 初始化头指针
// 动态分配第一个节点 Node* first = new Node; first->data = 10; first->next = nullptr; head = first; // 头指针指向第一个节点
// 动态分配第二个节点 Node* second = new Node; second->data = 20; second->next = nullptr; first->next = second; // 将第一个节点的 next 指针指向第二个节点
return 0;}2.2 插入节点
在链表中插入节点可以有几种不同的方式：
- 在链表头部插入：将新节点插入到链表的最前面，成为新的头节点。
- 在链表尾部插入：将新节点插入到链表的最后面，成为新的尾节点。
- 在链表中间插入：将新节点插入到链表的某个指定位置。
2.2.1 在头部插入节点
void insertAtHead(Node*& head, int newData) { Node* newNode = new Node; newNode->data = newData; newNode->next = head; head = newNode;}2.2.2 在尾部插入节点
void insertAtTail(Node*& head, int newData) { Node* newNode = new Node; newNode->data = newData; newNode->next = nullptr;
if (head == nullptr) { head = newNode; } else { Node* temp = head; while (temp->next != nullptr) { temp = temp->next; } temp->next = newNode; }}2.3 删除节点
删除节点也有几种不同的方式：
- 删除头节点：将头节点删除，并更新头指针。
- 删除尾节点：将尾节点删除，并更新新的尾节点的
next指针为nullptr。 - 删除中间节点：将链表中指定位置的节点删除，并调整前后节点的指针。
2.3.1 删除头节点
void deleteAtHead(Node*& head) { if (head == nullptr) return;
Node* temp = head; head = head->next; delete temp; // 释放原头节点的内存}2.3.2 删除尾节点
void deleteAtTail(Node*& head) { if (head == nullptr) return;
if (head->next == nullptr) { delete head; // 链表只有一个节点 head = nullptr; } else { Node* temp = head; while (temp->next->next != nullptr) { temp = temp->next; } delete temp->next; // 释放尾节点的内存 temp->next = nullptr; }}2.4 遍历链表
遍历链表时，从头节点开始，沿着 next 指针逐个访问每个节点，直到到达链表的末尾。
以下是遍历并打印链表中所有节点数据的示例：
void printList(Node* head) { Node* temp = head; while (temp != nullptr) { cout << temp->data << " "; temp = temp->next; } cout << endl;}3. 链表的优缺点
3.1 链表的优点
- 动态大小：链表的大小可以根据需要动态调整，不像数组那样在创建时必须指定固定大小。
- 高效的插入和删除：在链表的任意位置进行插入或删除操作时，时间复杂度为 O(1)，不需要移动其他元素。
3.2 链表的缺点
- 随机访问效率低：链表不支持随机访问，要访问某个特定位置的元素，必须从头节点开始逐个遍历。
- 额外的指针存储开销：链表的每个节点都需要额外的存储空间来保存指针，这在大规模数据存储时可能成为一个问题。
4. 链表的实际应用
链表在许多实际场景中都有广泛应用：
- 链表用于实现栈和队列：由于链表插入和删除操作的高效性，它常用于实现栈和队列这种需要频繁插入和删除操作的数据结构。
- 链表用于实现哈希表中的链地址法：在哈希表的冲突处理策略中，链地址法使用链表来处理哈希冲突。
- 链表用于操作系统中的进程调度：操作系统中的进程控制块（PCB）常用链表来管理，方便进程调度和管理。
5. 链表在不同场景中的选择
根据不同的需求和应用场景，可能会选择不同类型的链表：
- 单向链表：适用于只需要单向遍历的场景，简单且节省空间。
- 双向链表：适用于需要双向遍历的场景，如浏览器的前进和后退操作。
- 循环链表：适用于需要循环访问的场景，如循环队列、音乐播放列表等。
总结
链表是一种灵活的线性数据结构，它在内存管理、插入和删除操作的高效性上具有显著优势。通过理解链表的基本概念、操作方法以及在实际应用中的场景，你可以在编程中有效地选择和使用链表。链表与数组相比有其独特的优势和劣势，因此在选择数据结构时，需要根据具体的应用场景做出合理的选择。