链表是一种线性数据结构，由一系列节点组成。每个节点包含：
| 特性 | 数组 | 链表 |
|---|---|---|
| 内存 | 连续 | 不连续 |
| 访问第i个元素 | O(1) | O(n) |
| 插入/删除 | O(n) | O(1)（已知位置时） |
| 空间 | 固定大小 | 动态分配 |
1struct Node {
2 int data;
3 Node* next;
4};
5
6// 头插法
7void insertHead(Node*& head, int val) {
8 Node* newNode = new Node{val, head};
9 head = newNode;
10}
11
12// 删除节点
13void deleteNode(Node*& head, int val) {
14 if (!head) return;
15 if (head->data == val) {
16 Node* temp = head;
17 head = head->next;
18 delete temp;
19 return;
20 }
21 Node* cur = head;
22 while (cur->next && cur->next->data != val)
23 cur = cur->next;
24 if (cur->next) {
25 Node* temp = cur->next;
26 cur->next = temp->next;
27 delete temp;
28 }
29}