我一直是一个简单使用的人：
List<String> names = new ArrayList<>();
我使用接口作为可移植性的类型名称，这样当我问类似这样的问题时，我就可以修改代码。
LinkedList何时应用于ArrayList，反之亦然？
当前回答
这取决于您将在列表中执行更多操作。
ArrayList访问索引值更快。插入或删除对象时，情况更糟。
要了解更多信息，请阅读任何关于数组和链接列表之间区别的文章。
其他回答
您可以根据对该特定列表执行的操作的时间复杂性，使用一个而不是另一个。
|---------------------|---------------------|--------------------|------------|
| 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 |
|--------------------------------------|
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是第一种类型，即在列表末尾添加元素，然后在列表中的指定位置删除元素）：
如果您的代码有add（0）和remove（0），请使用LinkedList，这是更漂亮的addFirst（）和removeFirst（）方法。否则，请使用ArrayList。
当然，Guava的ImmutableList是你最好的朋友。
正确或不正确：请在本地执行测试并自行决定！
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);
}
}
我知道这是一篇老帖子，但我真的不敢相信没有人提到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不是主类在其清单文件
