请解释一下链表相对于数组的优点是什么。与链表相比，使用数组有什么优点吗？
问候，
舒阿布
两者都存储元素序列，但使用不同的技术。
An array将元素按连续顺序存储在内存中，即如下所示：
--------------------------------------------------------------------------------------
| item 1 | item 2 | item 3 | ... ... | item x | //here comes other stuff
--------------------------------------------------------------------------------------
这意味着，元素在内存中是一个接一个连续的。
A（（双）链接）list另一方面，按以下方式存储项目：它为每个元素创建一个自己的“列表项”；这个“列表项”保存实际元素and指向下一个“列表项”的指针/引用/提示/等。如果它是双向链接的，它还包含指向前一个“列表项”的指针/引用/提示/等：
------------
------------ ---------- | item 4 |
| item 1 | | item 2 | | next ---+----...
| next ---+------->| next | ------------
------------ ---+------ ^
| |
| |
v |
---------- |
| item 3 | |
| next --+---+
----------
这意味着，元素可以分布在整个内存中，而不是存储在特定的内存位置。
现在我们知道了这一点，我们可以比较一些对元素序列的常用操作：
-
访问特定索引处的元素：使用array，我们简单地计算offset对于这个索引并在索引处有元素。
这是非常便宜的。与一个list另一方面，我们不知道a priori索引处的元素存储在哪里（因为所有元素都可以位于内存中的任何位置），因此我们必须逐项遍历列表，直到找到索引处的元素。这是一项昂贵的操作。
-
在序列末尾添加新元素：使用array这可能会导致以下问题：数组通常具有固定大小，因此如果我们遇到数组已经完全填满的情况（请参阅//here comes other stuff），我们可能无法将新元素放在那里，因为可能已经有其他元素了。所以，也许我们必须复制整个数组。但是，如果数组未填充，我们可以简单地将元素放在那里。
Using a list，我们必须生成一个新的“列表项”，将元素放入其中并设置next当前最后一个元素指向这个新列表项的指针。通常，我们存储对当前最后一个元素的引用，这样我们就不必搜索整个列表来找到它。因此，插入新元素对于列表来说并不是真正的问题。
-
在中间某处添加一个新元素：我们首先考虑arrays：这里，我们可能会遇到以下情况：我们有一个包含元素 1 到 1000 的数组：
1 | 2 | 3 | 4 | 5 | 6 | ... | 999 | 1000 | free | free
现在，我们要插入4.5之间4 and 5: 这意味着我们必须搬家all元素来自5 to 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
移动所有这些元素是一项非常昂贵的操作。所以最好不要经常这样做。
现在我们考虑，如何list可以执行此任务：假设我们当前有以下列表：
1 -> 2 -> 3 -> 4 -> 5 -> ... -> 999 -> 1000
再次，我们要插入4.5之间4 and 5。这可以很容易地完成：我们生成一个新的列表项并更新指针/引用：
1 -> 2 -> 3 -> 4 5 -> ... -> 999 -> 1000
| ^
+-> 4.5 -+
我们只是创建了一个新的列表元素并生成了某种“旁路”来插入它——非常便宜（只要我们有一个指向列表项的指针/引用，新元素就会插入到后面）。
那么，我们总结一下：lists在随机位置插入时非常好（只要您有指向适当列表项的指针）。如果你的操作涉及动态添加大量元素并遍历all无论如何，列表可能是一个不错的选择。
An array在索引访问方面非常好。如果您的应用程序需要经常访问特定位置的元素，您应该使用数组。
值得注意的事情：
解决数组的固定大小问题：如前所述，（原始）数组通常具有固定大小。然而，这个问题现在已经不再重要了，因为几乎所有编程语言都提供了生成数组的机制，这些数组可以根据需要动态增长（并可能收缩）。这种增长和收缩可以这样实现：摊销的用于插入和删除元素（在数组末尾）的 O(1) 运行时间，这样程序员就不必调用grow and shrink明确地。
由于列表为插入提供了如此好的属性，因此它们可以用作搜索树等的基础数据结构。您构造一棵搜索树，其最低层由链表组成。
本文内容由网友自发贡献，版权归原作者所有，本站不承担相应法律责任。如您发现有涉嫌抄袭侵权的内容，请联系:hwhale#tublm.com(使用前将#替换为@)
