链表与数组-yiteyi-C++库

阵列将元素存储在连续的内存位置，从而为存储的元素生成易于计算的地址，这允许更快地访问特定索引处的元素。链表它们的存储结构不那么严格，而且元素通常不存储在相邻的位置，因此它们需要与其他标记一起存储，以提供对下一个元素的引用。数据存储方案中的这种差异决定了哪种数据结构更适合给定的情况。

null

阵列的数据存储方案

链表的数据存储方案

主要区别如下：

尺寸： 由于数据只能存储在阵列中的连续内存块中，因此在运行时无法更改其大小，因为存在覆盖其他数据的风险。然而，在链表中，每个节点指向下一个节点，这样数据就可以存在于分散（非连续）的地址；这允许在运行时更改动态大小。
内存分配： 用于编译时的数组，以及用于链表的运行时。但是，动态分配的数组也会在运行时分配内存。
内存效率： 对于相同数量的元素，链表会使用更多内存，因为对下一个节点的引用也会与数据一起存储。然而，链表的大小灵活性可能会使它们整体上使用更少的内存；当数据元素的大小存在不确定性或数据元素的大小存在较大变化时，这是有用的；在使用数组时，必须分配相当于大小上限的内存（即使不是所有内存都被使用），而链表可以根据数据量逐步增加其大小。
执行时间： 数组中的任何元素都可以通过其索引直接访问；然而，对于链表，必须遍历前面的所有元素才能到达任何元素。此外，阵列中更好的缓存位置（由于连续内存分配）可以显著提高性能。因此，一些操作（例如修改某个元素）在数组中更快，而另一些操作（例如在数据中插入/删除元素）在链表中更快。

下面是有利于链表的几点。（1）数组的大小是固定的：所以我们必须提前知道元素数量的上限。此外，通常，无论使用情况如何，分配的内存都等于上限，在实际使用中，很少达到上限。

（2）在元素数组中插入新元素的成本很高，因为必须为新元素创建空间，并且为了创建空间，必须移动现有元素。

例如，假设我们在一个数组id[]中维护一个已排序的id列表。

id[]=[10001010105020002040，…]。

如果我们想插入一个新的ID 1005，那么为了保持排序顺序，我们必须将所有元素移到1000之后（不包括1000）。

除非使用某些特殊技术，否则删除数组的代价也很高。例如，要删除id[]中的1010，必须移动1010之后的所有内容。

因此，与数组相比，链表提供了以下两个优势 1）动态大小 2）易于插入/删除

链表有以下缺点： 1）不允许随机访问。我们必须从第一个节点开始按顺序访问元素。所以我们不能用链表进行二进制搜索。 2）列表中的每个元素都需要为指针留出额外的内存空间。 3）阵列具有更好的缓存局部性，这会在性能上产生很大的差异。

4）遍历和更改指针需要很多时间。

5）当我们使用指针时，它会令人困惑。

如果您发现任何不正确的地方，或者您想分享有关上述主题的更多信息，请写下评论。