algo02 数组、链表与哈希表 — exercise.py 练习指南

Download exercise.py

练习目标

通过四个递进任务的实现，深入掌握数组、链表和哈希表的底层操作。

任务清单

任务1：补全动态数组的 insert/delete

在 DynamicArray 类中实现 insert() 和 delete() 方法。

insert 算法：

检查索引合法性 0 <= index <= size
若 size == capacity，调用 _resize(capacity * 2)
for i in range(size, index, -1): data[i] = data[i-1]（元素后移）
data[index] = value、size += 1

delete 算法：

检查索引合法性 0 <= index < size
for i in range(index, size-1): data[i] = data[i+1]（元素前移）
data[size-1] = None、size -= 1

任务2：实现双链表的 remove_node

关键：利用 prev 和 next 指针，在 O(1) 时间内删除任意节点。

需要考虑四种边界情况：

头节点（node.prev is None）→ 更新 self.head
尾节点（node.next is None）→ 更新 self.tail
中间节点 → 前后节点互连
不要忘记 size -= 1

任务3：实现开放地址法哈希表

使用线性探测实现 put、get、remove。

关键概念——墓碑（Tombstone）：

删除时不能设为 None（会切断探测链！）
必须用特殊标记 TOMBSTONE 替代
put 时可以复用 TOMBSTONE 位置
get 时遇到 TOMBSTONE 继续探测

任务4（Bonus）：实现 LRU 缓存

使用 dict + DoublyLinkedList 实现 O(1) 的 get/put。

核心思路：哈希表负责快速定位（O(1)），双链表维护访问顺序。

验证标准

bash

cd algo02_arrays_linkedlist_hash/code
python exercise.py

期望输出：四个任务的 ✅ 通过 信息和 🎉 所有练习已完成！

完整代码

# -*- coding: utf-8 -*-
"""
===============================================================================
algo02_arrays_linkedlist_hash/code/exercise.py — 数组、链表与哈希表练习
===============================================================================
本练习文件中，你需要完成以下任务：
  1. 补全动态数组的 insert 和 delete 方法
  2. 实现双链表指定节点的删除操作
  3. 实现哈希表的 get/put/remove（开放地址法版本）
  4. 实现一个简易的 LRU 缓存（Bonus）

运行方式：python exercise.py
===============================================================================
"""

import time


# ============================================================================
# 任务 1：补全动态数组
# ============================================================================

class DynamicArray:
    """动态数组（待补全）"""

    def __init__(self):
        self._capacity = 2
        self._size = 0
        self._data = [None] * 2

    def append(self, value):
        if self._size == self._capacity:
            self._resize(self._capacity * 2)
        self._data[self._size] = value
        self._size += 1

    def _resize(self, new_capacity):
        new_data = [None] * new_capacity
        for i in range(self._size):
            new_data[i] = self._data[i]
        self._data = new_data
        self._capacity = new_capacity

    # TODO: 实现 insert 方法 —— 在指定位置插入元素
    # 1. 检查索引合法性（0 <= index <= size）
    # 2. 若容量已满，先扩容
    # 3. 将 index 及之后的元素向后移动一位
    # 4. 在 index 处赋值，size += 1
    def insert(self, index, value):
        # TODO: 你的代码从这里开始
        if index < 0 or index > self._size:
            raise IndexError('索引越界')
        if self._size == self._capacity:
            self._resize(self._capacity * 2)
        # 将 index 之后的元素向后移动
        for i in range(self._size, index, -1):
            self._data[i] = self._data[i - 1]
        self._data[index] = value
        self._size += 1

    # TODO: 实现 delete 方法 —— 删除指定位置的元素
    # 1. 检查索引合法性（0 <= index < size）
    # 2. 将 index 之后的元素向前移动一位
    # 3. 将最后一个元素清空，size -= 1
    def delete(self, index):
        # TODO: 你的代码从这里开始
        if index < 0 or index >= self._size:
            raise IndexError('索引越界')
        for i in range(index, self._size - 1):
            self._data[i] = self._data[i + 1]
        self._data[self._size - 1] = None
        self._size -= 1

    def __getitem__(self, index):
        if index < 0 or index >= self._size:
            raise IndexError('索引越界')
        return self._data[index]

    def __len__(self):
        return self._size

    def __repr__(self):
        return f'[{", ".join(str(self._data[i]) for i in range(self._size))}]'


# ============================================================================
# 任务 2：实现双链表删除操作
# ============================================================================

class DoublyNode:
    def __init__(self, data):
        self.data = data
        self.prev = None
        self.next = None


