GESP考点
GESP 五级对链表的考查包括：单链表、双链表、循环链表的创建、插入、删除、遍历和反转等基本操作，以及链表与数组的对比。
做编程题时可能需要用到STL工具解决问题。
链表的基本概念
定义：一系列通过指针连接的节点，每个节点包含数据域（val）和指针域（next）
分类：单链表、双链表、循环链表
节点定义速记：
// 单链表节点
struct SNode {
int data;
SNode* next;
};
// 双链表节点
struct DNode {
int data;
DNode* prev, *next;
};链表操作速记：
单链表插入（在 p 之后插入 s）：
s->next = p->next; // ①新节点指向p的后继
p->next = s; // ②p指向新节点双向链表插入（在 p 之前插入 s）
s->next = p; // ①新节点指向p
s->prev = p->prev; // ②新节点前驱指向p的前驱
p->prev->next = s; // ③p的前驱的next指向s
p->prev = s; // ④p的前驱指针指向s双向链表尾部插入（append）
tail->next = newNode; // ①原尾节点的next指向新节点
newNode->prev = tail; // ②新节点的prev指向原尾节点
tail = newNode; // ③更新尾指针单链表删除（p为待删节点的前驱）：
Node* del = p->next; // 找到要删的节点
p->next = del->next; // 绕过它
delete del; // 释放内存循环链表删除（约瑟夫问题场景）
prev->next = p->next; // ①绕开要删除的节点p
delete p; // ②释放p
p = prev->next; // ③p指向下一个节点遍历
// 单链表遍历（p为头节点）
while(p) {
cout << p->data << " ";
p = p->next;
}链表VS数组
| 对比维度 | 数组 | 链表 |
|---|---|---|
| 内存 | 连续空间 | 离散空间 |
| 访问 | 下标 O(1) 随机访问 | 只能顺序遍历 O(n) |
| 插入/删除 | O(n) 需移动大量元素 | O(1) 只改指针 |
| 长度 | 固定（静态分配） | 动态扩展 |
| 内存位置 | 栈区（局部数组） | 堆区（new/delete） |
| 缓存友好性 | ✅ 连续内存，预读取效率高 | ❌ 节点分散，CPU预取失效 |
- 用链表：频繁在中间插入/删除、数据量动态变化（如约瑟夫环、LRU缓存）
- 用数组：频繁随机访问、数据量固定（如查找、排序算法）
链表判空方式：
bool is_empty() {
// ✅ 正确写法
return head == nullptr;
// 或 return tail == nullptr;
// 或 return size == 0;
// ❌ 不可用
// return head.data == 0; // head是指针，不能这样写！且data=0不代表链表为空
}约瑟夫环代码：
// 创建循环链表：尾节点的next指向头节点
Node* createCircularList(int n) {
Node* head = new Node(1);
Node* prev = head;
for (int i = 2; i <= n; i++) {
Node* node = new Node(i);
prev->next = node;
prev = node;
}
prev->next = head; // 尾→头，形成环
return head;
}实际做题时，画图推演！！！画图推演！！！画图推演！！！