算法与数据结构入门：复杂度、数组与链表

摘要

算法和数据结构是编程能力的基础。很多性能问题并不是由语言本身造成的，而是因为没有根据数据规模选择合适的数据结构，或者忽略了算法的时间和空间复杂度。

本文从复杂度分析开始，介绍数组、动态数组和链表的基本结构、访问与插入特点，并通过 Python 实现简单的数据结构和常见操作，为后续学习栈、队列、树、图和排序算法建立基础。

一、背景与问题

同一个功能可以有不同实现。例如，从一组数据中判断某个元素是否存在：

items=["A","B","C","D"]target="D"print(targetinitems)

当数据量很小时，不同实现之间的差异不明显；当数据量达到百万甚至更大时，查找、插入和删除的成本会直接影响响应时间。

常见问题包括：

• 只关注代码能否运行，不分析数据规模。
• 对列表头部频繁插入和删除，导致性能下降。
• 用线性查找处理本可以使用哈希结构的数据。
• 递归深度、内存占用和最坏情况被忽略。
• 复杂度分析停留在术语层面，没有联系实际操作。

算法学习的第一步不是背诵公式，而是理解数据结构如何组织数据，以及每个操作需要移动、比较或访问多少元素。

二、核心概念

1. 时间复杂度

时间复杂度描述输入规模增长时，算法执行步骤如何增长。常见复杂度如下：

复杂度通常关注增长趋势，不强调常数项和低阶项。例如3n + 10通常记为O(n)。

2. 空间复杂度

空间复杂度描述算法额外使用的内存。输入数据本身占用的空间通常不计入额外空间，但复制数组、递归栈和辅助哈希表需要计入。

时间和空间经常需要权衡：

使用更多内存建立索引 → 查询速度更快 减少额外内存 → 可能需要重复扫描数据

3. 数组

数组将元素存放在连续或逻辑连续的位置，并通过下标访问：

index: 0 1 2 3 value: 10 20 30 40

数组的特点：

• 按下标访问通常是O(1)。
• 尾部追加通常成本较低。
• 中间插入和删除需要移动元素。
• 适合随机访问和批量遍历。

4. 动态数组

Python 的list是动态数组。当容量不足时，运行时会申请更大的空间并复制元素。扩容策略通常让连续追加的均摊复杂度接近O(1)，但单次扩容可能需要O(n)。

5. 链表

链表由节点组成，每个节点保存数据和下一个节点的引用：

head │ ▼ [10 | next] → [20 | next] → [30 | None]

链表不要求节点连续存储。已知节点位置时，插入和删除可以只修改引用；但按下标查找需要从头遍历，通常是O(n)。

三、工作原理

1. 操作复杂度对比

表格中的复杂度描述的是典型情况，实际结果还会受到缓存、内存布局和实现细节影响。

2. 为什么数组访问是O(1)？

如果数组首地址为base，每个元素占用size字节，那么第i个元素的地址可以近似计算为：

address(i) = base + i × size

因此不需要从第一个元素逐个查找。

3. 为什么链表按下标访问是O(n)？

单向链表只有当前节点指向下一个节点的引用。要找到第i个节点，通常必须从头节点开始逐个跳转，最多访问i + 1个节点。

4. 均摊复杂度

动态数组偶尔需要扩容，但大多数追加操作不需要移动已有元素。把一系列操作的总成本平均到每次操作上，就得到均摊复杂度。

理解均摊复杂度后，可以解释为什么 Python 列表连续append通常表现良好，但在头部频繁insert仍然不适合。

四、实战示例

1. 数组和列表操作

numbers=[10,20,30,40]print(numbers[2])numbers.append(50)numbers[1]=25print(numbers)

通过下标访问和修改不需要遍历整个列表。

2. 头部操作的差异

fromcollectionsimportdeque items=[2,3,4]items.insert(0,1)print(items)queue=deque([2,3,4])queue.appendleft(1)print(queue)

如果需要频繁从两端插入和删除，deque通常比列表更合适。数据结构选择应由操作模式决定。

3. 实现单向链表

from__future__importannotationsfromdataclassesimportdataclass@dataclassclassNode:value:intnext:Node|None=NoneclassSinglyLinkedList:def__init__(self)->None:self.head:Node|None=Noneself.tail:Node|None=Noneself.size=0defappend(self,value:int)->None:node=Node(value)ifself.headisNone:self.head=self.tail=nodeelse:assertself.tailisnotNoneself.tail.next=node self.tail=node self.size+=1defvalues(self)->list[int]:result:list[int]=[]current=self.headwhilecurrentisnotNone:result.append(current.value)current=current.nextreturnresult

