data-structures - 链表相对于数组的优势是什么，反之亦然？

Question

请解释链表相对于数组的优势是什么。与链表相比，使用数组还有什么优势。

问候，
绍伊卜

Answer 1

两者都存储一系列元素，但使用不同的技术。

安 阵列 在内存中按连续顺序存储元素，即它看起来如下:

--------------------------------------------------------------------------------------
|  item 1  |  item 2  |  item 3  |  ...  ...  |  item x  | //here comes other stuff
--------------------------------------------------------------------------------------

这意味着，元素在内存中一个接一个地连续。

A((双)链接)列表 ，另一方面，以下列方式存储项目:它为每个元素创建一个自己的“列表项”；这个“列表项”包含实际元素和指向下一个“列表项”的指针/引用/提示/等。如果它是双向链接的，它还包含指向前一个“列表项”的指针/引用/提示/等:

                                  ------------
------------        ----------    |  item 4  |
|  item 1  |        | item 2 |    |  next ---+----...
|  next ---+------->| next   |    ------------
------------        ---+------      ^
                       |            |
                       |            |
                       v            |
                       ----------   |
                       | item 3 |   |
                       | next --+---+
                       ----------

这意味着，元素可以分布在整个内存中，而不是存储在特定的内存位置。

现在我们知道了这一点，我们可以比较一些对元素序列的常用操作:

访问特定索引处的元素:使用 阵列 ，我们只需计算此索引的偏移量，并在索引处放置元素。

这是非常便宜的。带 列表另一方面，我们不知道索引处的元素存储在哪里(因为所有元素都可以在内存中的任何位置)，所以我们必须逐项遍历列表，直到找到索引处的元素。这是一项昂贵的操作。

在序列末尾添加一个新元素:使用 阵列 这会导致以下问题:数组通常是固定大小的，所以如果我们的数组已经完全填满(见 //here comes other stuff)，我们可能无法将新元素放在那里，因为可能已经有其他东西了.所以，也许我们必须复制整个数组。但是，如果数组未填充，我们可以简单地将元素放在那里。

使用列表，我们必须生成一个新的“列表项”，将元素放入其中并设置 next当前最后一个元素的指针指向这个新的列表项。通常，我们存储对当前最后一个元素的引用，这样我们就不必搜索整个列表来找到它。因此，插入新元素对于列表来说不是真正的问题。

在中间某处添加一个新元素:我们先考虑数组 :在这里，我们可能会遇到以下情况:我们有一个元素为 1 到 1000 的数组:
1 | 2 | 3 | 4 | 5 | 6 | ... | 999 | 1000 | free | free
现在，我们要插入 4.5之间4和 5 :这意味着，我们必须从 5 移动所有元素至 1000一个位置，以便为 4.5 腾出空间:

 1 | 2 | 3 | 4 | free | 5 | 6 | ... | 999 | 1000 | free

                  ||
                  vv

 1 | 2 | 3 | 4 | 4.5  | 5 | 6 | ... | 999 | 1000 | free

移动所有这些元素是一项非常昂贵的操作。所以最好不要经常这样做。

现在我们考虑一下，列表可以执行此任务:假设我们目前有以下列表:

 1 -> 2 -> 3 -> 4 -> 5 -> ... -> 999 -> 1000

同样，我们要插入 4.5之间4和 5 .这可以很容易地完成:我们生成一个新的列表项并更新指针/引用:

 1 -> 2 -> 3 -> 4        5 -> ... -> 999 -> 1000
                |        ^
                +-> 4.5 -+

我们简单地创建了一个新的列表元素并生成了一种“绕过”来插入它 - 非常便宜(只要我们有一个指向列表项的指针/引用，新元素将在后面插入)。

所以，让我们总结一下:链接列表 在随机位置插入时非常好(只要您有一个指向适当列表项的指针)。如果您的操作涉及动态添加大量元素并且无论如何都要遍历所有元素，那么列表可能是一个不错的选择。

安 阵列 在索引访问方面非常好。如果您的应用程序需要经常访问特定位置的元素，您应该使用数组。

值得注意的事情:

解决数组的固定大小问题:如前所述，(原始)数组通常具有固定大小。然而，这个问题现在不再是真正的问题，因为几乎所有的编程语言都提供了生成数组的机制，这些数组根据需要动态增长(并可能缩小)。可以实现这种增长和收缩，这样我们就可以分摊 O(1) 的运行时间来插入和删除元素(在数组的末尾)，这样程序员就不必调用 grow和 shrink明确地。

由于列表为插入提供了如此好的属性，因此它们可以用作搜索树等的底层数据结构。即您构建了一个搜索树，其最低级别由链表组成。