首页 文章

数组与链表

提问于
浏览 次
181

为什么有人想在阵列上使用链表？

毫无疑问，对链接列表进行编码比使用数组要多一些工作，人们可能想知道什么是合理的额外工作 .

我认为在链表中插入新元素是微不足道的，但它是数组中的一项重要工作 . 使用链表存储一组数据与将其存储在数组中是否还有其他优点？

这个问题不是this question的重复，因为另一个问题是具体询问特定的Java类，而这个问题与一般数据结构有关 .

arrays data-structures linked-list

30 回答

  • 2

    • 在链表中存储不同大小的数据更容易 . 数组假定每个元素的大小完全相同 .

    • 正如您所提到的，它需要提前知道's easier for a linked list to grow organically. An array'的大小，或者在需要增长时重新创建 .

    • 改组链表只是改变指向什么的问题 . 混乱阵列更复杂和/或占用更多内存 .

    • 只要您的迭代都发生在"foreach"上下文中，您就不会在迭代中失去任何性能 .

    回复于
  • 1

    链接列表比数组更需要维护开销，它还需要额外的内存存储，所有这些点都是一致的 . 但有一些事情无法做到 . 在许多情况下，假设你想要一个长度为10 ^ 9的数组，你无法得到它，因为必须有一个连续的内存位置 . 链表可能是这里的救世主 .

    假设您希望使用数据存储多个内容，则可以在链接列表中轻松扩展它们 .

    STL容器通常在场景后面有链表实现 .

    回复于
  • 1

    我将添加另一个 - 列表可以充当purely functional数据结构 .

    例如，您可以拥有完全不同的列表，共享相同的结尾部分

    a = (1 2 3 4, ....)
b = (4 3 2 1 1 2 3 4 ...)
c = (3 4 ...)

    即：

    b = 4 -> 3 -> 2 -> 1 -> a
c = a.next.next

    无需将 a 指向的数据复制到 b 和 c 中 .

    这就是为什么它们在功能语言中如此受欢迎，它使用不可变变量 - prepend 和 tail 操作可以自由发生而无需复制原始数据 - 当您将数据视为不可变时非常重要的功能 .

    回复于
  • 2

    在确切知道项目的确切数量以及按索引搜索有意义的地方，数组是有意义的 . 例如，如果我想在没有压缩的情况下在给定时刻存储视频输出的确切状态，我可能会使用大小为[1024] [768]的数组 . 这将为我提供我所需要的，并且列表在获得给定像素的值时要慢得多 . 在数组没有意义的地方，通常有比列表更好的数据类型来有效地处理数据 .

    回复于
  • 5

    由于数组本质上是静态的，因此所有操作（如内存分配）仅在编译时发生 . 因此，处理器必须在运行时减少工作量 .

    回复于
  • 16

    Eric Lippert最近有一个post，原因之一就是保守地使用数组 .

    回复于
  • 1

    两件事情：

    毫无疑问，对链接列表进行编码比使用数组要多一些工作，他想知道什么是合理的额外努力 .

    使用C时，切勿对链表进行编码 . 只需使用STL . 实施起来有多难，绝不应该成为选择一种数据结构而不是另一种数据结构的理由，因为大多数数据结构已在那里实现 .

    至于数组和链表之间的实际差异，对我来说最重要的是你如何计划使用该结构 . 我将使用术语向量，因为这是C中可调整大小的数组的术语 .

    索引到链表是很慢的，因为你必须遍历列表才能到达给定的索引，而向量在内存中是连续的，你可以使用指针数学到达那里 .

    附加到链接列表的末尾或开头很容易，因为您只需要更新一个链接，在向量中您可能需要调整大小并复制内容 .

    从列表中删除项目很简单，因为您只需断开一对链接然后将它们重新连接在一起 . 从矢量中移除项目可以更快或更慢，具体取决于您是否关心订单 . 将最后一个项目交换到您想要删除的项目上方更快，而在向下移动所有内容后速度较慢但仍保留订购 .

    回复于
  • 2

    链接列表在集合不断增长和缩小时特别有用 . 例如，很难想象尝试使用数组实现队列（添加到最后，从前面删除） - 你将花费所有时间来减少事情 . 另一方面，链接列表很简单 .

    回复于
  • 2

    根据您的语言，可以考虑以下一些缺点和优点：

    C编程语言：使用链表时（通常通过结构指针），必须特别注意不要泄漏内存 . 正如前面提到的，链接列表很容易改变，因为所有的都是做的是改变指针，但我们是否会记得释放一切？

    Java：Java有一个自动垃圾收集，因此泄漏的内存不会成为问题，但是高级程序员隐藏的是链接列表的实现细节 . 诸如从列表中间删除节点的方法比一些语言的用户期望的更复杂 .

    回复于
  • 2

    为什么有人想在阵列上使用链表？

    这只是一个原因 - 如果您需要链接列表数据结构和您正在使用的编程语言不支持指针 .

    回复于
  • 1

    数组与链接列表：

    • 由于内存碎片，数组内存分配有时会失败 .

    • 在数组中缓存更好，因为所有元素都分配了连续的内存空间 .

    • 编码比数组更复杂 .

    • 链接列表没有大小限制，与数组不同

    • 在链接列表中插入/删除更快，并且在数组中访问速度更快 .
      从多线程的角度来看，

    • 链接列表更好 .

    回复于
  • 13

    虽然你们中的许多人已经触及了链表和阵列的主要优点，但大多数比较都是如何比另一个更好/更差.Eg . 您可以在数组中进行随机访问，但在链表和其他链接中不可能 . 但是，假设链接列表和数组将应用于类似的应用程序中 . 但是，正确的答案应该是如何在特定的应用程序部署中优先考虑链接列表而不是数组，反之亦然 . 假设您要实现字典应用程序，您会使用什么？数组：mmm它可以通过二进制搜索和其他搜索算法轻松检索..但让我们想想链接列表如何更好 . 想要在字典中搜索“Blob” . 有一个链接列表A-> B-> C-> D ----> Z是否有意义，然后每个列表元素也指向一个数组或以该字母开头的所有单词的另一个列表 .

    A -> B -> C -> ...Z
