arrays与链表
为什么有人想要在数组上使用链表？
编码一个链表无疑比使用一个数组有更多的工作，人们可能想知道什么可以certificate额外的努力。
我认为插入新元素在链表中是微不足道的，但这是数组中的一件大事。 使用链表来存储一组数据与将其存储在数组中还有其他的好处吗？
这个问题不是这个问题的重复，因为另外一个问题是关于一个特定的Java类，而这个问题是关于一般的数据结构。
- 将不同大小的数据存储在链表中更容易。 数组假定每个元素的大小完全相同。
- 正如你所提到的那样，链表更容易成长。 数组的大小需要提前知道，或者需要增长时重新创build。
- 改变链表只是改变什么点的问题。 对arrays进行混洗更为复杂，并且需要更多的内存。
- 只要你的迭代都发生在“foreach”上下文中，你就不会在迭代中失去任何性能。
另一个很好的理由是链接列表很好地适用于高效的multithreading实现。 其原因是更改往往是本地的 – 只影响一个或两个指针在数据结构的本地化部分插入和删除。 所以，你可以有许multithreading在同一个链表上工作。 更有甚者，可以使用CAStypes的操作创build无锁版本，并完全避免使用重量级锁。
通过链表，迭代器也可以在修改发生时遍历列表。 在乐观的情况下，修改不会相互冲突，迭代器可以继续而不会发生争用。
对于一个数组来说，任何修改数组大小的改变都可能需要locking大部分的数组，实际上，这种情况在整个数组中没有全局locking的情况下很less发生，因此修改会阻止世界事务。
维基百科有非常好的部分有关的差异。
链接列表比数组有几个优点。 元素可以无限期地插入到链表中，而一个数组最终可能会被填满或者需要resize，如果内存被分割，那么这个操作可能是不可能的。 类似地，从中移除许多元素的数组可能变得浪费空或需要变得更小。
另一方面，数组允许随机访问，而链接列表只允许顺序访问元素。 事实上，单向链表只能朝一个方向移动。 这使得链接列表不适合用于通过其索引快速查找元素的应用程序，例如heapsort。 由于引用和数据高速caching的局部性，在数组上的顺序访问也比在许多机器上的链表上快。 链接列表几乎不会从caching中获益。
链接列表的另一个缺点是引用需要额外的存储空间，这往往使得它们不适用于诸如字符或布尔值等小数据项的列表。 它也可能很慢，并且使用一个天真的分配器浪费，为每个新元素分配内存，一个问题通常使用内存池解决。
我会添加一个 – 列表可以作为纯粹的function数据结构。
例如，你可以有完全不同的列表共享相同的结束部分
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中。
这就是为什么它们在使用不可变variables的函数式语言中如此受欢迎 – preprend和tail操作可以自由进行，而无需复制原始数据 – 当您将数据视为不可变的时候非常重要的特性。
合并两个链表（特别是两个双链表）比合并两个数组要快得多（假设合并是破坏性的）。 前者取O（1），后者取O（n）。
编辑：澄清，我的意思是“合并”在这里无序的意义上，而不是在合并sorting。 也许“连接”会是一个更好的词。
除了插入到列表中间更容易 – 从一个链表中间删除比一个数组更容易。
但坦率地说，我从来没有使用链表。 每当我需要快速插入和删除，我还需要快速查找，所以我去了一个HashSet或一个词典。
首先，在C ++中，链接列表不应该比数组更麻烦。 您可以使用std :: list或链接列表的boost指针列表 。 链表和数组的关键问题是指针和可怕的随机访问需要额外的空间。 你应该使用链表
- 你不需要随机访问数据
- 您将添加/删除元素，特别是在列表中间
ArrayList和LinkedList的一个广泛的不受欢迎的参数是LinkedListsdebugging时不舒服 。 维护开发人员了解程序所花费的时间，例如寻找错误，增加和恕我直言，有时不能certificate性能改进的纳秒或企业应用内存消耗的字节数。 有时（当然，这取决于应用程序的types），最好是浪费几个字节，但有一个应用程序更易于维护或易于理解。
例如，在Java环境中并使用Eclipsedebugging器，debuggingArrayList将显示一个非常容易理解的结构：
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>
Eric Lippert最近发表了一篇关于arrays应该保守使用的原因之一。
两件事情：
毫无疑问，编码一个链表比使用一个数组要多一点，他想知道什么会certificate额外的努力。
在使用C ++时从不编码链表。 只需使用STL。 实施起来难度不应该是select一种数据结构而不是另一种数据结构的理由，因为大多数已经在那里实现了。
至于数组和链表之间的实际差异，对我来说最重要的是你如何计划使用这个结构。 我将使用术语向量，因为这是C ++中可resize的数组的术语。
索引到一个链表是慢的，因为你必须遍历列表才能到达给定的索引，而一个向量在内存中是连续的，你可以使用指针math到达那里。
添加到链表的末尾或开头很容易，因为您只需更新一个链接，在vector中的某个位置可能需要resize并复制内容。
从列表中删除一个项目很容易，因为你只需要打破一对链接，然后把它们连接在一起。 从一个vector中删除一个项目可以更快或更慢，这取决于你是否在意订单。 在最后一个项目中交换要删除的项目会更快，而将所有项目更改后更慢将保留sorting。
对我来说就是这样，
-
访问
- 链接列表只允许顺序访问元素。 因此，algorithm的复杂性是O（n）
- 数组允许随机访问其元素，因此复杂度为O（1）
-
存储
- 链接列表需要额外的引用存储。 这使得它们不适用于诸如字符或布尔值之类的小数据项的列表。
- 数组不需要额外的存储来指向下一个数据项。 每个元素都可以通过索引访问。
-
尺寸
- 链接列表的大小本质上是dynamic的。
- 数组的大小仅限于声明。
-
插入/缺失
- 可以无限期地在链接列表中插入和删除元素。
- 在数组中插入/删除值非常昂贵。 它需要内存重新分配。
除了从列表中间添加和删除，我更喜欢链接列表，因为它们可以dynamic增长和缩小。
这是一个快速的：删除项目更快。
快速插入和删除确实是链接列表的最佳参数。 如果您的结构dynamic增长，并且不需要对任何元素进行常量访问（如dynamic堆栈和队列），则链接列表是一个不错的select。
链接列表是特别有用的，当collections不断增长和收缩。 例如，很难想象使用一个数组来实现一个Queue（添加到最后，从前面删除） – 你将花费你所有的时间来移动事物。 另一方面，链接列表是微不足道的。
这实际上是一个效率问题，插入，移除或移动（不是简单地交换）链接列表中的元素的开销是最小的，即操作本身是O（1），对于数组而言是O（n）。 如果您在数据清单上进行大量操作，这可能会产生重大影响。 您根据自己的操作方式select数据types，并select最有效的algorithm。
在确定项目的确切数量的情况下，通过索引进行search是有意义的。 例如，如果我想存储我的video输出的确切状态在一个给定的时刻没有压缩，我可能会使用大小[1024] [768]的数组。 这将为我提供我所需要的东西，而列表会慢得多得到给定像素的值。 在数组没有意义的地方，通常比列表有更好的数据types来有效处理数据。
arrays与链接列表：
- arrays内存分配有时会由于内存碎片而失败。
- 因为所有的元素都被分配了连续的内存空间，所以在数组中caching更好。
- 编码比数组更复杂。
- 链接列表没有大小限制，不像数组
- 链接列表中的插入/删除速度更快，数组中的访问速度更快。
- 链表更好，从multithreading的angular度来看更好。
没有人再编码自己的链表。 那太傻了。 使用链表需要更多代码的前提是错误的。
这些日子里，build立一个链表只是对学生的练习，所以他们可以理解这个概念。 相反，每个人都使用预先build立的列表。 在C ++中，根据我们问题中的描述，这可能意味着一个stl向量（ #include <vector> ）。
因此，select一个链表与一个数组完全是相对于你的应用程序的需求来衡量每个结构的不同特征。 克服额外的编程负担应该对决策产生零影响。
假设你有一个有序集合，你也想通过添加和删除元素来修改。 此外，您需要能够保留对元素的引用，以便稍后可以获取上一个元素或下一个元素。 例如，一本书中的待办事项列表或一组段落。
首先我们应该注意的是，如果你想保留对象集合之外的对象的引用，你最终可能会把指针存储在数组中，而不是自己存储对象。 否则，你将无法插入到数组中 – 如果对象被embedded到数组中，它们将在插入过程中移动，任何指向它们的指针都将失效。 数组索引也是如此。
你自己的第一个问题就是插入链表允许插入O（1），但是一个数组通常需要O（n）。 这个问题可以部分克服 – 可以创build一个数据结构，使数组类似的顺序访问接口，读写最差的时候是对数的。
你的第二个也是更严重的问题是给定一个元素find下一个元素是O（n）。 如果这个集合没有被修改，你可以保留元素的索引而不是指针，从而使find-next成为一个O（1）操作，但是因为它只是一个指向对象本身的指针而没有办法除了通过扫描整个“数组”来确定其在数组中的当前索引。 对于数组来说，这是一个不可逾越的问题 – 即使您可以优化插入，也无法优化find-nexttypes的操作。
在数组中，你有权访问O（1）中的任何元素。 所以它适合于像二进制search快速sorting等操作。另一方面链接列表适合插入删除，因为它在O（1）时间。 两者都有优点，也有缺点，比其他优点更容易实现。
– 更大的问题是我们可以混合使用两者。 就像python和perl实现列表一样。
链接列表
当它插入时它更可取！ 基本上，它是处理指针
1→3→4
插入（2）
1 …….. 3 …… 4
2 …..
最后
1→2→3→4
箭头2点3点，箭头1点2点
简单！
但从arrays
| 1 | 3 | 4 |
插入（2）| 1 | 3 | | 4 | | 1 | | 3 | 4 | | 1 | 2 | 3 | 4 |
那么任何人都可以想象其中的差异！ 只是4索引，我们正在执行3个步骤
那么如果数组长度是一百万呢？ 数组是否高效？ 答案是不！ 🙂
同样的事情去删除！ 在链接列表中，我们可以简单地使用指针并将对象类中的元素和接下来的元素废除！ 但是对于数组，我们需要执行shiftLeft（）
希望有所帮助！ 🙂
只有使用链表的原因是插入元素很容易（也是删除）。
Disadvatige可能是指针占用大量的空间。
而关于这个编码更难：通常你不需要代码链表（或只有一次），它们被包含在STL中 ，如果你仍然需要这样做，它并不是那么复杂。
我也认为链接列表比数组更好。 因为我们在链接列表中遍历，而不是在数组中
因为数组在本质上是静态的，所以所有的操作，如内存分配，都只在编译时才会发生。 所以处理器必须减less运行时间。
根据您的语言，可以考虑这些缺点和优点中的一些：
C编程语言 ：当使用链表（通常通过结构指针）时，必须特别考虑到你没有泄漏内存。 正如前面提到的，链表很容易洗牌，因为所有的操作都在改变指针，但是我们会记得释放所有的东西吗？
Java ：Java有一个自动垃圾收集器，所以泄漏内存不会是一个问题，但是从高层次的程序员隐藏的是链接列表的实现细节。 诸如从列表中移除节点的方法比一些语言的用户期望的更复杂。
链表更多的是维护开销，而不是数组，所有这些要求都需要额外的内存。 但有几件事不能做。 在许多情况下，假设你想要一个长度为10 ^ 9的数组，你不能得到它，因为获得一个连续的内存位置必须在那里。 链接列表可能是一个救世主在这里。
假设你想用数据存储多个东西，那么他们可以很容易地在链表中扩展。
STL容器通常在幕后实现链表实现。
使用linklist的人必须阅读。 人们会再次爱上阵容。 它讲的是乱序执行，硬件预取，内存延迟等。
http://www.futurechips.org/thoughts-for-researchers/quick-post-linked-lists.html
为什么在数组上的链表？ 那么有些人已经说过，插入和删除的速度更快。
但是，也许我们不必忍受任何一方的限制，同时又能兼顾两方面，呃？
对于数组删除，可以使用“已删除”字节来表示一行已被删除的事实，因此重新定位该数组不再是必需的。 为了减轻插入的负担或快速改变数据，请使用链接列表。 那么当提到它们时，首先search一个逻辑，然后search另一个逻辑。 因此，将它们组合使用可以使您获得最好的效果。
如果你有一个非常大的数组，你可以将它与另一个更小的数组或链表进行组合，其中较小的数组保存20,50,100个最近使用的项目。 如果需要的不在较短的链表或数组中，则转到大数组。 如果在那里find的话，你可以把它添加到较小的链接列表/数组上，假定“最近使用的东西最喜欢被重用”（是的，可能会碰到列表中最近最less使用的东西）。 在许多情况下，这是真实的，解决了一个问题，我不得不在一个.ASP安全权限检查模块，轻松，优雅，速度惊人的解决。
虽然你们中的许多人已经涉及到链表和数组的主要adv./dis，大多数的比较是一个比另一个更好/更差的比较。 你可以在数组中进行随机访问，但在链表和其他数据库中不可能。 但是，这是假设链接列表和数组将被用于类似的应用程序。 然而，正确的答案应该是在特定的应用程序部署中链接列表如何优先于数组，反之亦然。 假设你想实现一个字典应用程序，你会用什么？ 数组：嗯，这将允许通过二进制search和其他searchalgorithm容易检索..但让我们想想如何链接列表可以更好..你可以在字典中search“Blob”。 有一个A-> B-> C-> D —-> Z的链接列表是有意义的，然后每个列表元素也指向一个数组或另一个以该字母开始的所有单词列表。
A -> B -> C -> ...Z | | | | | [Cat, Cave] | [Banana, Blob] [Adam, Apple]
现在是上面的方法更好还是平面arrays[亚当，苹果，香蕉，斑点，猫，洞]？ arrays甚至可能吗？ 所以链接列表的一个主要优点是你可以有一个元素不仅指向下一个元素，而且还有其他链接列表/数组/堆/或任何其他内存位置。 数组是一个单一的连续的内存，将其分割成要存储的元素的块大小。另一方面，链接列表是大块非连续的内存单元（可以是任何大小，可以存储任何东西），并指向每个其他你想要的方式。 同样可以说，你正在做一个USB驱动器。 现在你想将文件保存为任何数组或链接列表？ 我想你知道我指的是什么:)
