我一直是一个简单使用的人：
List<String> names = new ArrayList<>();
我使用 interface 作为portability的类型名称，因此当我提出这样的问题时，我可以重新编写我的代码。
什么时候应该LinkedList用完，ArrayList反之亦然？
sdellysse
问问题
1251850 次
33 回答
3707
在更多ArrayList的用例中，总结比. 如果您不确定 - 只需从.ArrayDequeLinkedListArrayList
TLDR，在 ArrayList 中访问一个元素需要常数时间 [O(1)]，而添加一个元素需要 O(n) 时间[最坏情况]。在 LinkedList 中添加元素需要 O(n) 时间，访问也需要 O(n) 时间，但 LinkedList 比 ArrayList 使用更多内存。
LinkedList并且ArrayList是 List 接口的两种不同实现。LinkedList用双向链表实现它。ArrayList使用动态调整大小的数组来实现它。
与标准链表和数组操作一样，各种方法将具有不同的算法运行时。
get(int index)是O(n)（平均有n/4步），但O(1) whenindex = 0orindex = list.size() - 1（在这种情况下，您也可以使用getFirst()andgetLast()）。的主要好处之一LinkedList<E>add(int index, E element)是O(n)（平均有n/4步），但是O(1) whenindex = 0orindex = list.size() - 1（在这种情况下，您也可以使用addFirst()andaddLast()/add()）。的主要好处之一LinkedList<E>remove(int index)是O(n)（平均有n/4步），但O(1) whenindex = 0orindex = list.size() - 1（在这种情况下，您也可以使用removeFirst()andremoveLast()）。的主要好处之一LinkedList<E>Iterator.remove()是O(1)。的主要好处之一LinkedList<E>ListIterator.add(E element)是O(1)。的主要好处之一LinkedList<E>
注意：许多操作平均需要n/4步，最佳情况下的步数恒定（例如 index = 0），最坏情况下需要n/2步（列表中间）
get(int index)是O(1)。主要好处ArrayList<E>add(E element)是O(1)摊销，但O(n)最坏情况，因为必须调整数组大小和复制add(int index, E element)是O(n)（平均有n/2步）remove(int index)是O(n)（平均有n/2步）Iterator.remove()是O(n)（平均有n/2步）ListIterator.add(E element)是O(n)（平均有n/2步）
注意：许多操作平均需要n/2步，最佳情况下（列表末尾）的步数恒定，最坏情况下（列表开头）需要n步
LinkedList<E>允许使用迭代器进行恒定时间的插入或删除，但只能顺序访问元素。换句话说，您可以向前或向后遍历列表，但在列表中查找位置所花费的时间与列表的大小成正比。Javadoc 说“索引到列表中的操作将从开头或结尾遍历列表，以较近者为准”，因此这些方法平均为O (n)（n/4步），尽管对于.index = 0
ArrayList<E>，另一方面，允许快速随机读取访问，因此您可以在恒定时间内抓取任何元素。但是从任何地方添加或删除，但最后需要将所有后面的元素转移过来，要么打开一个开口，要么填补空白。另外，如果添加的元素多于底层数组的容量，则会分配一个新数组（大小的 1.5 倍），并将旧数组复制到新数组中，因此添加到 an最坏的情况ArrayList是O(n)情况但平均保持不变。
因此，根据您打算执行的操作，您应该相应地选择实现。迭代任何一种 List 实际上同样便宜。（迭代 anArrayList在技术上更快，但除非你正在做一些对性能非常敏感的事情，否则你不应该担心这一点——它们都是常量。）
LinkedList当您重新使用现有的迭代器来插入和删除元素时，使用 a 的主要好处就出现了。然后可以通过仅在本地更改列表在O(1)中完成这些操作。在数组列表中，数组的其余部分需要移动（即复制）。另一方面，在最坏的情况下，按照O(n)LinkedList中的链接（n/2步）寻找方法，而在所需位置可以通过数学计算并在O(1)中访问。ArrayList
LinkedList当您从列表的头部添加或删除时，使用 a 的另一个好处会出现，因为这些操作是O(1) ，而对于，它们是O(n)ArrayList。请注意，这ArrayDeque可能是LinkedList添加和删除头部的一个很好的替代方法，但它不是List.
此外，如果您有大型列表，请记住内存使用量也不同。a 的每个元素LinkedList都有更多的开销，因为指向下一个和前一个元素的指针也被存储。ArrayLists没有这个开销。但是，ArrayLists无论是否实际添加了元素，都会占用为容量分配的内存。
an 的默认初始容量ArrayList非常小（Java 1.4 - 1.8 为 10）。但是由于底层实现是一个数组，如果添加很多元素，则必须调整数组的大小。当您知道要添加大量元素时，为了避免调整大小的高成本，请ArrayList使用更高的初始容量构建 。
如果从数据结构的角度来理解这两种结构，LinkedList 基本上是一个包含头节点的顺序数据结构。Node 是两个组件的包装器：一个 T 类型的值 [通过泛型接受] 和另一个对链接到它的 Node 的引用。所以，我们可以断言它是一个递归数据结构（一个节点包含另一个节点，另一个节点有另一个节点，依此类推......）。如上所述，在 LinkedList 中添加元素需要线性时间。
ArrayList 是一个可增长的数组。它就像一个常规数组。在幕后，当添加一个元素并且 ArrayList 已经满载时，它会创建另一个大小大于先前大小的数组。然后将元素从先前的数组复制到新数组，并且要添加的元素也放置在指定的索引处。
于 2008-11-27T01:49:42.357 回答
671
到目前为止，似乎没有人解决这些列表中的每一个的内存占用问题，除了普遍认为 aLinkedList比 a “多得多”，ArrayList所以我做了一些数字运算来证明两个列表究竟占用了多少 N 个空引用。
由于引用在其相关系统上是 32 位或 64 位（即使为空），因此我包含了 4 组 32 位和 64 位的数据LinkedLists以及ArrayLists.
注意：显示的ArrayList行大小适用于修剪后的列表- 实际上，an 中后备数组的容量ArrayList通常大于其当前元素数。
注意 2：（ 感谢 BeeOnRope）由于 CompressedOops 现在是 JDK6 中期及更高版本的默认值，因此以下 64 位机器的值将基本匹配它们的 32 位对应物，当然除非您特别将其关闭。
结果清楚地表明，LinkedList它远远超过ArrayList，尤其是在元素数量非常多的情况下。如果内存是一个因素，请避开LinkedLists.
我使用的公式如下，如果我做错了什么，请告诉我，我会修复它。对于 32 位或 64 位系统，“b”是 4 或 8，“n”是元素的数量。注意 mods 的原因是因为 java 中的所有对象无论是否全部使用都会占用 8 字节空间的倍数。
数组列表：
ArrayList object header + size integer + modCount integer + array reference + (array oject header + b * n) + MOD(array oject, 8) + MOD(ArrayList object, 8) == 8 + 4 + 4 + b + (12 + b * n) + MOD(12 + b * n, 8) + MOD(8 + 4 + 4 + b + (12 + b * n) + MOD(12 + b * n, 8), 8)
链表：
LinkedList object header + size integer + modCount integer + reference to header + reference to footer + (node object overhead + reference to previous element + reference to next element + reference to element) * n) + MOD(node object, 8) * n + MOD(LinkedList object, 8) == 8 + 4 + 4 + 2 * b + (8 + 3 * b) * n + MOD(8 + 3 * b, 8) * n + MOD(8 + 4 + 4 + 2 * b + (8 + 3 * b) * n + MOD(8 + 3 * b, 8) * n, 8)
于 2011-10-06T06:46:45.893 回答
283
ArrayList是你想要的。LinkedList几乎总是一个（性能）错误。
为什么LinkedList很烂：
- 它使用大量的小内存对象，因此会影响整个进程的性能。
- 许多小对象不利于缓存局部性。
- 任何索引操作都需要遍历，即具有 O(n) 性能。这在源代码中并不明显，导致算法 O(n) 比
ArrayList使用时慢。 - 获得良好的性能是棘手的。
- 即使 big-O 性能与 相同
ArrayList，它也可能会明显变慢。 - 在源代码中看到它很不和谐，
LinkedList因为它可能是错误的选择。
于 2008-11-27T14:20:16.133 回答
169
Algorithm ArrayList LinkedList
seek front O(1) O(1)
seek back O(1) O(1)
seek to index O(1) O(N)
insert at front O(N) O(1)
insert at back O(1) O(1)
insert after an item O(N) O(1)
算法：Big-Oh Notation（已归档）
ArrayLists 适用于一次写入多次读取或附加程序，但不适合从前面或中间添加/删除。
于 2010-04-08T20:33:35.467 回答
153
作为一个已经在超大规模 SOA Web 服务上进行操作性能工程大约十年的人，我更喜欢 LinkedList 的行为而不是 ArrayList。虽然 LinkedList 的稳态吞吐量更差，因此可能会导致购买更多硬件 - ArrayList 在压力下的行为可能会导致集群中的应用程序以近乎同步的方式扩展其阵列，并且对于大阵列大小可能会导致缺乏响应能力在应用程序和中断，而在压力下，这是灾难性的行为。
同样，您可以从默认吞吐量的终身垃圾收集器中获得更好的应用程序吞吐量，但是一旦您获得具有 10GB 堆的 Java 应用程序，您可能会在 Full GC 期间锁定应用程序 25 秒，这会导致 SOA 应用程序超时和失败如果它发生得太频繁，就会破坏你的 SLA。尽管 CMS 收集器占用更多资源并且无法达到相同的原始吞吐量，但它是一个更好的选择，因为它具有更高的可预测性和更小的延迟。
如果您所说的性能是吞吐量并且您可以忽略延迟，那么 ArrayList 只是性能更好的选择。根据我的工作经验，我不能忽视最坏情况下的延迟。
更新（2021 年 8 月 27 日——10 年后）：这个答案（我对 SO 历史上最受好评的答案）很可能是错误的（原因在下面的评论中列出）。我想补充一点，ArrayList 将优化内存的顺序读取并最大限度地减少缓存行和 TLB 未命中等。相比之下，当数组增长超过界限时的复制开销可能是无关紧要的（并且可以通过高效的 CPU 操作来完成）。考虑到硬件趋势，随着时间的推移，这个答案也可能变得更糟。LinkedList 可能有意义的唯一情况是高度做作的事情，您有数千个列表，其中任何一个都可能增长到 GB 大小，但在分配列表和设置它们时无法做出好的猜测所有到 GB 大小的都会炸毁堆。如果你发现了这样的问题，那么它确实需要重新设计你的解决方案（我不喜欢轻易建议重新设计旧代码，因为我自己维护成堆的旧代码，但那将是一个非常好的案例，原始设计只是跑出了跑道，确实需要被淘汰）。不过，我仍然会将我几十年前的糟糕观点留在那里供您阅读。简单，合乎逻辑而且非常错误。不过，我仍然会将我几十年前的糟糕意见留在那里供您阅读。简单，合乎逻辑而且非常错误。不过，我仍然会将我几十年前的糟糕意见留在那里供您阅读。简单，合乎逻辑而且非常错误。
于 2011-01-01T20:23:52.100 回答
117
是的，我知道，这是一个古老的问题，但我会投入两分钱：
LinkedList在性能方面几乎总是错误的选择。有一些非常特殊的算法需要 LinkedList，但这些算法非常非常罕见，并且该算法通常特别依赖于 LinkedList 在列表中间相对快速地插入和删除元素的能力，一旦你导航到那里使用 ListIterator。
LinkedList 优于 ArrayList 的一个常见用例是：队列。但是，如果您的目标是性能，而不是 LinkedList，您还应该考虑使用 ArrayBlockingQueue （如果您可以提前确定队列大小的上限，并且可以预先分配所有内存），或者这个CircularArrayList 实现. （是的，它是从 2001 年开始的，因此您需要对其进行泛化，但我得到的性能比与刚刚在最近的 JVM 中引用的文章中的内容相当）
于 2009-05-19T11:21:20.293 回答
93
LinkedList 的作者 Joshua Bloch：
有人真的使用 LinkedList 吗？我写了它，我从不使用它。
链接：https ://twitter.com/joshbloch/status/583813919019573248
我很抱歉这个答案没有像其他答案那样信息丰富，但我认为如果不透露的话，这将是最不言自明的。
于 2017-03-01T10:47:43.927 回答
79
这是一个效率问题。LinkedList添加和删除元素很快，但访问特定元素很慢。ArrayList访问特定元素的速度很快，但添加到任一端可能很慢，尤其是在中间删除很慢。
Array vs ArrayList vs LinkedList vs Vector更深入， Linked List也是如此。
于 2008-11-27T01:39:59.897 回答
57
正确或错误：请在本地执行测试并自行决定！
编辑/删除LinkedList比ArrayList.
ArrayList, backed by Array，需要双倍大小，在大容量应用中效果更差。
下面是每个操作的单元测试结果。时间以纳秒为单位。
Operation ArrayList LinkedList
AddAll (Insert) 101,16719 2623,29291
Add (Insert-Sequentially) 152,46840 966,62216
Add (insert-randomly) 36527 29193
remove (Delete) 20,56,9095 20,45,4904
contains (Search) 186,15,704 189,64,981
这是代码：
import org.junit.Assert;
import org.junit.Test;
import java.util.*;
public class ArrayListVsLinkedList {
private static final int MAX = 500000;
String[] strings = maxArray();
////////////// ADD ALL ////////////////////////////////////////
@Test
public void arrayListAddAll() {
Watch watch = new Watch();
List<String> stringList = Arrays.asList(strings);
List<String> arrayList = new ArrayList<String>(MAX);
watch.start();
arrayList.addAll(stringList);
watch.totalTime("Array List addAll() = ");//101,16719 Nanoseconds
}
@Test
public void linkedListAddAll() throws Exception {
Watch watch = new Watch();
List<String> stringList = Arrays.asList(strings);
watch.start();
List<String> linkedList = new LinkedList<String>();
linkedList.addAll(stringList);
watch.totalTime("Linked List addAll() = "); //2623,29291 Nanoseconds
}
//Note: ArrayList is 26 time faster here than LinkedList for addAll()
///////////////// INSERT /////////////////////////////////////////////
@Test
public void arrayListAdd() {
Watch watch = new Watch();
List<String> arrayList = new ArrayList<String>(MAX);
watch.start();
for (String string : strings)
arrayList.add(string);
watch.totalTime("Array List add() = ");//152,46840 Nanoseconds
}
@Test
public void linkedListAdd() {
Watch watch = new Watch();
List<String> linkedList = new LinkedList<String>();
watch.start();
for (String string : strings)
linkedList.add(string);
watch.totalTime("Linked List add() = "); //966,62216 Nanoseconds
}
//Note: ArrayList is 9 times faster than LinkedList for add sequentially
/////////////////// INSERT IN BETWEEN ///////////////////////////////////////
@Test
public void arrayListInsertOne() {
Watch watch = new Watch();
List<String> stringList = Arrays.asList(strings);
List<String> arrayList = new ArrayList<String>(MAX + MAX / 10);
arrayList.addAll(stringList);
String insertString0 = getString(true, MAX / 2 + 10);
String insertString1 = getString(true, MAX / 2 + 20);
String insertString2 = getString(true, MAX / 2 + 30);
String insertString3 = getString(true, MAX / 2 + 40);
watch.start();
arrayList.add(insertString0);
arrayList.add(insertString1);
arrayList.add(insertString2);
arrayList.add(insertString3);
watch.totalTime("Array List add() = ");//36527
}
@Test
public void linkedListInsertOne() {
Watch watch = new Watch();
List<String> stringList = Arrays.asList(strings);
List<String> linkedList = new LinkedList<String>();
linkedList.addAll(stringList);
String insertString0 = getString(true, MAX / 2 + 10);
String insertString1 = getString(true, MAX / 2 + 20);
String insertString2 = getString(true, MAX / 2 + 30);
String insertString3 = getString(true, MAX / 2 + 40);
watch.start();
linkedList.add(insertString0);
linkedList.add(insertString1);
linkedList.add(insertString2);
linkedList.add(insertString3);
watch.totalTime("Linked List add = ");//29193
}
//Note: LinkedList is 3000 nanosecond faster than ArrayList for insert randomly.
////////////////// DELETE //////////////////////////////////////////////////////
@Test
public void arrayListRemove() throws Exception {
Watch watch = new Watch();
List<String> stringList = Arrays.asList(strings);
List<String> arrayList = new ArrayList<String>(MAX);
arrayList.addAll(stringList);
String searchString0 = getString(true, MAX / 2 + 10);
String searchString1 = getString(true, MAX / 2 + 20);
watch.start();
arrayList.remove(searchString0);
arrayList.remove(searchString1);
watch.totalTime("Array List remove() = ");//20,56,9095 Nanoseconds
}
@Test
public void linkedListRemove() throws Exception {
Watch watch = new Watch();
List<String> linkedList = new LinkedList<String>();
linkedList.addAll(Arrays.asList(strings));
String searchString0 = getString(true, MAX / 2 + 10);
String searchString1 = getString(true, MAX / 2 + 20);
watch.start();
linkedList.remove(searchString0);
linkedList.remove(searchString1);
watch.totalTime("Linked List remove = ");//20,45,4904 Nanoseconds
}
//Note: LinkedList is 10 millisecond faster than ArrayList while removing item.
///////////////////// SEARCH ///////////////////////////////////////////
@Test
public void arrayListSearch() throws Exception {
Watch watch = new Watch();
List<String> stringList = Arrays.asList(strings);
List<String> arrayList = new ArrayList<String>(MAX);
arrayList.addAll(stringList);
String searchString0 = getString(true, MAX / 2 + 10);
String searchString1 = getString(true, MAX / 2 + 20);
watch.start();
arrayList.contains(searchString0);
arrayList.contains(searchString1);
watch.totalTime("Array List addAll() time = ");//186,15,704
}
@Test
public void linkedListSearch() throws Exception {
Watch watch = new Watch();
List<String> linkedList = new LinkedList<String>();
linkedList.addAll(Arrays.asList(strings));
String searchString0 = getString(true, MAX / 2 + 10);
String searchString1 = getString(true, MAX / 2 + 20);
watch.start();
linkedList.contains(searchString0);
linkedList.contains(searchString1);
watch.totalTime("Linked List addAll() time = ");//189,64,981
}
//Note: Linked List is 500 Milliseconds faster than ArrayList
class Watch {
private long startTime;
private long endTime;
public void start() {
startTime = System.nanoTime();
}
private void stop() {
endTime = System.nanoTime();
}
public void totalTime(String s) {
stop();
System.out.println(s + (endTime - startTime));
}
}
private String[] maxArray() {
String[] strings = new String[MAX];
Boolean result = Boolean.TRUE;
for (int i = 0; i < MAX; i++) {
strings[i] = getString(result, i);
result = !result;
}
return strings;
}
private String getString(Boolean result, int i) {
return String.valueOf(result) + i + String.valueOf(!result);
}
}
于 2011-09-21T22:59:23.773 回答
55
ArrayList本质上是一个数组。LinkedList实现为双链表。
get很清楚。O(1) for ArrayList，因为ArrayList允许使用索引进行随机访问。O(n) for LinkedList，因为它需要先找到索引。add注意：和有不同的版本remove。
LinkedList添加和删除速度更快，但获取速度较慢。简而言之，LinkedList如果出现以下情况，应该首选：
- 没有大量随机访问元素
- 有大量的添加/删除操作
===数组列表 ===
- 加(E e)
- 在 ArrayList 末尾添加
- 需要调整内存大小的成本。
- O(n) 最差，O(1) 摊销
- 添加（int索引，E元素）
- 添加到特定的索引位置
- 需要转移和可能的内存调整成本
- 在）
- 删除（整数索引）
- 移除指定元素
- 需要转移和可能的内存调整成本
- 在）
- 删除（对象o）
- 从此列表中删除第一次出现的指定元素
- 需要先搜索元素，然后转移和可能的内存调整成本
- 在）
===链表===
加(E e)
- 添加到列表的末尾
- O(1)
添加（int索引，E元素）
- 在指定位置插入
- 需要先找到位置
- 在）
- 消除（）
- 删除列表的第一个元素
- O(1)
- 删除（整数索引）
- 移除指定索引的元素
- 需要先找到元素
- 在）
- 删除（对象o）
- 删除指定元素的第一次出现
- 需要先找到元素
- 在）
这是来自programcreek.com的图（add并且remove是第一种类型，即在列表末尾添加一个元素并删除列表中指定位置的元素。）：
于 2013-04-21T00:03:47.817 回答
44
TL;DR由于现代计算机体系结构，ArrayList对于几乎任何可能的用例都将显着提高效率 - 因此LinkedList除了一些非常独特和极端的情况外，应避免使用。
理论上，LinkedList 对于add(E element)
此外，在列表中间添加一个元素应该非常有效。
实践非常不同，因为 LinkedList 是一个Cache Hostile Data 结构。从性能 POV 来看 - 很少有比Cache-friendlyLinkedList性能更好的情况。 ArrayList
以下是在随机位置插入元素的基准测试结果。如您所见 - 数组列表效率更高，尽管理论上列表中间的每个插入都需要“移动”数组的n 个后面的元素（较低的值更好）：
在下一代硬件上工作（更大、更高效的缓存）——结果更具决定性：
LinkedList 需要更多的时间来完成同样的工作。source 源代码
这有两个主要原因：
主要是- 的节点
LinkedList随机分散在内存中。RAM（“随机存取存储器”）并不是真正随机的，需要提取内存块进行缓存。这个操作需要时间，而且当这种抓取频繁发生时——缓存中的内存页需要一直被替换->缓存未命中->缓存效率不高。ArrayList元素存储在连续内存上——这正是现代 CPU 架构正在优化的目标。Secondary
LinkedList需要保留后向/前向指针，这意味着存储的每个值的内存消耗是ArrayList.
顺便说一句， DynamicIntArray是一个自定义的 ArrayList 实现，它持有Int（原始类型）而不是 Objects - 因此所有数据实际上都是相邻存储的 - 因此效率更高。
要记住的一个关键因素是，获取内存块的成本比访问单个内存单元的成本更重要。这就是为什么读取器 1MB 的顺序内存比从不同的内存块读取这么多的数据快 400 倍：
Latency Comparison Numbers (~2012)
----------------------------------
L1 cache reference 0.5 ns
Branch mispredict 5 ns
L2 cache reference 7 ns 14x L1 cache
Mutex lock/unlock 25 ns
Main memory reference 100 ns 20x L2 cache, 200x L1 cache
Compress 1K bytes with Zippy 3,000 ns 3 us
Send 1K bytes over 1 Gbps network 10,000 ns 10 us
Read 4K randomly from SSD* 150,000 ns 150 us ~1GB/sec SSD
Read 1 MB sequentially from memory 250,000 ns 250 us
Round trip within same datacenter 500,000 ns 500 us
Read 1 MB sequentially from SSD* 1,000,000 ns 1,000 us 1 ms ~1GB/sec SSD, 4X memory
Disk seek 10,000,000 ns 10,000 us 10 ms 20x datacenter roundtrip
Read 1 MB sequentially from disk 20,000,000 ns 20,000 us 20 ms 80x memory, 20X SSD
Send packet CA->Netherlands->CA 150,000,000 ns 150,000 us 150 ms
资料来源：每个程序员都应该知道的延迟数字
为了更清楚地说明这一点，请检查将元素添加到列表开头的基准。这是一个用例，在理论上，LinkedList应该真正发光，并且ArrayList应该呈现较差甚至更坏的结果：
注意：这是 C++ 标准库的基准测试，但我之前的经验表明 C++ 和 Java 的结果非常相似。源代码
复制连续的大量内存是现代 CPU 优化的操作 - 改变理论并实际上再次ArrayList/Vector更高效
致谢：此处发布的所有基准均由Kjell Hedström创建。更多数据可以在他的博客上找到
于 2018-10-19T02:53:16.687 回答
36
ArrayList是随机访问的，而LinkedList扩展和删除元素非常便宜。大多数情况下，ArrayList没问题。
除非您创建了大型列表并测量了瓶颈，否则您可能永远不需要担心差异。
于 2008-11-27T01:41:47.740 回答
25
如果您的代码有add(0)and remove(0)，请使用LinkedListand 它更漂亮的addFirst()andremoveFirst()方法。否则，使用ArrayList.
当然，Guava的ImmutableList是你最好的朋友。
于 2008-11-28T02:04:15.433 回答
23
让我们比较一下 LinkedList 和 ArrayList wrt 下面的参数：
一、实施
ArrayList是列表接口的可调整大小的数组实现，而
LinkedList是列表接口的双向链表实现。
2. 性能
get(int index) 或搜索操作
ArrayList get(int index) 操作以恒定时间运行，即 O(1) 而
LinkedList get(int index) 操作运行时间为 O(n) 。
ArrayList比 LinkedList 更快的原因是 ArrayList 对其元素使用基于索引的系统，因为它在内部使用数组数据结构，另一方面，
LinkedList不为其元素提供基于索引的访问，因为它从开头或结尾（以较近者为准）进行迭代以检索指定元素索引处的节点。
insert() 或 add(Object) 操作
LinkedList中的插入通常比 ArrayList 快。在 LinkedList 添加或插入是 O(1) 操作。
而在ArrayList中，如果数组是完整的，即最坏的情况，则调整数组大小并将元素复制到新数组会产生额外的成本，这使得 ArrayList 中的添加操作的运行时间为 O(n)，否则为 O(1) .
删除（int）操作
LinkedList 中的删除操作一般与ArrayList 相同，即O(n)。
在LinkedList中，有两个重载的 remove 方法。一种是不带任何参数的 remove()，它删除列表的头部并以恒定时间 O(1) 运行。LinkedList 中另一个重载的删除方法是 remove(int) 或 remove(Object)，它删除作为参数传递的 Object 或 int。此方法遍历 LinkedList 直到找到 Object 并将其从原始列表中取消链接。因此，此方法运行时间为 O(n)。
而在ArrayList remove(int) 方法涉及将元素从旧数组复制到新的更新数组，因此它的运行时间是 O(n)。
3. 反向迭代器
LinkedList可以使用 descendingIterator() 反向迭代，而
ArrayList中没有 descendingIterator() ，因此我们需要编写自己的代码来反向迭代 ArrayList。
4. 初始容量
如果构造函数没有重载，则ArrayList创建一个初始容量为 10 的空列表，而
LinkedList 只构造空列表，没有任何初始容量。
5. 内存开销
与 ArrayList 相比， LinkedList中的内存开销更大，因为 LinkedList 中的节点需要维护下一个和前一个节点的地址。尽管
在ArrayList 中，每个索引只保存实际的对象（数据）。
于 2017-02-10T15:14:02.713 回答
23
我通常根据我在该特定列表上执行的操作的时间复杂性使用一个而不是另一个。
|---------------------|---------------------|--------------------|------------|
| Operation | ArrayList | LinkedList | Winner |
|---------------------|---------------------|--------------------|------------|
| get(index) | O(1) | O(n) | ArrayList |
| | | n/4 steps in avg | |
|---------------------|---------------------|--------------------|------------|
| add(E) | O(1) | O(1) | LinkedList |
| |---------------------|--------------------| |
| | O(n) in worst case | | |
|---------------------|---------------------|--------------------|------------|
| add(index, E) | O(n) | O(n) | LinkedList |
| | n/2 steps | n/4 steps | |
| |---------------------|--------------------| |
| | | O(1) if index = 0 | |
|---------------------|---------------------|--------------------|------------|
| remove(index, E) | O(n) | O(n) | LinkedList |
| |---------------------|--------------------| |
| | n/2 steps | n/4 steps | |
|---------------------|---------------------|--------------------|------------|
| Iterator.remove() | O(n) | O(1) | LinkedList |
| ListIterator.add() | | | |
|---------------------|---------------------|--------------------|------------|
|--------------------------------------|-----------------------------------|
| ArrayList | LinkedList |
|--------------------------------------|-----------------------------------|
| Allows fast read access | Retrieving element takes O(n) |
|--------------------------------------|-----------------------------------|
| Adding an element require shifting | o(1) [but traversing takes time] |
| all the later elements | |
|--------------------------------------|-----------------------------------|
| To add more elements than capacity |
| new array need to be allocated |
|--------------------------------------|
于 2019-01-14T12:54:12.597 回答
22
我知道这是一篇旧帖子，但老实说，我不敢相信没有人提到过LinkedListimplements Deque。看看Deque(and Queue) 中的方法；如果您想要一个公平的比较，请尝试运行并LinkedList进行ArrayDeque功能比较。
于 2013-04-19T07:26:48.140 回答
20
这是ArrayListandLinkedList和 also中的 Big-O 符号CopyOnWrite-ArrayList：
数组列表
get O(1)
add O(1)
contains O(n)
next O(1)
remove O(n)
iterator.remove O(n)
链表
get O(n)
add O(1)
contains O(n)
next O(1)
remove O(1)
iterator.remove O(1)
CopyOnWrite-ArrayList
get O(1)
add O(n)
contains O(n)
next O(1)
remove O(n)
iterator.remove O(n)
基于这些，您必须决定选择什么。:)
于 2012-11-06T14:32:08.023 回答
15
除了上面的其他好论点之外，您还应该注意ArrayListimplementsRandomAccess接口，而LinkedListimplements Queue。
因此，它们以某种方式解决了略有不同的问题，效率和行为有所不同（请参阅他们的方法列表）。
于 2008-11-27T01:47:34.280 回答
11
这取决于您将在列表中执行更多操作。
ArrayList访问索引值更快。插入或删除对象时情况更糟。
要了解更多信息，请阅读任何有关数组和链表之间区别的文章。
于 2008-11-27T01:42:03.217 回答
9
数组列表本质上是一个具有添加项目等方法的数组（您应该改用通用列表）。它是可以通过索引器访问的项目集合（例如 [0]）。它意味着从一个项目到下一个项目的进展。
链表指定从一个项目到下一个项目的进展（项目 a -> 项目 b）。您可以使用数组列表获得相同的效果，但链表绝对说明了应该在前一个之后的项目。
于 2010-04-20T15:32:01.660 回答
9
请参阅Java 教程 - 列出实现。
于 2011-09-05T06:33:52.753 回答
8
链表的一个重要特征（我在另一个答案中没有读到）是两个列表的串联。对于数组，这是 O(n)（+ 一些重新分配的开销）对于链表，这只是 O(1) 或 O(2) ;-)
重要提示：对于 Java，LinkedList这是不正确的！请参阅Java中的链表是否有快速的连接方法？
于 2010-03-22T22:32:31.243 回答
8
ArrayList 和 LinkedList 各有优缺点。
ArrayList 使用连续的内存地址，而 LinkedList 使用指向下一个节点的指针。因此，当您想在 ArrayList 中查找元素时，比使用 LinkedList 进行 n 次迭代要快。
另一方面，LinkedList 中的插入和删除要容易得多，因为您只需更改指针，而 ArrayList 意味着对任何插入或删除都使用移位操作。
如果您的应用程序中有频繁的检索操作，请使用 ArrayList。如果您经常插入和删除，请使用 LinkedList。
于 2017-05-15T18:06:30.810 回答
7
1) 底层数据结构
ArrayList 和 LinkedList 之间的第一个区别在于 ArrayList 由 Array 支持，而 LinkedList 由 LinkedList 支持。这将导致性能上的进一步差异。
2) LinkedList 实现 Deque
add()ArrayList 和 LinkedList 的另一个区别是，除了 List 接口之外，LinkedList 还实现了 Deque 接口，该接口为andpoll()和其他几个 Deque 函数提供了先进先出操作。3）在ArrayList中添加元素 在ArrayList中添加元素如果不触发Array的re-size是O（1）操作，在这种情况下它变为O（log（n）），另一方面，在其中追加一个元素LinkedList 是 O(1) 操作，因为它不需要任何导航。
4) 从一个位置移除一个元素
为了从特定索引中删除一个元素，例如remove(index)调用根据接近度从任一方向遍历。
5) 遍历 ArrayList 或 LinkedList
迭代是 LinkedList 和 ArrayList 的 O(n) 操作，其中 n 是元素的编号。
6) 从某个位置检索元素
该get(index)操作在 ArrayList 中为 O(1)，而在 LinkedList 中为 O(n/2)，因为它需要遍历该条目。不过，在大 O 表示法中，O(n/2) 只是 O(n)，因为我们忽略了那里的常数。
7) 内存
LinkedList 使用一个包装对象 Entry，它是一个静态嵌套类，用于存储数据和两个节点 next 和 previous，而 ArrayList 只是将数据存储在 Array 中。
因此，ArrayList 的内存需求似乎比 LinkedList 少，除了 Array 在将内容从一个 Array 复制到另一个 Array 时执行重新调整大小操作的情况。
如果 Array 足够大，此时可能会占用大量内存并触发垃圾收集，这会减慢响应时间。
从 ArrayList 与 LinkedList 之间的所有上述差异来看，看起来 ArrayList 在几乎所有情况下都是比 LinkedList 更好的选择，除非您执行频繁add()操作而不是remove(), 或get()。
修改链表比修改 ArrayList 更容易，特别是当您从开始或结束添加或删除元素时，因为链表内部保留了这些位置的引用，并且它们可以在 O(1) 时间内访问。
换句话说，你不需要遍历链表到达你想要添加元素的位置，那样的话，加法就变成了O(n)的操作。例如，在链表中间插入或删除一个元素。
在我看来，对于 Java 中的大多数实际目的，使用 ArrayList 而不是 LinkedList。
于 2018-06-07T10:33:41.423 回答
6
我已经阅读了回复，但在一种情况下，我总是在 ArrayList 上使用 LinkedList，我想分享以听取意见：
每次我有一个方法返回从数据库获得的数据列表时，我总是使用 LinkedList。
我的理由是，因为不可能确切知道我得到了多少结果，所以不会浪费内存（就像 ArrayList 中的容量和实际元素数量之间的差异一样），并且不会浪费时间尝试复制容量。
就 ArrayList 而言，我同意至少您应该始终使用具有初始容量的构造函数，以尽可能减少数组的重复。
于 2011-10-03T23:23:00.370 回答
5
ArrayList 中的 get(i) 操作比 LinkedList 更快，因为：
ArrayList： List 接口的 Resizable-array 实现
LinkedList： List 和 Deque 接口的双向链表实现
索引到列表中的操作将从开头或结尾遍历列表，以更接近指定索引的为准。
于 2013-04-25T07:57:38.497 回答
5
ArrayList两者LinkedList的实现List interface 及其方法和结果几乎相同。但是，它们之间几乎没有区别，这取决于要求，它们使一个比另一个更好。
ArrayList 与 LinkedList
1）Search: ArrayList与搜索操作相比，LinkedList搜索操作相当快。get(int index)inArrayList给出了O(1)while LinkedListperformance is的表现O(n)。
Reason: ArrayList为其元素维护基于索引的系统，因为它隐式使用数组数据结构，这使得在列表中搜索元素的速度更快。另一方面LinkedList实现了双向链表，它需要遍历所有元素以搜索元素。
2）Deletion: LinkedList删除操作提供O(1)性能，同时ArrayList提供可变性能：O(n)在最坏的情况下（在删除第一个元素时）和O(1)在最好的情况下（在删除最后一个元素时）。
结论：LinkedList 元素删除比 ArrayList 更快。
原因：LinkedList 的每个元素都维护着两个指针（地址），它们指向列表中的两个相邻元素。因此，删除只需要更改将要删除的节点的两个相邻节点（元素）中的指针位置。而在 ArrayList 中，所有元素都需要移动以填充已删除元素创建的空间。
3) Inserts Performance: LinkedListadd 方法提供性能O(1)，而在最坏的情况下提供。原因与删除的解释相同。ArrayListO(n)
4)Memory Overhead: ArrayList维护索引和元素数据，同时LinkedList维护元素数据和相邻节点的两个指针
因此，LinkedList 中的内存消耗相对较高。
这些类之间几乎没有相似之处，如下所示：
- ArrayList 和 LinkedList 都是 List 接口的实现。
- 它们都维护元素插入顺序，这意味着在显示 ArrayList 和 LinkedList 元素时，结果集将具有与元素插入列表相同的顺序。
- 这两个类都是非同步的，可以使用 Collections.synchronizedList 方法显式同步。
- 这些类返回的 和 是
iterator（如果在迭代器创建后的任何时候对 list 进行了结构修改，除了通过自己的 remove 或 add 方法之外的任何方式，迭代器将a ）。listIteratorfail-fastiterator’sthrowConcurrentModificationException
什么时候用 LinkedList，什么时候用 ArrayList？
- 如上所述，插入和删除操作
(O(1))与LinkedList.ArrayList(O(n))因此，如果应用中需要频繁的增删改查，那么LinkedList是最好的选择。
- 搜索 (
get method) 操作速度快Arraylist (O(1))但速度不快LinkedList (O(n))因此，如果添加和删除操作较少，搜索操作要求较多，ArrayList 将是您的最佳选择。
于 2016-11-02T09:00:23.477 回答
3
对于 ArrayLists 和 LinkedLists，两者remove()都insert()具有 O(n) 的运行时效率。然而，线性处理时间背后的原因来自两个截然不同的原因：
在 ArrayList 中，您可以在 O(1) 中找到元素，但实际上删除或插入某些东西会使它成为 O(n)，因为需要更改以下所有元素。
在 LinkedList 中，实际上需要 O(n) 才能到达所需的元素，因为我们必须从头开始，直到到达所需的索引。实际上删除或插入是不变的，因为我们只需要更改 1 个引用remove()和 2 个引用insert()。
两者中哪一个更快插入和删除取决于它发生的位置。如果我们更接近开始，LinkedList 会更快，因为我们必须通过相对较少的元素。如果我们更接近终点，ArrayList 会更快，因为我们在恒定时间内到达那里，只需要更改它后面的少数剩余元素。当恰好在中间完成时，LinkedList 会更快，因为遍历 n 个元素比移动 n 个值要快。
奖励：虽然没有办法为 ArrayList 制作这两种方法 O(1)，但实际上在 LinkedLists 中有一种方法可以做到这一点。假设我们要遍历整个 List 删除和插入元素。通常，您将使用 LinkedList 从一开始就为每个元素开始，我们也可以使用迭代器“保存”我们正在处理的当前元素。在迭代器的帮助下，我们在使用 LinkedList 时获得了 O(1) 的remove()效率insert()。使它成为唯一的性能优势，我知道 LinkedList 总是比 ArrayList 更好。
于 2016-06-11T20:40:29.867 回答
3
我在这里看到的一项测试只进行一次测试。但我注意到的是，您需要多次运行这些测试，最终它们的时间会收敛。基本上，JVM 需要预热。对于我的特定用例，我需要将项目添加/删除到一个增长到大约 500 个项目的列表中。在我的测试LinkedList中，结果更快，LinkedList大约 50,000 NS 和ArrayList大约 90,000 NS ......给予或接受。请参阅下面的代码。
public static void main(String[] args) {
List<Long> times = new ArrayList<>();
for (int i = 0; i < 100; i++) {
times.add(doIt());
}
System.out.println("avg = " + (times.stream().mapToLong(x -> x).average()));
}
static long doIt() {
long start = System.nanoTime();
List<Object> list = new LinkedList<>();
//uncomment line below to test with ArrayList
//list = new ArrayList<>();
for (int i = 0; i < 500; i++) {
list.add(i);
}
Iterator it = list.iterator();
while (it.hasNext()) {
it.next();
it.remove();
}
long end = System.nanoTime();
long diff = end - start;
//uncomment to see the JVM warmup and get faster for the first few iterations
//System.out.println(diff)
return diff;
}
于 2018-08-04T18:52:06.510 回答
1
ArrayList 扩展了 AbstractList 并实现了 List 接口。ArrayList 是动态数组。
可以说它基本上是为了克服数组的缺点而创建
的 LinkedList 类扩展了 AbstractSequentialList 并实现了 List、Deque 和 Queue 接口。
性能
arraylist.get()是 O(1) 而linkedlist.get()is O(n)
arraylist.add()是 O(1) 并且linkedlist.add()是 0(1)
arraylist.contains()是 O(n) 并且linkedlist.contains()是 O(n)
arraylist.next()是 O(1) 并且linkedlist.next()是 O(1)
arraylist.remove()是 O(n)而在数组列表中是 O( linkedlist.remove()1 )是 O(n)而在链表
中是 O(1)iterator.remove()iterator.remove()
于 2018-02-20T21:51:19.830 回答
1
我的经验法则是，如果我需要 a Collection（即不需要是 a List），那么ArrayList如果您事先知道尺寸，或者可以自信地知道尺寸，或者知道它不会有太大变化，请使用。如果您需要随机访问（即您使用get(index)），请避免使用LinkedList. 基本上，LinkedList仅当您不需要索引访问并且不知道要分配的集合的（近似）大小时才使用。此外，如果您要进行大量添加和删除（再次通过Collection界面），那么 LinkedList 可能更可取。
于 2019-10-10T00:09:07.827 回答
-2
我应该什么时候使用LinkedList？主要使用堆栈或使用缓冲区时。我应该什么时候使用ArrayList？只有在使用索引时，否则您可以将 HashTable 与链表一起使用，然后您将获得：
哈希表+链表
- 通过密钥O(1) 访问，
- 按键O(1)插入，
- 按键删除O(1)
- 在使用版本控制时，有一个技巧可以用 O(1) 实现 RemoveAll / SetAll
这似乎是一个很好的解决方案，在大多数情况下，您应该知道：HashTable 占用大量磁盘空间，因此当您需要管理 1,000,000 个元素列表时，它可能变得很重要。这可能发生在服务器实现中，在客户端中很少发生。
也看看红黑树
- 随机访问日志（n），
- 插入日志（n），
- 删除日志（n）
于 2012-06-11T09:08:06.680 回答
-8
首先使用 Vector 代替 ArrayList 因为您可以覆盖 insureCapasity 方法，在 ArrayList 中是私有的并添加 1.5 大小的当前数组https://docs.oracle.com/javase/8/docs/api/java/util/Vector.html #ensureCapacity-int-
在许多情况下，linkedList 可能会更好，las 具有很大的优势，即您可以插入高频数据，因此列表的大小变化非常快，并且您无法为数字元素分配大小。从理论上讲，您可能会遇到诸如“内存不足”之类的错误，但在现代计算机中，您有 16G 和交换磁盘，因此如果您列出的是 billoins 元素，则与 15-20 年前相比，您可能会失败。
于 2020-06-08T10:51:09.763 回答