一般来说，数组被认为是一种在编译时大小固定的数据结构，数组内存是从数据段（例如全局数组）或堆栈段（例如本地数组）分配的。
类似地，链表被认为是一种大小不固定的数据结构，并且在需要时从堆部分（例如使用 malloc() 等）分配内存。从这个意义上讲，数组被视为静态数据结构（驻留在数据或堆栈部分），而链表被视为动态数据结构（驻留在堆部分）。数组和链表的内存表示可以可视化如下：
由 1、2、3 和 4 初始化的 4 个元素（整数类型）的数组。假设这些元素分别分配在内存地址 0x100、0x104、0x108 和 0x10C。
[(1)] [(2)] [(3)] [(4)] 0x100 0x104 0x108 0x10C
一个有 4 个节点的链表，每个节点都有一个整数作为数据，这些数据用 1、2、3 和 4 初始化。假设这些节点是通过 malloc() 分配的，为它们分配的内存是 0x200、0x308、0x404 和 0x20B分别。
[(1), 0x308] [(2),0x404] [(3),0x20B] [(4),NULL] 0x200 0x308 0x404 0x20B
任何对数组和链表了解甚少的人可能对上述解释不感兴趣。我的意思是，众所周知，数组元素按顺序分配内存，即连续内存，而链表的节点在内存中是不连续的。虽然这听起来微不足道，但这是数组和链表之间最重要的区别。应该注意的是，由于这种连续与非连续内存，数组和链表是不同的。事实上，正是这种差异导致了数组与链表的区别！在接下来的部分中，我们将尝试进一步探讨这个想法。
由于数组的元素在内存中是连续的，我们可以使用索引随机访问任何元素，例如 intArr[3] 将直接访问数组的第四个元素。（对于新手，数组索引从 0 开始，这就是为什么第四个元素索引为 3）。此外，由于数组中连续元素的连续内存，不需要额外的信息存储在单个元素中，即没有数组中元数据的开销。与此相反，链表节点在内存中是不连续的。这意味着我们需要某种机制来遍历或访问链表节点。为了实现这一点，每个节点都存储下一个节点的位置，这构成了从一个节点到下一个节点的链接的基础。因此，它被称为链表。虽然在链表中存储下一个节点的位置是开销，但它是必需的。通常，
struct llNode { int dataInt; struct llNode * nextNode; };
因此数组元素在内存中是连续的，因此不需要任何元数据。并且链表节点在内存中是不连续的，因此需要下一个节点位置形式的元数据。除了这个区别，我们可以看到数组可能有几个未使用的元素，因为内存已经分配了。但是链表将只有所需的编号。数据项。以上所有关于数组和链表的信息在几本教科书中都以不同的方式提到过。
如果我们需要从堆部分（即在运行时）分配数组内存和从数据/堆栈部分分配链表内存怎么办。首先，有可能吗？在此之前，有人可能会问为什么有人需要这样做？现在，我希望剩下的文章能让你重新思考数组与链表的概念
现在考虑我们需要在数组中存储某些数据的情况（因为数组由于连续内存而具有随机访问的特性）但我们不知道总大小先验。一种可能性是在运行时从堆分配此数组的内存。例如，如下：
int * dynArr = (int *)malloc(sizeof(int)*arrSize);
尽管该数组的内存是从堆分配的，但仍然可以通过索引机制（例如 dynArr[i]）访问元素。基本上，基于编程问题，我们结合了数组的一个好处（即元素的随机访问）和链表的一个好处（即延迟内存分配到运行时和从堆分配内存）。拥有这种类型的动态数组的另一个优点是这种在运行时从堆分配数组的方法可以减少代码大小（当然，这取决于某些其他因素，例如程序格式等）
