我一直是一个简单使用的人：
List<String> names = new ArrayList<>();
我使用接口作为可移植性的类型名称，这样当我问类似这样的问题时，我就可以修改代码。
LinkedList何时应用于ArrayList，反之亦然？
当前回答
与LinkedList相比，Summary ArrayList和ArrayDeque在更多的用例中更可取。如果您不确定，请从ArrayList开始。
TLDR，在ArrayList中，访问元素需要恒定的时间[O（1）]，添加元素需要O（n）时间[最坏情况]。在LinkedList中，插入元素需要O（n）时间，访问也需要O（n）时间，但LinkedList比ArrayList使用更多内存。
LinkedList和ArrayList是List接口的两种不同实现。LinkedList使用双链接列表实现它。ArrayList通过动态调整数组大小来实现它。
与标准的链表和数组操作一样，不同的方法将有不同的算法运行时。
对于LinkedList＜E＞
get（int index）为O（n）（平均步数为n/4），但当index=0或index=list.size（）-1时为O（1）（在这种情况下，还可以使用getFirst（）和getLast（））。LinkedList的主要优点之一add（int index，E元素）为O（n）（平均步数为n/4），但当index=0或index=list.size（）-1时为O（1）（在这种情况下，还可以使用addFirst（）和addLast（）/add（））。LinkedList的主要优点之一remove（int index）为O（n）（平均步数为n/4），但当index=0或index=list.size（）-1时为O（1）（在这种情况下，还可以使用removeFirst（）和removeLast（））。LinkedList的主要优点之一Iterator.remove（）为O（1）。LinkedList的主要优点之一ListIterator.add（E元素）为O（1）。LinkedList的主要优点之一
注：许多操作平均需要n/4步，在最佳情况下（例如索引=0）需要恒定的步数，在最坏情况下（列表中间）需要n/2步
对于ArrayList＜E＞
get（int索引）为O（1）。ArrayList的主要优势<E>add（E元素）是O（1）摊销，但O（n）最坏情况，因为数组必须调整大小并复制add（int索引，E元素）为O（n）（平均n/2步）remove（int索引）为O（n）（平均n/2步）Iterator.remove（）为O（n）（平均为n/2步）ListIterator.add（E元素）为O（n）（平均n/2步）
注：许多操作平均需要n/2步，在最佳情况下（列表末尾）需要恒定的步数，在最坏情况下（开始列表）需要n步
LinkedList＜E＞允许使用迭代器进行恒定时间的插入或删除，但只能对元素进行顺序访问。换句话说，您可以向前或向后遍历列表，但在列表中找到位置所需的时间与列表的大小成正比。Javadoc表示“索引到列表中的操作将从开始或结束遍历列表，以较近者为准”，因此这些方法平均为O（n）（n/4步），尽管索引=0时为O（1）。
另一方面，ArrayList＜E＞允许快速随机读取访问，因此您可以在恒定时间内获取任何元素。但是，除了末端之外，任何地方的添加或删除都需要将后面的所有元素转换过来，要么打开，要么填补空白。此外，如果添加的元素超过了基础数组的容量，则会分配一个新数组（大小的1.5倍），并将旧数组复制到新数组，因此在最坏的情况下，添加到ArrayList是O（n），但平均来说是常量。
因此，根据您打算执行的操作，您应该相应地选择实现。对这两种列表进行迭代实际上都是同样便宜的。（在ArrayList上迭代在技术上更快，但除非您正在做一些对性能非常敏感的事情，否则不必担心这一点——它们都是常量。）
使用LinkedList的主要好处是重用现有迭代器来插入和删除元素。然后，这些操作可以在O（1）中通过仅本地更改列表来完成。在阵列列表中，需要移动（即复制）阵列的其余部分。另一方面，在LinkedList中查找意味着在最坏情况下遵循O（n）（n/2步）中的链接，而在ArrayList中，所需位置可以通过数学计算并在O（1）中访问。
使用LinkedList的另一个好处是在列表的开头添加或删除，因为这些操作是O（1），而ArrayList是O（n）。请注意，ArrayDeque可能是LinkedList的一个很好的替代方案，用于添加和删除头部，但它不是List。
此外，如果您有大量列表，请记住内存使用情况也不同。LinkedList的每个元素都有更多的开销，因为指向下一个和上一个元素的指针也会被存储。ArrayList没有这个开销。然而，ArrayList占用的内存与为容量分配的内存一样多，而不管是否实际添加了元素。
ArrayList的默认初始容量非常小（Java 1.4-1.8中为10）。但由于底层实现是一个数组，如果添加大量元素，则必须调整数组的大小。为了避免在知道要添加大量元素时调整大小的高昂成本，请使用更高的初始容量构建ArrayList。
如果使用数据结构透视图来理解这两个结构，LinkedList基本上是一个包含头节点的顺序数据结构。Node是两个组件的包装器：一个类型为T的值[通过泛型接受]，另一个对链接到它的Node的引用。因此，我们可以断言它是一个递归数据结构（一个Node包含另一个节点，该节点具有另一个Node等等…）。如上所述，在LinkedList中添加元素需要线性时间。
ArrayList是一个可增长的数组。它就像一个常规数组。在后台，当添加了一个元素，并且ArrayList已经满了容量时，它将创建另一个大小大于先前大小的数组。然后将元素从先前的数组复制到新的数组，并且将要添加的元素也放置在指定的索引处。
其他回答
是的，我知道，这是一个古老的问题，但我会投入我的两分钱：
LinkedList在性能方面几乎总是错误的选择。有一些非常具体的算法需要LinkedList，但这些算法非常非常罕见，并且该算法通常具体取决于LinkedLists在使用ListIterator导航到列表中间后相对快速地插入和删除元素的能力。
有一个常见的用例LinkedList优于ArrayList：队列。但是，如果您的目标是性能，那么您也应该考虑使用ArrayBlockingQueue（如果您可以提前确定队列大小的上限，并且能够提前分配所有内存），而不是LinkedList，或者使用CircularArray实现。（是的，它来自2001年，因此您需要对其进行一般化，但我得到的性能比与最近一篇JVM文章中引用的性能比相当）
我的经验法则是，如果我需要一个集合（即不需要是一个列表），那么如果你事先知道大小，或者可以自信地知道大小，或知道它不会有太大变化，那么就使用ArrayList。如果您需要随机访问（即使用get（index）），请避免LinkedList。基本上，只有当您不需要索引访问并且不知道正在分配的集合的（近似）大小时，才使用LinkedList。此外，如果您要进行大量添加和删除（再次通过Collection接口），则LinkedList可能更可取。
ArrayList中的get（i）操作比LinkedList更快，因为：ArrayList：List接口的可调整大小的数组实现LinkedList：list和Deque接口的双重链接列表实现
索引到列表中的操作将从开始或结束遍历列表，以更接近指定索引的为准。
首先使用Vector而不是ArrayList，因为您可以覆盖insuranceCapasity方法，在ArrayList中是私有的，并添加1.5大小的当前数组https://docs.oracle.com/javase/8/docs/api/java/util/Vector.html#ensureCapacity-整数-
在很多情况下，linkedList会更好，las有一个很大的优势：你可以高频插入数据，所以列表的大小变化很快，你不能为数字元素分配大小。从理论上讲，你可能会遇到“内存不足”之类的错误，但在现代计算机中，你有16G和交换磁盘，所以如果你列出的是billoins元素，与15-20年前相比，你可能失败。
正确或不正确：请在本地执行测试并自行决定！
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);
}
}
推荐文章
- Eclipse调试器总是阻塞在ThreadPoolExecutor上，没有任何明显的异常，为什么?
- Java生成两个给定值之间的随机数
- 如何有效地从数组列表或字符串数组中删除所有空元素?
- 比较JUnit断言中的数组，简洁的内置方式?
- codestyle;把javadoc放在注释之前还是之后?
- 如何在Spring中定义List bean ?
- 将Set<T>转换为List<T>的最简洁的方法
- 在JavaScript中，什么相当于Java的Thread.sleep() ?
- 使用Java重命名文件
- URL从Java中的类路径加载资源
- .toArray（new MyClass[0]） or .toArray（new MyClass[myList.size（）]）？
- Hibernate中不同的保存方法之间有什么区别?
- Java 8流和数组操作
- Java Regex捕获组
- 从另一个列表id中排序一个列表
