数据结构从入门到精通二 ~ 数组和链表
1. 前言
在计算机科学和软件工程领域，数据结构是指在计算机中组织和存储数据的方式，数组和链表是其中最基础也是最常用的两种数据结构之一。
-
数组（Array）：是一种线性表数据结构，它使用连续的内存空间来存储一组相同类型的数据。数组提供了快速随机访问元素的能力，但插入和删除操作可能比较耗时，因为需要移动大量元素。
-
链表（Linked List）：也是一种线性表数据结构，但不同于数组，链表中的元素（节点）通过指针相互连接。每个节点包含数据和指向下一个节点的指针。链表支持快速插入和删除操作，但访问特定位置的元素时需要从头开始遍历，效率较低。
2. 内存结构
数组和链表这两种基础且重要的数据结构，它们分别代表了“连续存储”和“分散存储”两种物理结构。
物理结构在很大程度上决定了程序对内存和缓存的使用效率，进而影响算法程序的整体性能。
- 硬盘用于长期存储大量数据
- 内存用于临时存储程序运行中正在处理的数据
- 缓存则用于存储经常访问的数据和指令
内存是有限的，且同一块内存不能被多个程序共享，因此我们希望数据结构能够尽可能高效地利用空间。数组的元素紧密排列，不需要额外的空间来存储链表节点间的引用（指针），因此空间效率更高。然而，数组需要一次性分配足够的连续内存空间，这可能导致内存浪费，数组扩容也需要额外的时间和空间成本。
链表以“节点”为单位进行动态内存分配和回收，提供了更大的灵活性。
另一方面，在程序运行时，随着反复申请与释放内存，空闲内存的碎片化程度会越来越高，从而导致内存的利用效率降低。数组由于其连续的存储方式，相对不容易导致内存碎片化。相反，链表的元素是分散存储的，在频繁的插入与删除操作中，更容易导致内存碎片化。
“缓存未命中”越少，CPU 读写数据的效率就越高。
缓存的容量有限，只能存储一小部分频繁访问的数据，因此当 CPU 尝试访问的数据不在缓存中时，就会发生缓存未命中（cache miss），此时 CPU 不得不从速度较慢的内存中加载所需数据。
- 占用空间：链表元素比数组元素占用空间更多，导致缓存中容纳的有效数据量更少。
- 缓存行：链表数据分散在内存各处，而缓存是“按行加载”的，因此加载到无效数据的比例更高。
- 空间局部性：数组被存储在集中的内存空间中，因此被加载数据附近的数据更有可能即将被访问。
数组具有更高的缓存命中率，因此它在操作效率上通常优于链表。
如果数据量非常大、动态性很高、栈的预期大小难以估计，那么基于链表实现的栈更加合适。链表能够将大量数据分散存储于内存的不同部分，并且避免了数组扩容产生的额外开销。
程序运行时，数据主要存储在内存中。数组可提供更高的内存空间效率，而链表则在内存使用上更加灵活。
数组灵活性：栈上的数组的大小需要在编译时确定，而堆上的数组的大小可以在运行时动态确定。
数组实现额外支持随机访问，但这已超出了栈的定义范畴，因此一般不会用到。效率并不高。