链表是一种基本的数据结构，它可以用来存储一系列的元素，并且支持灵活的插入、删除操作。在计算机科学中，链表常常用于构建更复杂的数据结构，如栈、队列以及图等。
链表的基本概念
链表由一系列节点组成，每个节点包含两部分：数据域和指针域。数据域存储节点的值，指针域则指向下一个节点。根据指针的类型，链表分为单向链表和双向链表。
单向链表： 单向链表中，每个节点只有一个指针，指向下一个节点。最后一个节点的指针指向空。这种结构使得在单向链表中，我们只能从头节点开始逐个访问元素，无法直接反向访问。
双向链表： 双向链表中，每个节点有两个指针，一个指向前一个节点，一个指向后一个节点。这种结构允许我们从任一方向遍历链表，灵活性更高。
插入操作
链表的插入操作是向链表中添加新元素。在链表中插入元素有以下几种常见情况：
在链表头部插入新节点
在链表尾部插入新节点
在链表中间某个位置插入新节点
我们将分别介绍这三种情况的插入操作。
在链表头部插入新节点
在链表头部插入新节点是一种常见的操作，它的时间复杂度为 O(1)，因为我们只需改变少量指针的指向。
首先，创建一个新节点，然后将新节点的指针指向原头节点，再更新头节点指针指向新节点。
单向链表头部插入新节点
+---+ +---+
| A | => | N |
+---+ +---+
↑
Head
A: 原头节点
N: 新节点
在链表尾部插入新节点
在链表尾部插入新节点同样需要创建一个新节点，然后将新节点的指针指向原尾节点的下一个节点（即空），再更新原尾节点的指针指向新节点。
单向链表尾部插入新节点
+---+ +---+
| A | | N |
+---+ => +---+
↑ ↑
Head Tail
A: 原尾节点
N: 新节点
在链表中间插入新节点
在链表中间插入新节点需要考虑的是找到插入位置的前一个节点，然后更新前一个节点的指针和新节点的指针。这也是一个 O(1) 的操作，因为我们只需要访问一个常数个节点。
单向链表中间插入新节点：
+---+ +---+ +---+
| A | | N | | B |
+---+ +---+ +---+
↑ ↑
Head Tail
A: 前一个节点
N: 新节点
B: 原插入位置节点
删除操作
链表的删除操作是从链表中移除节点。和插入操作一样，删除操作也有几种情况：
删除链表头部节点
删除链表尾部节点
删除链表中间节点
我们将逐个介绍这些情况的删除操作。
删除链表头部节点
删除链表头部节点同样是一个 O(1) 的操作。我们只需要将头节点指针指向头节点的下一个节点，然后释放原头节点的内存。
删除链表头部节点的示意图（主打一个灵魂）：
+---+ +---+
| A | => | B |
+---+ +---+
↑
Head
A: 原头节点
B: 新头节点
删除链表尾部节点
删除链表尾部节点需要找到倒数第二个节点，然后将倒数第二个节点的指针指向空。最后一个节点则可以被释放。
删除链表尾部节点的（笔者的灵魂模型）：
| A | => | B |
Tail
删除链表中间节点
删除链表中间节点同样需要找到前一个节点和后一个节点，然后将前一个节点的指针指向后一个节点，从而绕过需要删除的节点。被删除的节点可以被释放。
删除链表中间节点的示意图（pus绷不住加个框框哈哈哈）：
+---+ +---+ +---+
| A | | C | | B |
+---+ +---+ +---+
↑ ↑
Head Tail
A: 前一个节点
C: 需要删除的节点
B: 后一个节点
这里使用 C++ 实现链表的插入和删除操作：
#include <iostream>
using namespace std;
class Node {
public:
int data; // 节点存储的数据
Node* next; // 指向下一个节点的指针
Node(int value) : data(value), next(nullptr) {}
};
class LinkedList {
private:
Node* head; // 链表头节点指针
public:
LinkedList() : head(nullptr) {}
// 在链表头部插入新节点
void insertAtHead(int value) {
Node* newNode = new Node(value); // 创建新节点
newNode->next = head; // 新节点指向原头节点
head = newNode; // 更新头节点指针
}
// 删除链表头部节点
void deleteAtHead() {
if (head) {
Node* temp = head; // 临时保存原头节点
head = head->next; // 更新头节点指针
delete temp; // 释放原头节点内存
}
}
// 显示链表中的元素
void display() {
Node* current = head;
while (current) {
cout << current->data << " "; // 输出节点数据
current = current->next; // 移动到下一个节点
}
cout << endl;
}
};
int main() {
LinkedList list;
list.insertAtHead(3);
list.insertAtHead(2);
list.insertAtHead(1);
list.display(); // 输出：1 2 3
list.deleteAtHead();
list.display(); // 输出：2 3
return 0;
}
