我一直是一个简单使用的人：
List<String> names = new ArrayList<>();
我使用接口作为可移植性的类型名称，这样当我问类似这样的问题时，我就可以修改代码。
LinkedList何时应用于ArrayList，反之亦然？
当前回答
是的，我知道，这是一个古老的问题，但我会投入我的两分钱：
LinkedList在性能方面几乎总是错误的选择。有一些非常具体的算法需要LinkedList，但这些算法非常非常罕见，并且该算法通常具体取决于LinkedLists在使用ListIterator导航到列表中间后相对快速地插入和删除元素的能力。
有一个常见的用例LinkedList优于ArrayList：队列。但是，如果您的目标是性能，那么您也应该考虑使用ArrayBlockingQueue（如果您可以提前确定队列大小的上限，并且能够提前分配所有内存），而不是LinkedList，或者使用CircularArray实现。（是的，它来自2001年，因此您需要对其进行一般化，但我得到的性能比与最近一篇JVM文章中引用的性能比相当）
其他回答
Joshua Bloch，LinkedList的作者：
有人真的使用LinkedList吗？我写的，我从来没有用过。
链接：https://twitter.com/joshbloch/status/583813919019573248
很抱歉，我的答案没有其他答案那样信息丰富，但我认为这是最不言自明的答案。
除了上面的其他好参数之外，您应该注意到ArrayList实现了RandomAccess接口，而LinkedList实现了Queue。
因此，他们解决的问题略有不同，效率和行为有所不同（见他们的方法列表）。
1） 基础数据结构
ArrayList和LinkedList之间的第一个区别在于，ArrayList由Array支持，而LinkedList由LinkedList支持。这将导致性能的进一步差异。
2） LinkedList实现Deque
ArrayList和LinkedList之间的另一个区别是，除了List接口之外，LinkedList还实现了Deque接口，该接口为add（）和poll（）以及其他几个Deque函数提供先进先出操作。3） 在ArrayList中添加元素如果不触发Array的重新调整大小，则在ArrayList中添加元素是O（1）操作，在这种情况下，它变为O（log（n））。另一方面，在LinkedList中添加一个元素则是O（2）操作，因为它不需要任何导航。
4） 从位置移除元素
为了从特定索引中删除元素，例如通过调用remove（index），ArrayList执行复制操作，使其接近O（n），而LinkedList需要遍历到该点，这也使其成为O（n/2），因为它可以根据接近度从任意方向遍历。
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，这是一个静态嵌套类，用于存储数据和下一个和上一个节点，而ArrayList只在Array中存储数据。
因此，除了Array在将内容从一个Array复制到另一个Array时执行重新调整大小操作的情况外，ArrayList的内存需求似乎比LinkedList少。
如果Array足够大，那么此时可能会占用大量内存并触发垃圾收集，这会降低响应时间。
从ArrayList与LinkedList之间的所有差异来看，ArrayList在几乎所有情况下都是比LinkedList更好的选择，除非您经常执行add（）操作而不是remove（）或get（）操作。
修改链接列表比修改ArrayList更容易，尤其是当您从开始或结束处添加或删除元素时，因为链接列表内部保留了这些位置的引用，并且可以在O（1）时间内访问。
换句话说，您不需要遍历链接列表就可以到达要添加元素的位置，在这种情况下，添加就变成了O（n）操作。例如，在链接列表中间插入或删除元素。
在我看来，在Java中，使用ArrayList而不是LinkedList来实现大多数实际用途。
首先使用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);
}
}
推荐文章
- 到底是什么导致了堆栈溢出错误?
- 为什么Android工作室说“等待调试器”如果我不调试?
- Java:路径vs文件
- ExecutorService，如何等待所有任务完成
- Maven依赖Servlet 3.0 API?
- 如何在IntelliJ IDEA中添加目录到应用程序运行概要文件中的类路径?
- getter和setter是糟糕的设计吗?相互矛盾的建议
- Android room persistent: AppDatabase_Impl不存在
- Java的String[]在Kotlin中等价于什么?
- Intellij IDEA上的System.out.println()快捷方式
- 使用Spring RestTemplate获取JSON对象列表
- Spring JPA选择特定的列
- URLEncoder不能翻译空格字符
- Java中的super()
- 如何转换JSON字符串映射<字符串，字符串>与杰克逊JSON
