为什么有人要在数组上使用链表？

毫无疑问，对链接列表进行编码比使用数组要花费更多的工作，并且人们可能会想知道什么可以证明需要付出额外的努力。

我认为在链表中插入新元素很简单，但这是数组中的一项主要工作。使用链表存储一组数据与将其存储在数组中相比，还有其他优势吗？

这个问题不是这个问题的重复，因为另一个问题是专门询问特定的Java类，而这个问题与常规数据结构有关。

解决方案

除了更容易插入列表的中间之外，从链接列表的中间删除也比数组更容易。

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

快速入门：物品清除速度更快。

• 将不同大小的数据存储在链接列表中更加容易。数组假定每个元素的大小都完全相同。
• 正如我们所提到的，链接列表的有机增长更容易。阵列的大小需要提前知道，或者在需要增长时重新创建。
• 改组链表只是将什么指向什么更改的问题。改组数组更复杂和/或者占用更多内存。
• 只要所有迭代都发生在" foreach"上下文中，我们就不会在迭代中损失任何性能。

埃里克·利珀特(Eric Lippert)最近发表了一篇关于应谨慎使用数组的原因之一的文章。

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

对于链表，快速插入和删除确实是最好的参数。如果结构动态增长，并且不需要对任何元素(例如动态堆栈和队列)进行恒定时间访问，那么链表是一个不错的选择。

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

编辑：为澄清起见，我的意思是在此处以无序的方式"合并"，而不是在合并排序中。也许"级联"是一个更好的词。

当集合不断增长和缩小时，链接列表特别有用。例如，很难想象尝试使用数组实现Queue(添加到末尾，从前面移除)-我们将花费所有时间将内容向下移动。另一方面，它与链接列表无关紧要。

Wikipedia很好地介绍了这些差异。

Linked lists have several advantages
  over arrays. Elements can be inserted
  into linked lists indefinitely, while
  an array will eventually either fill
  up or need to be resized, an expensive
  operation that may not even be
  possible if memory is fragmented.
  Similarly, an array from which many
  elements are removed may become
  wastefully empty or need to be made
  smaller.
  
  On the other hand, arrays allow random
  access, while linked lists allow only
  sequential access to elements.
  Singly-linked lists, in fact, can only
  be traversed in one direction. This
  makes linked lists unsuitable for
  applications where it's useful to look
  up an element by its index quickly,
  such as heapsort. Sequential access on
  arrays is also faster than on linked
  lists on many machines due to locality
  of reference and data caches. Linked
  lists receive almost no benefit from
  the cache.
  
  Another disadvantage of linked lists
  is the extra storage needed for
  references, which often makes them
  impractical for lists of small data
  items such as characters or boolean
  values. It can also be slow, and with
  a na?ve allocator, wasteful, to
  allocate memory separately for each
  new element, a problem generally
  solved using memory pools.

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

没有人再编码自己的链表了。那真是愚蠢。使用链接列表需要更多代码的前提是错误的。

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

因此，选择链表和数组完全是要权衡每种结构相对于应用程序需求的不同特征。克服额外的编程负担应该对决策产生零影响。

这实际上是一个效率问题，在链表中插入，删除或者移动(并非简单交换)元素的开销是最小的，即操作本身为O(1)，而数组的O(n)则为O.如果我们要对数据列表进行大量操作，则这可能会产生很大的不同。我们根据要对它们进行操作的方式来选择数据类型，并为所使用的算法选择最有效的数据类型。

首先，在C ++中，使用链表应该比处理数组要麻烦得多。我们可以将std :: list或者boost指针列表用于链接列表。链表和数组的关键问题是指针所需的额外空间和可怕的随机访问。如果我们要使用链表

• 我们不需要随机访问数据
• 我们将添加/删除元素，尤其是在列表的中间

两件事情：

Coding a linked list is, no doubt, a bit more work than using an array and he wondered what would justify the additional effort.

使用C ++时，切勿编写链表。只需使用STL。实施起来有多难，决不应成为选择一个数据结构而不选择另一个数据结构的理由，因为大多数数据结构已经在那里实现了。

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

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

将链接添加到链接列表的末尾或者开头很容易，因为我们只需要更新一个链接即可，在矢量中，我们可能需要调整大小并复制内容。

