一、学前花絮
数组（Array）和链表（linked List）是计算机科学中最基础、最核心的线性数据结构。理解它们的差异，就像是理解“火车”和“一列并排的房间”的区别一样。
1. 数组 (Array)：整齐的“一排房间”
想象一下酒店的一层楼，房间号是 0, 1, 2, 3... 这些房间在物理上是挨在一起的。数组就是这样，它在内存中占据一段连续的空间。因为这种连续性，我们可以通过“首地址 + 偏移量”直接计算出任意元素的位置。
缺点：
- 大小固定： 传统数组一旦定义，大小就无法改变（虽然现代语言如 Python 列表、Java ArrayList 提供了动态扩容，但这其实是通过申请新空间、拷贝旧数据实现的，会有性能损耗）。
- 插入/删除低效： 如果你想在中间插入一个新元素，后面所有的元素都要向后“挪一步”；删除时则都要向前“补位”。这非常耗时，时间复杂度是 O(n)。
2. 链表 (linked List)：灵活的“火车”
想象一列火车，车头连着车厢1，车厢1连着车厢2... 这些车厢在物理位置上不一定挨着，它们通过“挂钩”（指针）连接起来。链表的每个节点包含两部分：数据域（存数据）和指针域（存下一个节点的地址）。
单向链表： 只能从头走到尾。
循环链表： 尾巴连回了头，形成一个环。
缺点：
- 访问慢： 如果你想找第 1000 个元素，你不能直接跳过去，必须从车头开始，一个一个车厢找过去，时间复杂度是 O(n)。
- 额外空间开销： 每个节点都要额外存储指针信息，如果数据本身很小，指针的开销占比就会很大。
- 缓存不友好： 节点在内存中是零散分布的，遍历时 CPU 缓存命中率低，实际运行速度可能比数组慢。
1. 数组与列表比较
应该说Python 的 list 在使用体验上替代了 C 语言中数组的角色，但从底层实现来看，它其实是一种动态数组（Dynamic Array），而不是 C 语言那种纯粹的静态数组。
在 C 语言中，数组是“死”的；在 Python 中，List 是“活”的。
C 语言 (静态，需指定大小)：
arr[0] = 10; // 赋值 Python (动态，随用随取)：
如果在 Python 中需要链表，通常的做法是： # 定义节点 def __init__(self, val=0, next=None): self.next = next # 这里的 next 就是引用，相当于 C 的指针 class linkedList: self.head = None |
如果你需要的是链表那种“在头尾快速插入删除”的特性，Python 提供了 deque (双端队列)，它的底层是用双向链表实现的。
dq = deque([1, 2, 3]) dq.pop() # 在尾部快速弹出 |
Guido (Python 之父) 认为，99% 的场景下，动态数组 (List) 的性能已经足够好，且使用起来比链表简单得多。 只有在特定的高性能需求或算法题中，才需要手动处理链表。
在 Python 中，List 就是你平时干活用的“数组”；而链表通常是为了学习算法、或者在极少数需要极致插入性能时，才需要自己写或者用 deque 的东西。
2.3 示例
Python 代码说明：
None：相当于 C 语言中的 NULL，表示指针结束。
2.C语言实现链表
以上是 C 语言链表的标准范式：
- 定义结构体 (struct Node)。
- 动态申请 (malloc) 内存创建节点。
- 操作链表 (遍历、插入、删除)。
- 动态释放 (free) 内存回收资源。
我们从输出结果上看，C语言与python语言实现链表功能一样。但是二者还是有很大的区别：
三、小结
让我们保持学习热情，多做练习。我们下期再见！
快乐男孩