class DoublyLinkedList:
    """双链表（待补全）"""

    def __init__(self):
        self.head = None
        self.tail = None
        self._size = 0

    def append(self, data):
        new_node = DoublyNode(data)
        if self.tail is None:
            self.head = self.tail = new_node
        else:
            new_node.prev = self.tail
            self.tail.next = new_node
            self.tail = new_node
        self._size += 1

    # TODO: 实现 remove_node 方法 —— 在 O(1) 时间内删除指定节点
    # 提示：利用 prev 和 next 指针，考虑四种情况：
    #   1. node 是头节点（node.prev is None）→ 更新 self.head
    #   2. node 是尾节点（node.next is None）→ 更新 self.tail
    #   3. node 在中间 → 修改前后节点的指针
    #   4. 不要忘记 size -= 1
    def remove_node(self, node):
        # TODO: 你的代码从这里开始
        if node.prev:
            node.prev.next = node.next
        else:
            self.head = node.next
        if node.next:
            node.next.prev = node.prev
        else:
            self.tail = node.prev
        self._size -= 1

    def pop_tail(self):
        if self.tail is None:
            return None
        node = self.tail
        self.remove_node(node)
        return node

    def to_list(self):
        result = []
        cur = self.head
        while cur:
            result.append(cur.data)
            cur = cur.next
        return result

    def __len__(self):
        return self._size

    def __repr__(self):
        return f'DoublyLinkedList({self.to_list()})'


# ============================================================================
# 任务 3：实现开放地址法哈希表
# ============================================================================

class OpenAddressingHashTable:
    """开放地址法哈希表 —— 使用线性探测（待补全）

    每个槽存储 (key, value) 或 None（空槽）或 "TOMBSTONE"（已删除标记）
    """

    _TOMBSTONE = object()  # 墓碑标记

    def __init__(self, capacity=8):
        self._capacity = capacity
        self._size = 0
        self._table = [None] * capacity

    def _hash(self, key):
        return hash(key) % self._capacity

    # TODO: 实现 put 方法
    # 1. 从 h = hash(key) 开始，线性探测找到空槽（None 或 TOMBSTONE）
    # 2. 如果 key 已存在，更新 value
    # 3. 如果 key 不存在，插入到找到的空槽，size += 1
    # 4. 检查负载因子，必要时扩容
    def put(self, key, value):
        h = self._hash(key)
        first_tombstone = None

        for i in range(self._capacity):
            idx = (h + i) % self._capacity
            slot = self._table[idx]

            if slot is None:
                # 找到空槽
                insert_idx = first_tombstone if first_tombstone is not None else idx
                self._table[insert_idx] = (key, value)
                self._size += 1
                return
            elif slot == self._TOMBSTONE:
                if first_tombstone is None:
                    first_tombstone = idx
            elif slot[0] == key:
                # key 已存在，更新
                # 如果之前有墓碑标记，移到墓碑位置
                if first_tombstone is not None:
                    self._table[idx] = self._TOMBSTONE
                    self._table[first_tombstone] = (key, value)
                else:
                    self._table[idx] = (key, value)
                return

        # 表满（不应该发生，因为负载因子控制）
        self._resize(self._capacity * 2)
        self.put(key, value)

    # TODO: 实现 get 方法
    # 1. 从 h = hash(key) 开始线性探测
    # 2. 遇到 None（未探测到的位置）说明 key 不存在
    # 3. 遇到匹配的 key 返回 value
    # 4. 跳过 TOMBSTONE
    def get(self, key):
        h = self._hash(key)
        for i in range(self._capacity):
            idx = (h + i) % self._capacity
            slot = self._table[idx]
            if slot is None:
                return None
            if slot != self._TOMBSTONE and slot[0] == key:
                return slot[1]
        return None

    # TODO: 实现 remove 方法
    # 1. 找到 key 对应的槽
    # 2. 将其标记为 TOMBSTONE（不能设为 None！）
    # 3. size -= 1
    def remove(self, key):
        h = self._hash(key)
        for i in range(self._capacity):
            idx = (h + i) % self._capacity
            slot = self._table[idx]
            if slot is None:
                return False
            if slot != self._TOMBSTONE and slot[0] == key:
                self._table[idx] = self._TOMBSTONE
                self._size -= 1
                return True
        return False

    def _resize(self, new_capacity):
        old_table = self._table
        self._capacity = new_capacity
        self._table = [None] * new_capacity
        self._size = 0
        for slot in old_table:
            if slot is not None and slot != self._TOMBSTONE:
                self.put(slot[0], slot[1])

    def __len__(self):
        return self._size

    def __repr__(self):
        items = []
        for slot in self._table:
            if slot is not None and slot != self._TOMBSTONE:
                items.append(f'{slot[0]!r}: {slot[1]!r}')
        return 'OAHTable({' + ', '.join(items) + '})'


# ============================================================================
# 任务 4（Bonus）：实现 LRU 缓存
# ============================================================================

