3.1 – 链表引入
3.1.1 – 数组和链表的内存
在上一讲中我们使用数组实现了一个列表，数组访问速度快、内存布局紧凑，但它要求元素连续存储，并且创建后通常不能直接改变长度，因此在某些场景下存在限制。我们现在详细看看数组在内存中的存储方式。
- 首先，当你想在内存中存储一个整数，你必须事先声明，例如
int x;； - 当内存管理器读到这一行，就会在内存中寻找 4 字节的可用空间，并分配给 x 变量*；
- 内存块的地址是内存中第一个字节的地址，我们假设 x 使用的内存块的地址是 217，那么 x 变量就占用了地址为 217-220 这个四个字节；
- 然后你就可以为 x 赋值。
*需要说明的是，这是一个非常简化的说法，实际上编译器往往在编译时就已经确定它在栈帧中的位置，程序运行时只需要调整栈指针。真正比较接近“向内存管理器申请空间”的情况，是使用 malloc、calloc、realloc 等函数从堆中动态申请内存，但是这些内容不在我们目前的讨论范围内。
现在，如果你需要存储一个整形数组，长度为 4，也就是 int A[4]; 。
- 数组总是作为一个连续的内存块存储在内存中；
- 所以内存管理器就知道了它现在要寻找一个 16 字节的内存块给 A；
- 假设内存块的地址是 201，也就是 201-216 这 16 个字节的内存被分配给了整形数组 A。
假设你想给 A[3] 赋值为 2 的时候，因为知道基地址（起始地址），程序就可以计算出 A[3] 的地址，也就是 201+3*4 = 213。
也就是说对于数组来讲，无论大小如何，程序都可以在一个固定的时间内访问到任意一个元素。
此时，如果你想要往数组 A 中存储第五个元素，就需要扩容数组了。但是此时，内存管理器就会告诉你，A 所在的内存块之后的内存已经被分配，因此无法扩容。你只能告诉内存管理器一个你希望的新的大小，重新申请一块新的内存。
但是，这种做法面临的问题就是，如果需要扩容，就要进行全数组的复制操作。并且数组还存在着未使用的容量。
一种不要求元素连续存储、并且可以灵活增加和删除元素的数据结构是链表。
我们能做的事情就是每次只申请一个单位的内存，而不是一个内存块。加入我们想要存储几个数 6、5、4、2，因为是分开申请的，所以很可能得不到连续的内存块。
为了形成一个列表，我们需要把分散的内存块串联在一起。我们能做的就是，可以在每个块中都额外存储一些信息——下一个块的地址。
我们每次存储一个数的时候，都申请一个更大的内存块，记录要存储的值以及下一个内存块的地址。在最后一个内存块中，指针 0/NULL 表示不指向任何节点，作为列表的末尾。
例如在 C 中，可以定义一个 Node 结构体，包含 data 和 next 两个字段：
struct Node {
int data; // 4 字节
struct Node* next; // 大部分情况下 32 位架构 4 字节，64 位架构 8 字节
}
在常见计算机中，int 类型确实是 4 字节，但是 C 标准并没有规定必须是 4 字节，并且指针变量的大小也不一定就是 4/8 字节，可以通过 sizeof 获取实际大小。
3.1.2 – 链表操作的时间复杂度
链表不支持像数组一样根据下标进行 O(1) 的随机访问。
- 链表的第一项叫做首节点（Head），首节点可以让我们访问完整的链表。想要遍历链表，唯一的方式就是从头开始，所以链表的读取时间 T ∝ N。
- 访问第 k 个节点时，需要从头指针开始依次经过前面的节点，因此时间复杂度为 O(k)，最坏情况下为 O(N)。
对于插入/删除项，链表真正的插入/删除操作均为 O(1)，耗时的是寻找插入/删除的位置。
new_node->next = p->next;
p->next = new_node;
只需要单独创建一个 Node，得到这个新 Node 的地址，给前后节点正确修改节点的 next 的值就可以了。
- 虽然插入项的操作比数组更简单，但是因为仍然需要进行读取，所以时间复杂度依然是 O(N)。
- 相似地，从链表中删除任意某项的时间复杂度也是 O(N)，因为需要进行读取操作。
链表相较于数组有明显的好处，我们可以按需创建节点，也可以按需释放不需要的节点，不必像在数组中那样预测一个列表的大小。
3.2 – 链表 vs 数组
3.2.1 – 链表和数组哪个更好？
实际上不存在一个数据结构好于另一个数据结构的说法。对于不同的问题，每一种数据结构都有不同的表现。
上表中的链表不保存尾指针，如果维护尾指针，显然在末尾插入元素的操作复杂度为 O(1)。
当元素本身很大时，链表中指针所占的比例会相对降低。不过，这并不能直接说明链表比数组更节省空间。动态数组的额外空间主要来自尚未使用的容量，而链表还需要承担指针、内存对齐、内存分配器元数据和内存碎片等开销。具体哪种结构更节省内存，需要结合实际元素大小、元素数量和扩容策略判断。
如果元素本身很大，又不希望数组扩容时频繁复制大对象，可以让数组存储对象的指针，而不是直接存储对象：
LargeObject *array[100];
3.2.2 – 缓存局部性
虽然遍历数组和链表的理论时间复杂度都是 O(N)，但实际运行中，数组通常会明显更快。
- 数组中的元素是连续存储的，当程序访问某个元素时，CPU 通常会把它附近的整块数据一并加载到高速缓存中，因此顺序遍历数组非常快。
- 链表节点通常分散在内存中的不同位置。访问下一个节点时，CPU可能需要重新从主存读取数据，产生更多缓存未命中。
3.2.3 – 内存分配和内存泄露
我们在上表中提到，链表在 C/C++ 中实现难度较高，容易带来内存错误。
这是因为链表需要为每个节点单独申请和释放内存：
Node *node = malloc(sizeof(Node));
- 删除节点时必须进行 free，如果只修改指针却没有释放节点，就会造成内存泄漏。
- 如果释放节点之后仍继续访问它，则会造成悬空指针，可能造成段错误或未定义行为（如重复释放）。
3.3 – 总结
数组和链表不存在绝对的优劣。
- 数组支持 O(1) 的随机访问，内存布局紧凑，并具有良好的缓存局部性，适合频繁读取和按下标访问的场景。
- 链表不要求元素连续存储，可以灵活地增加和删除节点，在已经找到操作位置时，插入和删除只需要 O(1) 的指针修改。不过，链表不能快速地根据下标访问元素，并且需要承担指针、内存对齐和动态内存管理等额外开销。
适合使用数组的例子：
- 存储一周内每一天的温度：数据总量确定、常按编号读取、不插入或删除；
- 存储一个班级内学生的成绩：数据总量确定、常按编号读取、不插入或删除；
适合使用链表的例子：
- 不断在开头加入元素：假设程序不断接收新的日志，并且希望最新日志位于最前面，那么使用链表的时间复杂度是 O(1)；
- 在一个固定位置之后频繁插入/删除元素：链表的插入操作本身是 O(1)，只有读取的过程是 O(N)，适合“在第 100 个元素后插入 100 新元素”这种场景；
- 元素数量频繁变化，且难以预测的情况。
选择哪一种数据结构，应当根据程序中最常见的操作来决定。