01-数组与链表
💡 核心结论
数组
内存：连续内存空间，固定大小或动态扩容
访问：O(1)随机访问任意元素
插入删除：O(n)需要移动元素，末尾操作O(1)
扩容：通常2倍扩容，摊还复杂度O(1)
适用：读多写少、需要随机访问
链表
内存：离散内存空间，动态分配
访问：O(n)只能顺序访问
插入删除：O(1)已知位置直接操作，查找位置O(n)
无需扩容：动态增长，无容量限制
适用：频繁插入删除、不需随机访问
关键对比
特性 |
数组 |
链表 |
|---|---|---|
内存 |
连续 |
分散 |
访问 |
O(1) |
O(n) |
插入删除 |
O(n) |
O(1)* |
缓存友好 |
✅ |
❌ |
内存开销 |
低 |
高（额外指针） |
*已知位置
🎯 数组（Array）
特点
连续内存空间
支持随机访问 O(1)
插入删除 O(n)
固定大小（静态数组）或动态扩容（动态数组）
动态数组实现
初始容量
自动扩容（通常2倍）
缩容策略
时间复杂度
操作 |
平均 |
最坏 |
|---|---|---|
访问 |
O(1) |
O(1) |
查找 |
O(n) |
O(n) |
插入 |
O(n) |
O(n) |
删除 |
O(n) |
O(n) |
末尾插入 |
O(1)* |
O(n) |
*摊还复杂度
🔗 链表（Linked List）
单链表
head -> [data|next] -> [data|next] -> [data|next] -> null
特点：
单向遍历
O(1)头部插入删除
O(n)查找
双链表
null <- [prev|data|next] <-> [prev|data|next] <-> [prev|data|next] -> null
特点：
双向遍历
O(1)头尾插入删除
O(n)查找
循环链表
┌──────────────────────────┐
↓ ↑
[data|next] -> [data|next] -> [data|next]
特点：
尾节点指向头节点
适合循环遍历
时间复杂度
操作 |
平均 |
最坏 |
|---|---|---|
访问 |
O(n) |
O(n) |
查找 |
O(n) |
O(n) |
插入（已知位置） |
O(1) |
O(1) |
删除（已知位置） |
O(1) |
O(1) |
插入（需查找） |
O(n) |
O(n) |
删除（需查找） |
O(n) |
O(n) |
⚖️ 数组 vs 链表
特性 |
数组 |
链表 |
|---|---|---|
内存 |
连续 |
分散 |
大小 |
固定或扩容 |
动态 |
访问 |
O(1) 随机访问 |
O(n) 顺序访问 |
插入删除 |
O(n) |
O(1) |
空间利用 |
紧凑 |
额外指针开销 |
缓存友好 |
是 |
否 |
🔧 应用场景
数组适用于
需要随机访问
数据量固定或变化不大
读多写少
链表适用于
频繁插入删除
不知道数据规模
不需要随机访问
💡 实战技巧
快慢指针
# 找链表中点
def find_middle(head):
slow = fast = head
while fast and fast.next:
slow = slow.next
fast = fast.next.next
return slow
# 检测环
def has_cycle(head):
slow = fast = head
while fast and fast.next:
slow = slow.next
fast = fast.next.next
if slow == fast:
return True
return False
反转链表
def reverse_list(head):
prev = None
curr = head
while curr:
next_node = curr.next
curr.next = prev
prev = curr
curr = next_node
return prev
合并有序链表
def merge_lists(l1, l2):
dummy = ListNode(0)
curr = dummy
while l1 and l2:
if l1.val < l2.val:
curr.next = l1
l1 = l1.next
else:
curr.next = l2
l2 = l2.next
curr = curr.next
curr.next = l1 or l2
return dummy.next
📚 LeetCode练习
数组
链表
🎯 实现要点
Python实现
使用列表实现动态数组
自定义ListNode类
利用Python的垃圾回收
C++实现
手动内存管理
使用指针和引用
注意内存泄漏
实现析构函数
📊 性能分析
数组扩容策略
容量翻倍：
初始: 4
扩容: 4 -> 8 -> 16 -> 32 -> 64
总拷贝: 4 + 8 + 16 + 32 = 60
插入64个元素，平均每次拷贝 < 1
摊还复杂度: O(1)
链表vs数组实测
操作10000次：
- 数组随机访问: 0.001s
- 链表顺序访问: 0.1s
- 数组末尾插入: 0.01s
- 链表头部插入: 0.005s
- 数组中间插入: 1s
- 链表已知位置插入: 0.001s
💡 最佳实践
选择合适的数据结构
需要频繁随机访问 → 数组
需要频繁插入删除 → 链表
内存管理
C++必须手动delete
Python自动垃圾回收
注意循环引用
边界条件
空链表
单节点
头尾操作
代码优化
使用哨兵节点简化逻辑
避免重复遍历
注意指针空判断
💻 完整代码实现
Python 实现
数组实现
1"""
2动态数组实现
3支持自动扩容和缩容
4"""
5
6class DynamicArray:
7 """动态数组实现"""
8
9 def __init__(self, capacity=4):
10 """初始化
11
12 Args:
13 capacity: 初始容量
14 """
15 self._data = [None] * capacity
16 self._size = 0
17 self._capacity = capacity
18
19 def __len__(self):
20 """返回元素个数"""
21 return self._size
22
23 def __getitem__(self, index):
24 """获取索引位置的元素
25
26 Args:
27 index: 索引
28
29 Returns:
30 元素值
31
32 Raises:
33 IndexError: 索引越界
34 """
35 if not 0 <= index < self._size:
36 raise IndexError('Index out of range')
37 return self._data[index]
38
39 def __setitem__(self, index, value):
40 """设置索引位置的元素
41
42 Args:
43 index: 索引
44 value: 新值
45
46 Raises:
47 IndexError: 索引越界
48 """
49 if not 0 <= index < self._size:
50 raise IndexError('Index out of range')
51 self._data[index] = value
52
53 def append(self, value):
54 """在末尾添加元素
55
56 Args:
57 value: 要添加的元素
58 """
59 if self._size == self._capacity:
60 self._resize(2 * self._capacity) # 扩容2倍
61 self._data[self._size] = value
62 self._size += 1
63
64 def insert(self, index, value):
65 """在指定位置插入元素
66
67 Args:
68 index: 插入位置
69 value: 要插入的元素
70
71 Raises:
72 IndexError: 索引越界
73 """
74 if not 0 <= index <= self._size:
75 raise IndexError('Index out of range')
76
77 if self._size == self._capacity:
78 self._resize(2 * self._capacity)
79
80 # 后移元素
81 for i in range(self._size, index, -1):
82 self._data[i] = self._data[i - 1]
83
84 self._data[index] = value
85 self._size += 1
86
87 def remove(self, value):
88 """删除第一个匹配的元素
89
90 Args:
91 value: 要删除的元素
92
93 Raises:
94 ValueError: 元素不存在
95 """
96 for i in range(self._size):
97 if self._data[i] == value:
98 self.pop(i)
99 return
100 raise ValueError(f'{value} not in array')
101
102 def pop(self, index=None):
103 """删除并返回指定位置的元素
104
105 Args:
106 index: 索引，默认为末尾
107
108 Returns:
109 被删除的元素
110
111 Raises:
112 IndexError: 索引越界或数组为空
113 """
114 if self._size == 0:
115 raise IndexError('pop from empty array')
116
117 if index is None:
118 index = self._size - 1
119
120 if not 0 <= index < self._size:
121 raise IndexError('Index out of range')
122
123 value = self._data[index]
124
125 # 前移元素
126 for i in range(index, self._size - 1):
127 self._data[i] = self._data[i + 1]
128
129 self._data[self._size - 1] = None
130 self._size -= 1
131
132 # 缩容：当元素数量为容量的1/4时，缩容为1/2
133 if self._size > 0 and self._size == self._capacity // 4:
134 self._resize(self._capacity // 2)
135
136 return value
137
138 def _resize(self, new_capacity):
139 """调整容量
140
141 Args:
142 new_capacity: 新容量
143 """
144 new_data = [None] * new_capacity
145 for i in range(self._size):
146 new_data[i] = self._data[i]
147 self._data = new_data
148 self._capacity = new_capacity
149
150 def index(self, value):
151 """查找元素的索引
152
153 Args:
154 value: 要查找的元素
155
156 Returns:
157 元素索引
158
159 Raises:
160 ValueError: 元素不存在
161 """
162 for i in range(self._size):
163 if self._data[i] == value:
164 return i
165 raise ValueError(f'{value} not in array')
166
167 def is_empty(self):
168 """判断数组是否为空"""
169 return self._size == 0
170
171 def clear(self):
172 """清空数组"""
173 self._data = [None] * 4
174 self._size = 0
175 self._capacity = 4
176
177 def __str__(self):
178 """字符串表示"""
179 return '[' + ', '.join(str(self._data[i]) for i in range(self._size)) + ']'
180
181 def __repr__(self):
182 """调试表示"""
183 return f'DynamicArray({list(self._data[i] for i in range(self._size))})'
184
185
186def demo():
187 """演示动态数组的使用"""
188 print("=== 动态数组演示 ===\n")
189
190 # 创建数组
191 arr = DynamicArray()
192 print(f"创建空数组: {arr}")
193 print(f"容量: {arr._capacity}, 大小: {len(arr)}\n")
194
195 # 添加元素
196 print("添加元素: 1, 2, 3, 4, 5")
197 for i in range(1, 6):
198 arr.append(i)
199 print(f"数组: {arr}")
200 print(f"容量: {arr._capacity}, 大小: {len(arr)}\n")
201
202 # 继续添加触发扩容
203 print("继续添加元素: 6, 7, 8")
204 for i in range(6, 9):
205 arr.append(i)
206 print(f"数组: {arr}")
207 print(f"容量: {arr._capacity}, 大小: {len(arr)}\n")
208
209 # 访问元素
210 print(f"访问索引2: {arr[2]}")
211 print(f"修改索引2为99")
212 arr[2] = 99
213 print(f"数组: {arr}\n")
214
215 # 插入元素
216 print("在索引0插入100")
217 arr.insert(0, 100)
218 print(f"数组: {arr}\n")
219
220 # 删除元素
221 print("删除末尾元素")
222 removed = arr.pop()
223 print(f"删除的元素: {removed}")
224 print(f"数组: {arr}\n")
225
226 # 查找元素
227 print(f"查找元素99的索引: {arr.index(99)}\n")
228
229 # 删除多个元素触发缩容
230 print("删除多个元素...")
231 for _ in range(5):
232 arr.pop()
233 print(f"数组: {arr}")
234 print(f"容量: {arr._capacity}, 大小: {len(arr)}")
235
236
237if __name__ == '__main__':
238 demo()
239
链表实现
1"""
2单链表和双链表实现
3"""
4
5class ListNode:
6 """链表节点"""
7
8 def __init__(self, val=0, next=None):
9 self.val = val
10 self.next = next
11
12 def __str__(self):
13 return str(self.val)
14
15
16class LinkedList:
17 """单链表实现"""
18
19 def __init__(self):
20 """初始化"""
21 self._head = None
22 self._size = 0
23
24 def __len__(self):
25 """返回链表长度"""
26 return self._size
27
28 def is_empty(self):
29 """判断是否为空"""
30 return self._size == 0
31
32 def prepend(self, val):
33 """在头部添加节点
34
35 Args:
36 val: 节点值
37 """
38 new_node = ListNode(val, self._head)
39 self._head = new_node
40 self._size += 1
41
42 def append(self, val):
43 """在尾部添加节点
44
45 Args:
46 val: 节点值
47 """
48 if self._head is None:
49 self._head = ListNode(val)
50 else:
51 curr = self._head
52 while curr.next:
53 curr = curr.next
54 curr.next = ListNode(val)
55 self._size += 1
56
57 def insert(self, index, val):
58 """在指定位置插入节点
59
60 Args:
61 index: 插入位置
62 val: 节点值
63
64 Raises:
65 IndexError: 索引越界
66 """
67 if not 0 <= index <= self._size:
68 raise IndexError('Index out of range')
69
70 if index == 0:
71 self.prepend(val)
72 return
73
74 curr = self._head
75 for _ in range(index - 1):
76 curr = curr.next
77
78 curr.next = ListNode(val, curr.next)
79 self._size += 1
80
81 def remove(self, val):
82 """删除第一个匹配的节点
83
84 Args:
85 val: 要删除的值
86
87 Raises:
88 ValueError: 值不存在
89 """
90 if self._head is None:
91 raise ValueError(f'{val} not in list')
92
93 # 删除头节点
94 if self._head.val == val:
95 self._head = self._head.next
96 self._size -= 1
97 return
98
99 # 删除其他节点
100 curr = self._head
101 while curr.next:
102 if curr.next.val == val:
103 curr.next = curr.next.next
104 self._size -= 1
105 return
106 curr = curr.next
107
108 raise ValueError(f'{val} not in list')
109
110 def pop(self, index=None):
111 """删除并返回指定位置的节点值
112
113 Args:
114 index: 索引，默认为尾部
115
116 Returns:
117 节点值
118
119 Raises:
120 IndexError: 索引越界或链表为空
121 """
122 if self._head is None:
123 raise IndexError('pop from empty list')
124
125 if index is None:
126 index = self._size - 1
127
128 if not 0 <= index < self._size:
129 raise IndexError('Index out of range')
130
131 # 删除头节点
132 if index == 0:
133 val = self._head.val
134 self._head = self._head.next
135 self._size -= 1
136 return val
137
138 # 删除其他节点
139 curr = self._head
140 for _ in range(index - 1):
141 curr = curr.next
142
143 val = curr.next.val
144 curr.next = curr.next.next
145 self._size -= 1
146 return val
147
148 def find(self, val):
149 """查找值的索引
150
151 Args:
152 val: 要查找的值
153
154 Returns:
155 索引
156
157 Raises:
158 ValueError: 值不存在
159 """
160 curr = self._head
161 index = 0
162 while curr:
163 if curr.val == val:
164 return index
165 curr = curr.next
166 index += 1
167 raise ValueError(f'{val} not in list')
168
169 def reverse(self):
170 """反转链表"""
171 prev = None
172 curr = self._head
173 while curr:
174 next_node = curr.next
175 curr.next = prev
176 prev = curr
177 curr = next_node
178 self._head = prev
179
180 def to_list(self):
181 """转换为Python列表"""
182 result = []
183 curr = self._head
184 while curr:
185 result.append(curr.val)
186 curr = curr.next
187 return result
188
189 def __str__(self):
190 """字符串表示"""
191 return ' -> '.join(str(val) for val in self.to_list()) + ' -> None'
192
193
194# 双链表节点
195class DListNode:
196 """双链表节点"""
197
198 def __init__(self, val=0, prev=None, next=None):
199 self.val = val
200 self.prev = prev
201 self.next = next
202
203
204class DoublyLinkedList:
205 """双链表实现"""
206
207 def __init__(self):
208 """初始化"""
209 self._head = None
210 self._tail = None
211 self._size = 0
212
213 def __len__(self):
214 """返回链表长度"""
215 return self._size
216
217 def is_empty(self):
218 """判断是否为空"""
219 return self._size == 0
220
221 def prepend(self, val):
222 """在头部添加节点"""
223 new_node = DListNode(val, None, self._head)
224 if self._head is None:
225 self._head = self._tail = new_node
226 else:
227 self._head.prev = new_node
228 self._head = new_node
229 self._size += 1
230
231 def append(self, val):
232 """在尾部添加节点"""
233 new_node = DListNode(val, self._tail, None)
234 if self._tail is None:
235 self._head = self._tail = new_node
236 else:
237 self._tail.next = new_node
238 self._tail = new_node
239 self._size += 1
240
241 def pop_front(self):
242 """删除并返回头节点值"""
243 if self._head is None:
244 raise IndexError('pop from empty list')
245
246 val = self._head.val
247 self._head = self._head.next
248 if self._head:
249 self._head.prev = None
250 else:
251 self._tail = None
252 self._size -= 1
253 return val
254
255 def pop_back(self):
256 """删除并返回尾节点值"""
257 if self._tail is None:
258 raise IndexError('pop from empty list')
259
260 val = self._tail.val
261 self._tail = self._tail.prev
262 if self._tail:
263 self._tail.next = None
264 else:
265 self._head = None
266 self._size -= 1
267 return val
268
269 def to_list(self):
270 """转换为Python列表"""
271 result = []
272 curr = self._head
273 while curr:
274 result.append(curr.val)
275 curr = curr.next
276 return result
277
278 def __str__(self):
279 """字符串表示"""
280 return ' <-> '.join(str(val) for val in self.to_list())
281
282
283def demo():
284 """演示链表的使用"""
285 print("=== 单链表演示 ===\n")
286
287 # 创建链表
288 ll = LinkedList()
289 print(f"创建空链表: {ll}\n")
290
291 # 添加元素
292 print("尾部添加: 1, 2, 3")
293 for i in range(1, 4):
294 ll.append(i)
295 print(f"链表: {ll}\n")
296
297 # 头部添加
298 print("头部添加: 0")
299 ll.prepend(0)
300 print(f"链表: {ll}\n")
301
302 # 插入
303 print("在索引2插入99")
304 ll.insert(2, 99)
305 print(f"链表: {ll}\n")
306
307 # 查找
308 print(f"查找99的索引: {ll.find(99)}\n")
309
310 # 删除
311 print("删除元素99")
312 ll.remove(99)
313 print(f"链表: {ll}\n")
314
315 # 反转
316 print("反转链表")
317 ll.reverse()
318 print(f"链表: {ll}\n")
319
320 print("\n=== 双链表演示 ===\n")
321
322 # 创建双链表
323 dll = DoublyLinkedList()
324 print(f"创建空双链表\n")
325
326 # 添加元素
327 print("尾部添加: 1, 2, 3")
328 for i in range(1, 4):
329 dll.append(i)
330 print(f"双链表: {dll}\n")
331
332 # 头部添加
333 print("头部添加: 0")
334 dll.prepend(0)
335 print(f"双链表: {dll}\n")
336
337 # 头部删除
338 print(f"头部删除: {dll.pop_front()}")
339 print(f"双链表: {dll}\n")
340
341 # 尾部删除
342 print(f"尾部删除: {dll.pop_back()}")
343 print(f"双链表: {dll}")
344
345
346if __name__ == '__main__':
347 demo()
348
C++ 实现
数组实现
1/**
2 * 动态数组实现
3 * 支持自动扩容和缩容
4 */
5
6#include <iostream>
7#include <stdexcept>
8
9template<typename T>
10class DynamicArray {
11private:
12 T* data;
13 int size;
14 int capacity;
15
16 void resize(int newCapacity) {
17 T* newData = new T[newCapacity];
18 for (int i = 0; i < size; i++) {
19 newData[i] = data[i];
20 }
21 delete[] data;
22 data = newData;
23 capacity = newCapacity;
24 }
25
26public:
27 // 构造函数
28 DynamicArray(int initialCapacity = 4)
29 : size(0), capacity(initialCapacity) {
30 data = new T[capacity];
31 }
32
33 // 析构函数
34 ~DynamicArray() {
35 delete[] data;
36 }
37
38 // 拷贝构造函数
39 DynamicArray(const DynamicArray& other)
40 : size(other.size), capacity(other.capacity) {
41 data = new T[capacity];
42 for (int i = 0; i < size; i++) {
43 data[i] = other.data[i];
44 }
45 }
46
47 // 赋值运算符
48 DynamicArray& operator=(const DynamicArray& other) {
49 if (this != &other) {
50 delete[] data;
51 size = other.size;
52 capacity = other.capacity;
53 data = new T[capacity];
54 for (int i = 0; i < size; i++) {
55 data[i] = other.data[i];
56 }
57 }
58 return *this;
59 }
60
61 // 获取大小
62 int getSize() const {
63 return size;
64 }
65
66 // 获取容量
67 int getCapacity() const {
68 return capacity;
69 }
70
71 // 是否为空
72 bool isEmpty() const {
73 return size == 0;
74 }
75
76 // 访问元素
77 T& operator[](int index) {
78 if (index < 0 || index >= size) {
79 throw std::out_of_range("Index out of range");
80 }
81 return data[index];
82 }
83
84 const T& operator[](int index) const {
85 if (index < 0 || index >= size) {
86 throw std::out_of_range("Index out of range");
87 }
88 return data[index];
89 }
90
91 // 尾部添加
92 void append(const T& val) {
93 if (size == capacity) {
94 resize(2 * capacity);
95 }
96 data[size++] = val;
97 }
98
99 // 指定位置插入
100 void insert(int index, const T& val) {
101 if (index < 0 || index > size) {
102 throw std::out_of_range("Index out of range");
103 }
104
105 if (size == capacity) {
106 resize(2 * capacity);
107 }
108
109 for (int i = size; i > index; i--) {
110 data[i] = data[i - 1];
111 }
112 data[index] = val;
113 size++;
114 }
115
116 // 删除元素
117 void remove(const T& val) {
118 for (int i = 0; i < size; i++) {
119 if (data[i] == val) {
120 pop(i);
121 return;
122 }
123 }
124 throw std::runtime_error("Value not found");
125 }
126
127 // 删除指定位置
128 T pop(int index = -1) {
129 if (isEmpty()) {
130 throw std::runtime_error("Pop from empty array");
131 }
132
133 if (index == -1) {
134 index = size - 1;
135 }
136
137 if (index < 0 || index >= size) {
138 throw std::out_of_range("Index out of range");
139 }
140
141 T val = data[index];
142
143 for (int i = index; i < size - 1; i++) {
144 data[i] = data[i + 1];
145 }
146 size--;
147
148 // 缩容
149 if (size > 0 && size == capacity / 4) {
150 resize(capacity / 2);
151 }
152
153 return val;
154 }
155
156 // 查找索引
157 int find(const T& val) const {
158 for (int i = 0; i < size; i++) {
159 if (data[i] == val) {
160 return i;
161 }
162 }
163 return -1;
164 }
165
166 // 清空
167 void clear() {
168 size = 0;
169 capacity = 4;
170 delete[] data;
171 data = new T[capacity];
172 }
173
174 // 打印
175 void print() const {
176 std::cout << "[";
177 for (int i = 0; i < size; i++) {
178 std::cout << data[i];
179 if (i < size - 1) std::cout << ", ";
180 }
181 std::cout << "]" << std::endl;
182 }
183};
184
185
186// 演示
187int main() {
188 std::cout << "=== 动态数组演示 ===" << std::endl << std::endl;
189
190 DynamicArray<int> arr;
191 std::cout << "创建空数组" << std::endl;
192 std::cout << "容量: " << arr.getCapacity()
193 << ", 大小: " << arr.getSize() << std::endl << std::endl;
194
195 // 添加元素
196 std::cout << "添加元素: 1, 2, 3, 4, 5" << std::endl;
197 for (int i = 1; i <= 5; i++) {
198 arr.append(i);
199 }
200 std::cout << "数组: ";
201 arr.print();
202 std::cout << "容量: " << arr.getCapacity()
203 << ", 大小: " << arr.getSize() << std::endl << std::endl;
204
205 // 继续添加触发扩容
206 std::cout << "继续添加: 6, 7, 8" << std::endl;
207 for (int i = 6; i <= 8; i++) {
208 arr.append(i);
209 }
210 std::cout << "数组: ";
211 arr.print();
212 std::cout << "容量: " << arr.getCapacity()
213 << ", 大小: " << arr.getSize() << std::endl << std::endl;
214
215 // 访问和修改
216 std::cout << "访问索引2: " << arr[2] << std::endl;
217 arr[2] = 99;
218 std::cout << "修改索引2为99" << std::endl;
219 std::cout << "数组: ";
220 arr.print();
221 std::cout << std::endl;
222
223 // 插入
224 std::cout << "在索引0插入100" << std::endl;
225 arr.insert(0, 100);
226 std::cout << "数组: ";
227 arr.print();
228 std::cout << std::endl;
229
230 // 删除
231 std::cout << "删除末尾元素: " << arr.pop() << std::endl;
232 std::cout << "数组: ";
233 arr.print();
234 std::cout << std::endl;
235
236 // 查找
237 int index = arr.find(99);
238 std::cout << "查找元素99的索引: " << index << std::endl << std::endl;
239
240 // 删除多个元素
241 std::cout << "删除多个元素..." << std::endl;
242 for (int i = 0; i < 5; i++) {
243 arr.pop();
244 }
245 std::cout << "数组: ";
246 arr.print();
247 std::cout << "容量: " << arr.getCapacity()
248 << ", 大小: " << arr.getSize() << std::endl;
249
250 return 0;
251}
链表实现
1/**
2 * 单链表和双链表实现
3 */
4
5#include <iostream>
6#include <stdexcept>
7
8// 单链表节点
9template<typename T>
10struct ListNode {
11 T val;
12 ListNode* next;
13
14 ListNode(T v) : val(v), next(nullptr) {}
15};
16
17// 单链表
18template<typename T>
19class LinkedList {
20private:
21 ListNode<T>* head;
22 int size;
23
24public:
25 LinkedList() : head(nullptr), size(0) {}
26
27 ~LinkedList() {
28 clear();
29 }
30
31 int getSize() const {
32 return size;
33 }
34
35 bool isEmpty() const {
36 return size == 0;
37 }
38
39 // 头部添加
40 void prepend(const T& val) {
41 ListNode<T>* newNode = new ListNode<T>(val);
42 newNode->next = head;
43 head = newNode;
44 size++;
45 }
46
47 // 尾部添加
48 void append(const T& val) {
49 if (head == nullptr) {
50 head = new ListNode<T>(val);
51 } else {
52 ListNode<T>* curr = head;
53 while (curr->next) {
54 curr = curr->next;
55 }
56 curr->next = new ListNode<T>(val);
57 }
58 size++;
59 }
60
61 // 插入
62 void insert(int index, const T& val) {
63 if (index < 0 || index > size) {
64 throw std::out_of_range("Index out of range");
65 }
66
67 if (index == 0) {
68 prepend(val);
69 return;
70 }
71
72 ListNode<T>* curr = head;
73 for (int i = 0; i < index - 1; i++) {
74 curr = curr->next;
75 }
76
77 ListNode<T>* newNode = new ListNode<T>(val);
78 newNode->next = curr->next;
79 curr->next = newNode;
80 size++;
81 }
82
83 // 删除
84 void remove(const T& val) {
85 if (head == nullptr) {
86 throw std::runtime_error("Remove from empty list");
87 }
88
89 // 删除头节点
90 if (head->val == val) {
91 ListNode<T>* temp = head;
92 head = head->next;
93 delete temp;
94 size--;
95 return;
96 }
97
98 // 删除其他节点
99 ListNode<T>* curr = head;
100 while (curr->next) {
101 if (curr->next->val == val) {
102 ListNode<T>* temp = curr->next;
103 curr->next = curr->next->next;
104 delete temp;
105 size--;
106 return;
107 }
108 curr = curr->next;
109 }
110
111 throw std::runtime_error("Value not found");
112 }
113
114 // 反转
115 void reverse() {
116 ListNode<T>* prev = nullptr;
117 ListNode<T>* curr = head;
118 while (curr) {
119 ListNode<T>* next = curr->next;
120 curr->next = prev;
121 prev = curr;
122 curr = next;
123 }
124 head = prev;
125 }
126
127 // 查找
128 int find(const T& val) const {
129 ListNode<T>* curr = head;
130 int index = 0;
131 while (curr) {
132 if (curr->val == val) {
133 return index;
134 }
135 curr = curr->next;
136 index++;
137 }
138 return -1;
139 }
140
141 // 清空
142 void clear() {
143 while (head) {
144 ListNode<T>* temp = head;
145 head = head->next;
146 delete temp;
147 }
148 size = 0;
149 }
150
151 // 打印
152 void print() const {
153 ListNode<T>* curr = head;
154 while (curr) {
155 std::cout << curr->val;
156 if (curr->next) std::cout << " -> ";
157 curr = curr->next;
158 }
159 std::cout << " -> NULL" << std::endl;
160 }
161};
162
163
164// 双链表节点
165template<typename T>
166struct DListNode {
167 T val;
168 DListNode* prev;
169 DListNode* next;
170
171 DListNode(T v) : val(v), prev(nullptr), next(nullptr) {}
172};
173
174// 双链表
175template<typename T>
176class DoublyLinkedList {
177private:
178 DListNode<T>* head;
179 DListNode<T>* tail;
180 int size;
181
182public:
183 DoublyLinkedList() : head(nullptr), tail(nullptr), size(0) {}
184
185 ~DoublyLinkedList() {
186 clear();
187 }
188
189 int getSize() const {
190 return size;
191 }
192
193 bool isEmpty() const {
194 return size == 0;
195 }
196
197 // 头部添加
198 void prepend(const T& val) {
199 DListNode<T>* newNode = new DListNode<T>(val);
200 if (head == nullptr) {
201 head = tail = newNode;
202 } else {
203 newNode->next = head;
204 head->prev = newNode;
205 head = newNode;
206 }
207 size++;
208 }
209
210 // 尾部添加
211 void append(const T& val) {
212 DListNode<T>* newNode = new DListNode<T>(val);
213 if (tail == nullptr) {
214 head = tail = newNode;
215 } else {
216 newNode->prev = tail;
217 tail->next = newNode;
218 tail = newNode;
219 }
220 size++;
221 }
222
223 // 头部删除
224 T popFront() {
225 if (head == nullptr) {
226 throw std::runtime_error("Pop from empty list");
227 }
228
229 T val = head->val;
230 DListNode<T>* temp = head;
231 head = head->next;
232 if (head) {
233 head->prev = nullptr;
234 } else {
235 tail = nullptr;
236 }
237 delete temp;
238 size--;
239 return val;
240 }
241
242 // 尾部删除
243 T popBack() {
244 if (tail == nullptr) {
245 throw std::runtime_error("Pop from empty list");
246 }
247
248 T val = tail->val;
249 DListNode<T>* temp = tail;
250 tail = tail->prev;
251 if (tail) {
252 tail->next = nullptr;
253 } else {
254 head = nullptr;
255 }
256 delete temp;
257 size--;
258 return val;
259 }
260
261 // 清空
262 void clear() {
263 while (head) {
264 DListNode<T>* temp = head;
265 head = head->next;
266 delete temp;
267 }
268 tail = nullptr;
269 size = 0;
270 }
271
272 // 打印
273 void print() const {
274 DListNode<T>* curr = head;
275 while (curr) {
276 std::cout << curr->val;
277 if (curr->next) std::cout << " <-> ";
278 curr = curr->next;
279 }
280 std::cout << std::endl;
281 }
282};
283
284
285// 演示
286int main() {
287 std::cout << "=== 单链表演示 ===" << std::endl << std::endl;
288
289 LinkedList<int> ll;
290
291 std::cout << "尾部添加: 1, 2, 3" << std::endl;
292 for (int i = 1; i <= 3; i++) {
293 ll.append(i);
294 }
295 std::cout << "链表: ";
296 ll.print();
297 std::cout << std::endl;
298
299 std::cout << "头部添加: 0" << std::endl;
300 ll.prepend(0);
301 std::cout << "链表: ";
302 ll.print();
303 std::cout << std::endl;
304
305 std::cout << "在索引2插入99" << std::endl;
306 ll.insert(2, 99);
307 std::cout << "链表: ";
308 ll.print();
309 std::cout << std::endl;
310
311 std::cout << "反转链表" << std::endl;
312 ll.reverse();
313 std::cout << "链表: ";
314 ll.print();
315 std::cout << std::endl;
316
317 std::cout << "=== 双链表演示 ===" << std::endl << std::endl;
318
319 DoublyLinkedList<int> dll;
320
321 std::cout << "尾部添加: 1, 2, 3" << std::endl;
322 for (int i = 1; i <= 3; i++) {
323 dll.append(i);
324 }
325 std::cout << "双链表: ";
326 dll.print();
327 std::cout << std::endl;
328
329 std::cout << "头部添加: 0" << std::endl;
330 dll.prepend(0);
331 std::cout << "双链表: ";
332 dll.print();
333 std::cout << std::endl;
334
335 std::cout << "头部删除: " << dll.popFront() << std::endl;
336 std::cout << "双链表: ";
337 dll.print();
338 std::cout << std::endl;
339
340 std::cout << "尾部删除: " << dll.popBack() << std::endl;
341 std::cout << "双链表: ";
342 dll.print();
343
344 return 0;
345}