我一直是一个简单使用的人：
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)
其他回答
以下是ArrayList和LinkedList以及CopyOnWrite ArrayList中的Big-O符号：
阵列列表
get O(1)
add O(1)
contains O(n)
next O(1)
remove O(n)
iterator.remove O(n)
链表
get O(n)
add O(1)
contains O(n)
next O(1)
remove O(1)
iterator.remove O(1)
CopyOnWrite阵列列表
get O(1)
add O(n)
contains O(n)
next O(1)
remove O(n)
iterator.remove O(n)
基于这些，您必须决定选择什么。：）
除了上面的其他好参数之外，您应该注意到ArrayList实现了RandomAccess接口，而LinkedList实现了Queue。
因此，他们解决的问题略有不同，效率和行为有所不同（见他们的方法列表）。
数组列表本质上是一个具有添加项等方法的数组（您应该使用通用列表）。它是可以通过索引器（例如[0]）访问的项的集合。它意味着从一个项目到下一个项目的进展。
链接列表指定从一个项目到下一个项目（项目A->项目b）的进度。您可以使用数组列表获得相同的效果，但链接列表绝对会说明前一个列表后面应该包含哪些项。
正确或不正确：请在本地执行测试并自行决定！
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比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)
推荐文章
- 到底是什么导致了堆栈溢出错误?
- 为什么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
