题目：不使用内置链表，实现 get、头插、尾插、指定位置插入和指定位置删除。下标从 0 开始，非法查询返回 -1。
使用一个虚拟头节点 dummyHead_ 和一个记录真实节点数量的 size_。虚拟头节点永远存在，但不存题目数据；真正的第一个节点是 dummyHead_->next。
插入和删除都先找到目标位置的前驱节点，再修改 next：
1
2
| 插入：prev -> next 变成 prev -> newNode -> next
删除：prev -> target -> next 变成 prev -------> next
|
size_ 只负责判断下标是否合法，不能让链表像数组一样随机访问。访问第 index 个节点仍然需要从头沿着 next 走过去。
| 操作 | 时间复杂度 |
|---|
get(index) | $O(index)$，最坏 $O(n)$ |
addAtHead | $O(1)$ |
addAtTail | $O(n)$ |
addAtIndex | $O(index)$，最坏 $O(n)$ |
deleteAtIndex | $O(index)$，最坏 $O(n)$ |
总空间复杂度为 $O(n)$。
我的思考顺序是：
- 先构造只包含
val 和 next 的单链表节点。 - 写
get(index) 时意识到需要判断越界，于是引入 numbers 记录节点数量。 - 看到
index 后联想到 operator[]，又尝试设计一层 NodeList。 - 为了实现按下标查找，一度考虑
vector 和 unordered_map。 - 随后发现：用现成容器保存节点，实际上绕开了"自己实现链表"的训练目标。
- 回到虚拟头节点，但不知道它应该放在哪里、怎样与真实节点连接。
当时的核心尝试大致是：
1
2
3
4
5
6
7
8
9
10
| struct st_node {
int st_val{};
st_node* st_next{};
};
class NodeList {
int numbers{};
vector<st_node> node_list_;
unordered_map<int, st_node> select_table;
};
|
这段尝试的价值
方向虽然绕远了，但成功暴露出一个关键区别：下标是接口提供的查询条件，不代表底层必须支持数组式随机访问。
这里其实只需要两层结构：
1
2
3
4
5
6
7
| MyLinkedList
├── dummyHead_：虚拟头节点
└── size_：真实节点数量
Node
├── val
└── next
|
不需要再增加 NodeList，也不需要重载 operator[]。
另外，构造函数里单独写：
只会创建一个立即销毁的临时对象，并不会初始化链表成员。虚拟头节点必须成为 MyLinkedList 的成员：
1
| MyLinkedList() : dummyHead_(new Node()), size_(0) {}
|
没有虚拟头节点时，头部插入和删除通常要单独修改 head：
加入虚拟头节点后：
1
| dummy -> A -> B -> nullptr
|
此时 A 也有统一的前驱 dummy。所以在下标 0 处插入、删除，与中间位置的操作完全一样，不需要单独处理真实头节点。
记住这一句
查询节点时找"目标节点"；插入和删除时找"目标位置的前驱节点"。
假设要在 index = 2 前插入：
1
2
3
| dummy -> 0 -> 1 -> 2
↑
prev
|
从 dummy 出发移动 index 次，正好到达原下标 1 的节点，也就是插入位置的前驱。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
| class MyLinkedList {
private:
struct Node {
int val;
Node* next;
Node(int value = 0, Node* nextNode = nullptr)
: val(value), next(nextNode) {}
};
Node* dummyHead_; // 永远存在，不计入 size_
int size_; // 真实数据节点的数量
public:
MyLinkedList()
: dummyHead_(new Node()), size_(0) {}
~MyLinkedList() {
Node* cur = dummyHead_;
while (cur != nullptr) {
Node* next = cur->next;
delete cur;
cur = next;
}
}
int get(int index) {
if (index < 0 || index >= size_) {
return -1;
}
Node* cur = dummyHead_->next;
for (int i = 0; i < index; ++i) {
cur = cur->next;
}
return cur->val;
}
void addAtHead(int val) {
addAtIndex(0, val);
}
void addAtTail(int val) {
addAtIndex(size_, val);
}
void addAtIndex(int index, int val) {
if (index < 0) {
index = 0;
}
if (index > size_) {
return;
}
Node* prev = dummyHead_;
for (int i = 0; i < index; ++i) {
prev = prev->next;
}
prev->next = new Node(val, prev->next);
++size_;
}
void deleteAtIndex(int index) {
if (index < 0 || index >= size_) {
return;
}
Node* prev = dummyHead_;
for (int i = 0; i < index; ++i) {
prev = prev->next;
}
Node* target = prev->next;
prev->next = target->next;
delete target;
--size_;
}
};
|
1
2
3
4
5
6
7
8
9
10
11
12
13
| 初始：dummy
addAtHead(1)
dummy -> 1
addAtTail(3)
dummy -> 1 -> 3
addAtIndex(1, 2)
dummy -> 1 -> 2 -> 3
deleteAtIndex(1)
dummy -> 1 -> 3
|
每次成功插入后 size_ 加一，每次成功删除后 size_ 减一。
dummyHead_ 永远存在，而且不计入 size_。size_ 必须等于真实数据节点的数量。- 最后一个真实节点的
next 必须是 nullptr。
边界区别
addAtIndex 允许 index == size_，因为这代表尾插；但 get 和 deleteAtIndex 要求 index < size_。
- 插入、删除成功后才修改
size_。 - 删除前先保存
target，重新连接后再 delete target。 - 虚拟头节点不是下标
0；真实下标 0 是 dummyHead_->next。 vector 和哈希表可以加速按下标访问，但那已经改变了题目要求的数据结构实现方式。
如果额外维护一个尾指针，可以把 addAtTail 优化为 $O(1)$。但删除最后一个节点时也必须正确更新尾指针，维护成本更高。当前版本先把"虚拟头节点 + 前驱定位"掌握牢更重要。
- 能解释为什么
size_ 不能实现随机访问 - 能画出虚拟头节点与真实头节点的关系
- 不看答案写出指定位置插入
- 说清楚插入和删除的合法下标范围为什么不同