|    |    |
|    |    [Cat, Cave]
|    [Banana, Blob]
[Adam, Apple]

    现在是上面的方法更好还是[亚当，苹果，香蕉，Blob，猫，洞穴]的平面阵列？甚至可以用阵列吗？因此链接列表的一个主要优点是，您可以拥有一个元素，不仅指向下一个元素，还指向其他链接列表/数组/堆/或任何其他内存位置 . 数组是一个单独的连续存储器，切成它要存储的元素的块大小 . 另一方面，链接列表是一块非连续的存储单元（可以是任何大小，可以存储任何东西）并指向每个其他你想要的方式 . 同样地，假设您正在制作USB驱动器 . 您现在要将文件保存为任何数组还是链接列表？我想你明白我指的是:)

    回复于
  • 1

    首先，在C链接列表中使用它不应该比使用数组更麻烦 . 您可以将std::list或boost pointer list用于链接列表 . 链表和数组的关键问题是指针和可怕的随机访问所需的额外空间 . 如果你，你应该使用一个链表

    • 您不需要随机访问数据

    • 您将添加/删除元素，尤其是在列表中间

    回复于
  • 6

    为什么列表上的链表？正如一些人已经说过的那样，插入和删除的速度更快 .

    但也许我们不必忍受两者的限制，并同时充分利用两者......呃？

    对于数组删除，您可以使用“已删除”字节来表示已删除行的事实，因此不再需要重新排列数组 . 为了减轻插入或快速更改数据的负担，请使用链接列表 . 然后在提到它们时，先让你的逻辑搜索一个，然后再搜索另一个 . 因此，组合使用它们可以让您获得最佳效果 .

    如果你有一个非常大的数组，你可以将它与另一个更小的数组或链表结合起来，其中较小的数组包含最近使用的20,50,100个项目 . 如果所需的不在较短的链表或数组中，则转到大型数组 . 如果在那里找到，你可以将它添加到较小的链表/数组中，假定“最近使用的东西最适合重复使用”（是的，可能会从列表中碰到最近最少使用的项目） . 在许多情况下都是如此，并解决了我必须在.ASP安全权限检查模块中解决的问题，具有轻松，优雅和令人印象深刻的速度 .

    回复于
  • 5

    除了从列表中间添加和删除之外，我更喜欢链接列表，因为它们可以动态增长和缩小 .

    回复于
  • 5

    在数组中，您有权在O（1）时间内访问任何元素 . 因此它适用于二进制搜索快速排序等操作 . 另一方面，链接列表适合于在O（1）时间内插入删除 . 两者都有优点和缺点，并且优先选择其中一个而不是您想要实现的内容 .

    • 更大的问题是我们可以将两者混合使用 . 像python和perl实现的东西作为清单 .
    回复于
  • 16

    合并两个链表（尤其是两个双链表）比合并两个数组要快得多（假设合并具有破坏性） . 前者取O（1），后者取O（n） .

    EDIT: 为了澄清，我的意思是"merging"在这里是无序的，而不是在合并排序中 . 也许"concatenating"会是一个更好的词 .

    回复于
  • 1

    链接列表

    它更适合插入！基本上它的作用是处理指针

    1 - > 3 - > 4

    插入（2）

    1 ........ 3 ...... 4
    2 .....

    最后

    1 - > 2 - > 3 - > 4

    从2点3点处得到一个箭头，1点箭头指向2点

    简单！

    但是来自Array

    | 1 | 3 | 4 |

    插入（2）| 1 | 3 | | 4 | | 1 | | 3 | 4 | | 1 | 2 | 3 | 4 |

    那么任何人都可以想象出差异！仅为4指数我们正在执行3个步骤

    如果阵列长度是一百万呢？阵列有效吗？答案是不！ :)

    删除同样的事情！在链接列表中，我们可以简单地使用指针并使对象类中的元素和下一个元素无效！但对于数组，我们需要执行shiftLeft（）

    希望有所帮助！ :)

    回复于
  • 10

    快速插入和删除确实是链表的最佳参数 . 如果您的结构动态增长并且不需要对任何元素进行恒定时间访问（例如动态堆栈和队列），则链接列表是一个不错的选择 .

    回复于
  • 141

    ArrayList和LinkedList的广泛不受重视的论点是 LinkedLists are uncomfortable while debugging . 维护开发人员花在理解程序上的时间，例如找到错误，增加和IMHO确实有时不能证明性能改进中的纳秒或企业应用程序中内存消耗的字节数 . 有时（当然，这取决于应用程序的类型），最好浪费几个字节，但有一个更易于维护或更容易理解的应用程序 .

    例如，在Java环境中并使用Eclipse调试器，调试ArrayList将显示一个非常易于理解的结构：

    arrayList   ArrayList<String>
  elementData   Object[]
    [0] Object  "Foo"
    [1] Object  "Foo"
    [2] Object  "Foo"
    [3] Object  "Foo"
    [4] Object  "Foo"
    ...

    另一方面，观看LinkedList的内容并查找特定对象会成为一个Expand-The-Tree点击噩梦，更不用说过滤掉LinkedList内部所需的认知开销：

    linkedList  LinkedList<String>
    header  LinkedList$Entry<E>
        element E
        next    LinkedList$Entry<E>
            element E   "Foo"
            next    LinkedList$Entry<E>
                element E   "Foo"
                next    LinkedList$Entry<E>
                    element E   "Foo"
                    next    LinkedList$Entry<E>
                    previous    LinkedList$Entry<E>
                    ...
                previous    LinkedList$Entry<E>
            previous    LinkedList$Entry<E>
        previous    LinkedList$Entry<E>
    回复于
  • 121

    没有人再编码自己的链表了 . 那太傻了 . 使用链表需要更多代码的前提是错误的 .

    如今，构建链表只是学生的练习，因此他们可以理解这个概念 . 相反，每个人都使用预建列表 . 在C中，基于我们问题中的描述，这可能意味着一个stl向量（ #include <vector> ） .

    因此，选择链表与数组完全是关于权衡每个结构相对于应用需求的不同特征 . 克服额外的编程负担应该对决策没有任何影响 .

    回复于
  • 7

    这实际上是效率的问题，插入，移除或移动（不是简单地交换）链接列表中的元素的开销是最小的，即操作本身是O（1），对于数组而言是O（n） . 如果您在数据列表上运行很多，这可能会产生显着差异 . 您根据操作方式选择数据类型，并为您使用的算法选择最有效的数据类型 .

    回复于
  • 6

    维基百科有很好的部分关于差异 .

    链接列表与数组相比有几个优点 . 元素可以无限期地插入到链表中，而数组最终会填满或需要调整大小，这是一个昂贵的操作，如果内存碎片化甚至可能无法实现 . 类似地，从中移除许多元素的阵列可能变得浪费空或者需要变小 . 另一方面，数组允许随机访问，而链表仅允许对元素进行顺序访问 . 事实上，单链表只能在一个方向上进行 . 这使链接列表不适合于快速查找元素的应用程序，例如heapsort . 由于引用和数据高速缓存的位置，对阵列的顺序访问也比许多机器上的链接列表更快 . 链接列表几乎不会从缓存中获益 . 链表的另一个缺点是引用所需的额外存储空间，这常常使得它们对于诸如字符或布尔值之类的小数据项列表来说是不切实际的 . 它也可能很慢，并且对于每个新元素分别为每个新元素分配内存而浪费一个天真的分配器，通常使用内存池解决问题 .

    http://en.wikipedia.org/wiki/Linked_list

    回复于
  • 9

    只使用链表的原因是插入元素很容易（也删除） .

    Disadvatige可能是指针占用了大量空间 .

    关于编码更难：通常你不需要代码链表（或只需要一次）它们包含在STL中，如果你仍然必须这样做，它就不那么复杂了 .

    回复于
  • 53

    除了插入列表中间之外更简单 - 从链表中间删除比从数组中删除更容易 .

    但坦率地说，我从未使用过链表 . 每当我需要快速插入和删除时，我也需要快速查找，所以我去了HashSet或Dictionary .

    回复于
  • 163

    假设您有一个有序集，您还希望通过添加和删除元素来修改它 . 此外，您需要能够保留对元素的引用，以便以后可以获取上一个或下一个元素 . 例如，书中的待办事项列表或段落集 .

    首先我们应该注意，如果你想保留对集合本身之外的对象的引用，你可能最终会在数组中存储指针，而不是自己存储对象 . 否则你将无法插入到数组中 - 如果对象嵌入到数组中，它们将在插入期间移动，并且任何指向它们的指针都将变为无效 . 数组索引也是如此 .

    您已经注意到的第一个问题是插入链接列表允许插入O（1），但数组通常需要O（n） . 这个问题可以部分克服 - 有可能创建一个数据结构，提供类似于数组的顺序访问接口，其中读取和写入在最坏的情况下都是对数的 .

    你的第二个也是更严重的问题是，给定元素查找下一个元素是O（n） . 如果没有修改集合，你可以保留元素的索引作为引用而不是指针，从而使find-next成为O（1）操作，但是因为它只是指向对象本身而没有办法除了通过扫描整个“数组”之外，确定其在数组中的当前索引 . 这对于数组来说是一个难以克服的问题 - 即使您可以优化插入，也没有什么可以优化查找下一个类型的操作 .

    回复于
  • 6

    对我来说就是这样，

    • 访问

    • Linked Lists 仅允许对元素进行顺序访问 . 因此，算法的复杂性是O（n）的阶数

    • Arrays 允许随机访问其元素，因此复杂度为O（1）的顺序

    • 存储

    • Linked lists 需要额外的存储空间以供参考 . 这使得它们对于诸如字符或布尔值的小数据项列表是不实用的 .

    • Arrays 不需要额外的存储空间来指向下一个数据项 . 可以通过索引访问每个元素 .

    • 尺寸

    • Linked lists 的大小本质上是动态的 .

    • array 的大小仅限于声明 .

    • 插入/删除

    • 可以无限期地在 linked lists 中插入和删除元素 .

    • 在 arrays 中插入/删除值非常昂贵 . 它需要内存重新分配 .

    回复于
  • 6

    我也认为链接列表比数组更好 . 因为我们在链接列表中遍历但不在数组中遍历

    回复于
  • 26

    这是一个快速的：删除项目更快 .

    回复于
  • 27

    另一个很好的理由是链表很适合高效的多线程实现 . 这样做的原因是更改往往是本地的 - 只影响一个或两个指针，以便在数据结构的本地化部分插入和删除 . 因此，您可以让许多线程在同一个链表上工作 . 更重要的是，可以使用CAS类型的操作创建无锁版本，并完全避免重量级锁定 .

    使用链表，迭代器也可以在发生修改时遍历列表 . 在乐观的情况下，修改不会发生冲突，迭代器可以继续而不会发生争用 .

    对于数组，任何修改数组大小的更改都可能需要锁定数组的大部分，事实上，如果没有整个数组的全局锁定，很少这样做，因此修改会阻止这个世界事务 .

    回复于

相关问题