我一直是一个简单使用的人：
List<String> names = new ArrayList<>();
我使用接口作为可移植性的类型名称，这样当我问类似这样的问题时，我就可以修改代码。
LinkedList何时应用于ArrayList，反之亦然？
当前回答
我在这里看到的一个测试只进行一次测试。但我注意到的是，您需要多次运行这些测试，最终它们的时间会收敛。基本上JVM需要预热。对于我的特定用例，我需要向列表中添加/删除项目，该列表将增加到大约500个项目。在我的测试中，LinkedList的发布速度更快，LinkedList约为50000 NS，ArrayList约为90000NS。。。给予或索取。请参见下面的代码。
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;
}
其他回答
对于ArrayList和LinkedList，remove（）和insert（）的运行时效率都为O（n）。然而，线性处理时间背后的原因来自两个非常不同的原因：
在ArrayList中，您可以找到O（1）中的元素，但实际上删除或插入某些元素会使其成为O（n），因为以下所有元素都需要更改。
在LinkedList中，实际到达所需元素需要O（n），因为我们必须从一开始就开始，直到达到所需的索引。实际上，移除或插入是常量，因为我们只需要为remove（）更改1个引用，为insert（）更改2个引用。
插入和删除这两项中的哪一项更快取决于发生的位置。如果我们更接近开始，LinkedList将更快，因为我们必须经过相对较少的元素。如果我们接近末尾，ArrayList将更快，因为我们在恒定的时间内到达那里，只需更改紧随其后的几个剩余元素。如果正好在中间完成，LinkedList将更快速，因为遍历n个元素比移动n个值更快。
好处：虽然无法为ArrayList创建这两个方法O（1），但实际上在LinkedList中有一种方法可以做到这一点。假设我们想在整个列表中删除和插入元素。通常，您可以使用LinkedList从头开始每个元素，我们也可以使用迭代器“保存”当前正在处理的元素。在迭代器的帮助下，当在LinkedList中工作时，remove（）和insert（）的效率为O（1）。使其成为我所知的唯一性能优势，LinkedList总是优于ArrayList。
ArrayList是可随机访问的，而LinkedList扩展和删除元素非常便宜。在大多数情况下，ArrayList都可以。
除非您创建了大量列表并测量了瓶颈，否则您可能永远不需要担心差异。
正确或不正确：请在本地执行测试并自行决定！
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);
}
}
如果您的代码有add（0）和remove（0），请使用LinkedList，这是更漂亮的addFirst（）和removeFirst（）方法。否则，请使用ArrayList。
当然，Guava的ImmutableList是你最好的朋友。
TL；DR由于现代计算机体系结构，ArrayList对于几乎所有可能的用例都将显著提高效率，因此除了一些非常独特和极端的情况外，应避免使用LinkedList。
理论上，LinkedList的add（E元素）有一个O（1）
此外，在列表中间添加元素应该非常有效。
实践非常不同，因为LinkedList是一个缓存敌对数据结构。从性能POV来看，LinkedList很少比缓存友好的ArrayList性能更好。
以下是在随机位置插入元素的基准测试结果。如您所见，数组列表效率更高，但理论上，每次在列表中间插入都需要“移动”数组后面的n个元素（值越低越好）：
使用新一代硬件（更大、更高效的缓存），结果更为确凿：
LinkedList需要更多的时间来完成相同的任务。源源代码
这主要有两个原因：
主要是LinkedList的节点在内存中随机分布。RAM（“随机存取存储器”）不是真正随机的，需要将内存块提取到缓存中。此操作需要时间，并且当此类提取频繁发生时，缓存中的内存页需要一直被替换->缓存未命中->缓存效率不高。ArrayList元素存储在连续内存中——这正是现代CPU架构正在优化的目标。Secondary LinkedList需要保留/转发指针，这意味着与ArrayList相比，每个存储值的内存消耗是3倍。
顺便说一句，DynamicIntArray是一个自定义ArrayList实现，它保存Int（原始类型）而不是Object，因此所有数据都是相邻存储的，因此效率更高。
需要记住的一个关键因素是，获取存储块的成本比访问单个存储单元的成本更重要。这就是为什么读卡器1MB的顺序存储器比从不同内存块读取此数据量快x400倍的原因：
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创建的。在他的博客上可以找到更多的数据
推荐文章
- getResourceAsStream返回null
- 如何使用Java中的Scanner类从控制台读取输入?
- 如何添加JTable在JPanel与空布局?
- Statement和PreparedStatement的区别
- 为什么不能在Java中扩展注释?
- 在Java中使用UUID的最重要位的碰撞可能性
- 转换列表的最佳方法:map还是foreach?
- 如何分割逗号分隔的字符串?
- Java字符串—查看字符串是否只包含数字而不包含字母
- Mockito.any()传递带有泛型的接口
- 在IntelliJ 10.5中运行测试时，出现“NoSuchMethodError: org.hamcrest. matcher . descripbemismatch”
- 使用String.split()和多个分隔符
- Java数组有最大大小吗?
- 在Android中将字符串转换为Uri
- 从JSON生成Java类?
