题 链表在数组上有什么优势,反之亦然?


请解释链表在数组上的优势。与链表相比,使用数组还有什么优势。

问候, 邻省


20
2017-09-21 07:42


起源


这是一个功课吗?请相应地标记并描述您对该主题的确切理解。这不是一个自由的做作业的方式,试着先付出一些努力 - Andriy Tylychko
关于这个问题有很多问题,包括: stackoverflow.com/questions/166884/array-vs-linked-list - Don Reba


答案:


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

一个 排列 在内存中按顺序存储元素,即它如下所示:

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

这意味着,元素在内存中是一个接一个连续的。

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

                                  ------------
------------        ----------    |  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 明确。

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


45
2017-09-21 08:27



O(1)动态阵列的增长?它必须至少是元素数量的线性时间。此外,我不知道任何会自动缩小数组的语言。在C ++中,即使缩小std :: vector的手动方法也需要hack。 - Don Reba
我在说 摊销 O(1)插入/移除时间。 Growin / shrinkin当然需要线性时间。脚本语言(例如Python)提供看起来像数组并自动增长的东西。 - phimuemue
对不起,我误解了你的回答。你对性能部分是正确的。 “动态增长和收缩”部分仍然应该说“动态增长”。他们不缩水。 - Don Reba


数组具有固定的大小但访问速度更快:它们分配在一个位置,每个元素的位置都是已知的(您可以跳转到右侧元素)。

列表的大小不受限制,但可用内存量不受限制。它们访问速度较慢,因为要查找必须遍历列表的元素。

这是一个非常简短的解释:我建议你拿一本关于数据结构的书并阅读它。这些是您需要完全理解的基本概念。


7
2017-09-21 07:50





由于您使用“数据结构”标记了问题,我将在该上下文中回答这个问题。

声明/创建数组时,数组的大小是固定的,这意味着您无法向其中添加更多元素。因此,如果我有一个数组,比如5个元素,你可以用它做任何你想做的事情但你不能添加更多的元素。

链表基本上是一种表示列表的方式,您可以根据需要拥有尽可能多的“项目”。它由列表中的头(第一个元素),尾部(最后一个元素)和元素(称为节点)组成。

您可能会在任何数据结构类中遇到许多类型的链接列表。

在学习如何在类中创建字段以指向其他对象时,您将学习链接列表的关键是熟练,这就是链接列表的情况,您需要构建列表,以便每个节点指向下一个节点。

显然,这是一个非常普遍的答案。它应该为你的班级提供一个想法。


5
2017-09-21 08:04





数组优于链表的优点

  1. 该数组具有存储在其中的每个元素的特定地址,因此我们可以直接访问任何内存。

  2. 我们知道中间元素和其他元素的位置也很容易访问,我们可以轻松地在数组中执行BINARY SEARCH。

数组超过链接列表的缺点

  1. 需要提及的元素总数或者在创建数组时需要完成内存分配

  2. 一旦提到,阵列的大小就不能在程序中增加。如果输入的元素数超过数组ARRAY OVERFLOW EXCEPTION的大小。

链接列表优于数组的优点

  1. 在程序开头不需要提及列表的大小。

  2. 由于链表没有大小限制,我们可以继续添加新节点(元素)并将列表大小增加到任何程度。

链接列表超过数组的缺点

  1. 节点没有自己的地址。仅存储第一个节点的地址,为了到达任何节点,我们需要遍历从开始到所需节点的整个列表。

  2. 由于所有节点都没有其特定地址,因此无法执行BINARY SEARCH。


2
2017-08-03 10:55





如果您事先不知道需要存储的对象数量,那么列表可能就是您想要的,因为根据需要动态缩小或增大列表非常容易。这样做的另一个好处是能够轻松地插入列表中的元素,而无需重新分配。

另一方面,列表相对于数组的缺点是选择单个元素的速度较慢,因为您需要迭代。使用数组,您将不会遇到此问题。另一方面,如果需要调整数组大小,则使用数组很麻烦,因为此操作比添加或减少链接列表中的元素更昂贵。

列表应该更常用,因为易用性通常比使用静态大小阵列的小性能增益更有利。


0
2017-09-21 07:58



我想你应该修改你的最后一句话。由于选择适当的数据结构,完全取决于您的意图和应用。 BTW,+ 1 :) - Hengameh
遍历链表时,常量缓存的性能损失未命中 远 超过任何其他性能损失的衡量标准。它是 令人难以置信 遍历链表很昂贵。链接列表应该 决不 简单地说。 - antiHUMAN


虽然有人提到数组的性能比链表更好,但我很惊讶地看到在任何地方都没有提到“缓存”这个词。链表的问题主要是它们几乎可以保证从节点到节点的每次跳转都是缓存未命中,即 令人难以置信粗暴地 昂贵,性能方面。

粗略地说,如果你的计划中的表现很重要,你应该这样做 决不 使用链表。永远。它没有任何借口。它们远远超出“慢”,它们是 灾难性的 慢,没有任何关于他们可以弥补这一事实。使用它们就像是对你的表现的故意破坏,比如在你的代码中插入“wait()”函数是绝对没有理由的。


0
2018-04-13 23:11