class LRUCache:
    """LRU 缓存（待补全——使用哈希表 + 双链表的组合）

    提示：
      - self.cache: dict，key → DoublyNode，提供 O(1) 查找
      - self.dll: DoublyLinkedList，维护访问顺序（头部=最近使用，尾部=最久未使用）
    """

    def __init__(self, capacity):
        self.capacity = capacity
        self.cache = {}
        self.dll = DoublyLinkedList()

    # TODO: 实现 get 方法
    def get(self, key):
        if key not in self.cache:
            return -1
        node = self.cache[key]
        # 1. 将该节点从当前位置移除
        self.dll.remove_node(node)
        # 2. 将该节点插入双链表头部
        self.dll.append(node.data)  # 注意：append 到尾部，但我们需要 prepend...
        # 实际上这里我们需要 prepend 到头部。而上面 DoublyLinkedList 的 append 是加到尾部的。
        # 简化处理：使用 append 作为「最近使用」的末尾
        # 或者正确实现 prepend
        # 这里我们利用 pop_tail 淘汰尾部
        self.cache[key] = self.dll.tail  # 尾部是最新的
        return node.data[1]

    # TODO: 实现 put 方法
    def put(self, key, value):
        if key in self.cache:
            # 更新已存在的 key
            node = self.cache[key]
            self.dll.remove_node(node)
        elif len(self.cache) >= self.capacity:
            # 淘汰最久未使用的（头部）
            if self.dll.head:
                old_node = self.dll.head
                self.dll.remove_node(old_node)
                del self.cache[old_node.data[0]]

        # 插入新节点到尾部的表示（作为最新使用）
        self.dll.append((key, value))
        self.cache[key] = self.dll.tail

    def __repr__(self):
        return f'LRUCache({self.dll.to_list()})'


# ============================================================================
# 主函数
# ============================================================================

def main():
    print('=' * 60)
    print('  数组、链表与哈希表 — 练习程序')
    print('=' * 60)

    # 测试任务 1
    print('\n--- 任务 1：动态数组 ---')
    da = DynamicArray()
    for i in range(5):
        da.append(i * 10)
    print(f'初始: {da}')
    da.insert(2, 99)
    print(f'在索引 2 插入 99: {da}')
    da.delete(3)
    print(f'删除索引 3: {da}')
    assert str(da) == '[0, 10, 99, 30, 40]', f'期望 [0, 10, 99, 30, 40] 实际 {da}'
    print('✅ 任务 1 通过！')

    # 测试任务 2
    print('\n--- 任务 2：双链表 ---')
    dll = DoublyLinkedList()
    dll.append('A'); dll.append('B'); dll.append('C')
    print(f'初始: {dll}')
    # 删除中间节点
    dll.remove_node(dll.head.next)  # 删除 B
    print(f'删除 B 后: {dll}')
    assert dll.to_list() == ['A', 'C'], f'期望 [A, C] 实际 {dll.to_list()}'
    print('✅ 任务 2 通过！')

    # 测试任务 3
    print('\n--- 任务 3：开放地址法哈希表 ---')
    oaht = OpenAddressingHashTable()
    oaht.put('x', 100); oaht.put('y', 200); oaht.put('z', 300)
    print(f'插入 3 个条目: {oaht}')
    print(f'get("y") = {oaht.get("y")}')
    oaht.remove('x')
    print(f'删除 "x" 后: {oaht}')
    print(f'get("x") 仍能正确返回 None? {oaht.get("x")}')
    assert oaht.get('y') == 200
    assert oaht.get('x') is None
    print('✅ 任务 3 通过！')

    # 测试任务 4
    print('\n--- 任务 4：LRU 缓存 ---')
    lru = LRUCache(2)
    lru.put(1, 1); lru.put(2, 2)
    print(f'put(1,1), put(2,2) 后: {lru}')
    print(f'get(1) = {lru.get(1)}')
    lru.put(3, 3)  # 淘汰 2
    print(f'put(3,3) 后: {lru}')
    print(f'get(2) = {lru.get(2)} (应该返回 -1)')
    assert lru.get(2) == -1
    print('✅ 任务 4 通过！')

    print('\n🎉 所有练习已完成！')


if __name__ == '__main__':
    main()

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
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
330
331
332
333
334
335
336
337
338
339
340
341
342
343
344
345
346
347
348
349
350
351
352
353
354
355
356
357
358
359
360
361
362
363
364
365
366
367
368
369
370
371
372
373
374
375
376
377
378
379
380

algo02 数组、链表与哈希表 — exercise.py 练习指南 ​

练习目标 ​

任务清单 ​

任务1：补全动态数组的 insert/delete ​

任务2：实现双链表的 remove_node ​

任务3：实现开放地址法哈希表 ​

任务4（Bonus）：实现 LRU 缓存 ​

验证标准 ​

完整代码 ​