我一直是一个简单使用的人：
List<String> names = new ArrayList<>();
我使用接口作为可移植性的类型名称，这样当我问类似这样的问题时，我就可以修改代码。
LinkedList何时应用于ArrayList，反之亦然？
当前回答
到目前为止，除了人们普遍认为LinkedList比ArrayList“多得多”之外，似乎没有人解决这些列表中每一个的内存占用问题，所以我做了一些数字处理，以证明这两个列表对于N个空引用所占的空间。
由于引用在其相对系统上是32位或64位（即使为空），因此我为32位和64位LinkedList和ArrayList包含了4组数据。
注意：ArrayList行显示的大小是用于修剪列表的-实际上，ArrayList中的后备数组的容量通常大于其当前元素计数。
注2：（感谢BeeOnRope）由于压缩Oops现在是默认值，从JDK6中期开始，以下64位机器的值将基本上与32位机器的对应值相匹配，当然，除非您特意关闭它。
结果清楚地表明，LinkedList比ArrayList多得多，尤其是元素数非常高的情况。如果内存是一个因素，请避开LinkedList。
我使用的公式如下，如果我做错了什么，请告诉我，我会改正的对于32位或64位系统，b’是4或8，而n’是元素的数量。注意mods的原因是因为java中的所有对象都将占用8字节的倍数空间，而不管是否全部使用。
阵列列表：
ArrayList对象头+大小整数+modCount整数+数组引用+（数组项目头+b*n）+MOD
链接列表：
LinkedList对象标头+大小整数+modCount整数+对标头的引用+对页脚的引用+（节点对象开销+对上一元素的引用+下一元素的参考+对元素的引用）*n）+MOD（节点对象，8）*n+MOD， 8)
其他回答
是的，我知道，这是一个古老的问题，但我会投入我的两分钱：
LinkedList在性能方面几乎总是错误的选择。有一些非常具体的算法需要LinkedList，但这些算法非常非常罕见，并且该算法通常具体取决于LinkedLists在使用ListIterator导航到列表中间后相对快速地插入和删除元素的能力。
有一个常见的用例LinkedList优于ArrayList：队列。但是，如果您的目标是性能，那么您也应该考虑使用ArrayBlockingQueue（如果您可以提前确定队列大小的上限，并且能够提前分配所有内存），而不是LinkedList，或者使用CircularArray实现。（是的，它来自2001年，因此您需要对其进行一般化，但我得到的性能比与最近一篇JVM文章中引用的性能比相当）
这是一个效率问题。LinkedList添加和删除元素很快，但访问特定元素很慢。ArrayList访问特定元素的速度很快，但添加到两端的速度可能很慢，尤其是删除在中间的速度慢。
Array vs ArrayList vs LinkedList vs Vector更深入，同样如此链接列表。
正确或不正确：请在本地执行测试并自行决定！
LinkedList中的编辑/删除速度比ArrayList快。
Array支持的ArrayList需要两倍的大小，在大容量应用程序中更糟糕。
以下是每个操作的单元测试结果。计时单位为纳秒。
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);
}
}
ArrayList本质上是一个数组。LinkedList实现为双链接列表。
答案很清楚。O（1）表示ArrayList，因为ArrayList允许使用索引进行随机访问。O（n）表示LinkedList，因为它需要首先查找索引。注意：添加和删除有不同的版本。
LinkedList在添加和删除时速度更快，但在获取时速度较慢。简而言之，在以下情况下，应首选LinkedList：
元素没有大量的随机访问有大量的添加/删除操作
==阵列列表===
添加（E E）在ArrayList末尾添加需要内存大小调整成本。O（n）最差，O（1）摊销add（int索引，E元素）添加到特定索引位置需要移动和可能的内存调整成本O（n）删除（int索引）删除指定的元素需要移动和可能的内存调整成本O（n）删除（对象o）从此列表中删除第一个出现的指定元素需要先搜索元素，然后移动&可能的内存调整成本O（n）
==链接列表===
添加（E E）添加到列表末尾O（1）add（int索引，E元素）在指定位置插入需要先找到位置O（n）删除（）删除列表的第一个元素O（1）删除（int索引）删除具有指定索引的元素需要先找到元素O（n）删除（对象o）删除指定元素的第一个引用需要先找到元素O（n）
这是programcreek.com中的一个图（add和remove是第一种类型，即在列表末尾添加元素，然后在列表中的指定位置删除元素）：
我知道这是一篇老帖子，但我真的不敢相信没有人提到LinkedList实现了Deque。只需查看Deque（和Queue）中的方法；如果您希望进行公平的比较，请尝试对ArrayDeque运行LinkedList，并进行功能比较。
推荐文章
- Java 8接口方法中不允许“同步”的原因是什么?
- 如何找到Java堆大小和内存使用(Linux)?
- 使用Enum实现单例(Java)
- RabbitMQ与通道和连接之间的关系
- buildSessionFactory()配置方法在Hibernate中已弃用?
- Spring MVC -如何获得所有的请求参数在一个地图在Spring控制器?
- 如何在Java中按两个字段排序?
- 文件之间的差异。路径中的分隔符和斜杠
- 在方法参数中使用NotNull注释
- Spring MVC中处理可选参数的@RequestParam
- Tomcat:如何查找正在运行的Tomcat版本?
- “java”、“javaw”和“javaws”之间有什么区别?
- 将Date对象转换为日历对象
- 在Java中保存最后N个元素的大小有限的队列
- 如何运行一个类从Jar不是主类在其清单文件