从列表中删除项目很容易，因为我们只需要断开一对链接，然后将它们重新连接在一起即可。从向量中删除项目可能更快或者更慢，这取决于我们是否关心订单。在要删除的项目上方交换最后一个项目的速度更快，而在将其删除之后将所有内容转移的速度较慢，但​​会保持顺序。

另一个很好的理由是，链表非常适合高效的多线程实现。这样做的原因是，更改往往是局部的，仅影响在数据结构的局部插入和删除的一个或者两个指针。因此，我们可以有多个线程在同一个链表上工作。甚至可以使用CAS类型的操作创建无锁版本，并完全避免使用笨重的锁。

使用链接列表，迭代器还可以在进行修改时遍历列表。在修改不冲突的乐观情况下，迭代器可以继续进行而不会引起争用。

对于数组，任何修改数组大小的更改都可能需要锁定数组的很大一部分，实际上，很少在整个数组上都没有全局锁定的情况下完成此操作，因此修改变得停止了世界事务。

在知道确切项目数的地方以及在通过索引进行搜索的地方，数组是有意义的。例如，如果我想在给定的时刻存储视频输出的确切状态而不进行压缩，则可能会使用大小为[1024] [768]的数组。这将为我提供所需的确切信息，而获取给定像素值的列表会慢得多。在没有意义的数组中，通常有比列表更好的数据类型可以有效地处理数据。

使用链表的唯一原因是插入元素很容易(也可以删除)。

缺点可能是指针占用了大量空间。

而且关于该编码的难度更大：
通常，我们不需要代码链接列表(或者仅一次)，它们都包含在其中
STL
如果我们仍然需要这样做，它并没有那么复杂。

我将添加另一个可以充当纯功能数据结构的列表。

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

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

IE。：

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

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

这就是为什么它们在功能性语言中如此流行的原因，这些功能性语言使用不可变的变量prepend和tail操作可以自由进行，而在将数据视为不可变的数据时不必复制原始数据非常重要的功能。

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

由于数组本质上是静态的，因此所有操作
如内存分配发生在编译时
只要。因此处理器必须在其运行时投入更少的精力。

对于ArrayList和LinkedList而言，一个广为人知的参数是调试时LinkedLists不舒服。维护开发人员花在理解程序上的时间，例如来查找错误，增加漏洞，恕我直言，有时并不能证明企业应用程序中的性能提高了纳秒或者内存消耗的字节数。有时(当然，这取决于应用程序的类型)，最好浪费一些字节，但是拥有一个更易于维护或者易于理解的应用程序。

例如，在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>

假设我们有一个有序集合，我们还想通过添加和删除元素来对其进行修改。此外，我们需要能够以对后面元素的引用的方式保留对元素的引用，以便以后可以获取上一个或者下一个元素。例如，一本书的待办事项列表或者一组段落。

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

我们已经注意到自己的第一个问题是插入链接列表允许插入O(1)，但是数组通常需要O(n)。可以部分克服此问题，可以创建一个数据结构，该结构提供类似于数组的常规访问接口，在该接口中，读写操作在最坏情况下都是对数的。

第二个也是更严重的问题是，给定一个元素，找到下一个元素是O(n)。如果未修改集合，则可以保留元素的索引作为引用而不是指针，从而使find-next成为O(1)操作，但实际上只有一个指向对象本身的指针，而且没有而不是通过扫描整个"数组"来确定其当前在数组中的索引。即使我们可以优化插入，对于阵列来说这也是一个无法解决的问题，但是我们无法对查找下一个类型的操作进行优化。

在数组中，我们可以在O(1)时间内访问任何元素。因此，它适合于二进制搜索快速排序等操作。另一方面，链表由于其O(1)时间而适合插入删除。两者都有优点和缺点，并且优先选择一个要归结为我们要实现的目标。

-更大的问题是我们可以同时兼顾两者吗？像python和perl实现的列表一样。

对我来说就是这样

• 数组允许随机访问其元素，因此复杂度为O(1)的数量级
• 阵列不需要额外的存储即可指向下一个数据项。每个元素都可以通过索引进行访问。
• 数组的大小仅限于声明。
• 数组中值的插入/删除非常昂贵。它需要内存重新分配。