保存尾指针后，链表尾部追加可以避免每次从头遍历。

4. 删除第一个匹配节点

defremove_first(self,value:int)->bool:previous:Node|None=Nonecurrent=self.headwhilecurrentisnotNone:ifcurrent.value==value:ifpreviousisNone:self.head=current.nextelse:previous.next=current.nextifcurrentisself.tail:self.tail=previous self.size-=1returnTrueprevious=current current=current.nextreturnFalse

查找目标节点需要O(n)，找到后修改引用本身是O(1)。

5. 线性查找与二分查找

deflinear_search(values:list[int],target:int)->int:forindex,valueinenumerate(values):ifvalue==target:returnindexreturn-1defbinary_search(values:list[int],target:int)->int:left,right=0,len(values)-1whileleft<=right:middle=(left+right)//2ifvalues[middle]==target:returnmiddleifvalues[middle]<target:left=middle+1else:right=middle-1return-1

二分查找要求数据已经有序。它通过每次排除一半候选区间，将查找复杂度从O(n)降低到O(log n)。

6. 复杂度测试

fromtimeitimporttimeit values=list(range(100_000))linear_time=timeit(lambda:linear_search(values,99_999),number=100,)binary_time=timeit(lambda:binary_search(values,99_999),number=100,)print("linear:",linear_time)print("binary:",binary_time)

基准测试只能说明当前实现、数据和机器上的表现，不能代替复杂度分析，但可以帮助发现实现错误和明显的性能差异。

7. 使用集合优化存在性判断

allowed_users={"u001","u002","u003"}user_id="u002"ifuser_idinallowed_users:print("allowed")

集合通常使用哈希结构，平均情况下成员判断接近O(1)。如果只需要判断是否存在，不必每次在线性列表中扫描。

五、常见问题与实践建议

1.O(1)是否表示一定很快？

不一定。复杂度描述增长趋势，不代表常数开销为零。一个常数很大的O(1)操作，在小数据和特定硬件上可能慢于简单的O(n)操作。

2. 为什么列表中间插入较慢？

因为插入位置后面的元素通常需要整体向后移动，为新元素腾出空间，移动数量随列表长度增长。

3. 什么时候使用链表？

链表适合需要频繁在已知节点位置插入和删除、且不依赖随机访问的场景。实际 Python 业务中，很多队列场景使用deque已经足够，不需要手写链表。

4. 二分查找为什么返回错误结果？

优先检查：

• 输入是否已经按同一规则排序。
• left和right的边界是否一致。
• 找到目标后是否及时返回。
• 更新边界时是否排除了已经检查过的中间位置。

5. 复杂度分析需要考虑最坏情况吗？

通常需要。平均复杂度有助于描述常见表现，但权限、支付、任务调度等关键路径更应该关注最坏情况和资源上限。

六、进阶思考

1. 数据结构选择应从操作开始

先列出核心操作，再选择结构：

需要按下标随机访问 → 数组 / 动态数组 需要两端进出 → deque 需要快速判断是否存在 → set 需要键值映射 → dict 需要优先处理最小或最大元素 → heap

不要因为某个结构“更高级”就使用它，操作模式才是选择依据。

2. 理论复杂度与实际性能

真实性能还会受缓存局部性、内存分配、解释器开销、数据分布和并发影响。连续数组通常更利于缓存访问，链式结构则可能因为节点分散而产生额外开销。

3. 不变量

实现数据结构时，要为每个操作维护不变量。例如单向链表需要保证：

• 空链表的head和tail状态一致。
• tail.next始终为None。
• size与实际节点数量一致。
• 删除最后一个节点后，head和tail都正确更新。

不变量比记住某段代码更重要，因为它能指导边界情况处理。

4. 为算法增加测试

至少测试：

• 空数组或空链表。
• 只有一个元素。
• 目标在头部、中间和尾部。
• 目标不存在。
• 重复值。
• 删除后结构为空。

算法代码短，并不代表边界条件少。

结论

算法学习的基础是理解复杂度和数据结构操作成本。数组适合随机访问，链表适合已知节点位置的连接调整，列表、deque、集合和字典分别对应不同的操作模式。

后续可以继续学习栈与队列、哈希表、递归与回溯、树和图、排序与动态规划，并在每个主题中坚持分析时间复杂度、空间复杂度和边界条件。

参考资料

1. Python 官方文档：https://docs.python.org/3/
2. CPythonlist数据结构文档：https://docs.python.org/3/tutorial/datastructures.html
3. Introduction to Algorithms：https://mitpress.mit.edu/9780262046305/introduction-to-algorithms/