我一直是一个简单使用的人:
List<String> names = new ArrayList<>();
我使用接口作为可移植性的类型名称,这样当我问类似这样的问题时,我就可以修改代码。
LinkedList何时应用于ArrayList,反之亦然?
我一直是一个简单使用的人:
List<String> names = new ArrayList<>();
我使用接口作为可移植性的类型名称,这样当我问类似这样的问题时,我就可以修改代码。
LinkedList何时应用于ArrayList,反之亦然?
当前回答
除了上面的其他好参数之外,您应该注意到ArrayList实现了RandomAccess接口,而LinkedList实现了Queue。
因此,他们解决的问题略有不同,效率和行为有所不同(见他们的方法列表)。
其他回答
是的,我知道,这是一个古老的问题,但我会投入我的两分钱:
LinkedList在性能方面几乎总是错误的选择。有一些非常具体的算法需要LinkedList,但这些算法非常非常罕见,并且该算法通常具体取决于LinkedLists在使用ListIterator导航到列表中间后相对快速地插入和删除元素的能力。
有一个常见的用例LinkedList优于ArrayList:队列。但是,如果您的目标是性能,那么您也应该考虑使用ArrayBlockingQueue(如果您可以提前确定队列大小的上限,并且能够提前分配所有内存),而不是LinkedList,或者使用CircularArray实现。(是的,它来自2001年,因此您需要对其进行一般化,但我得到的性能比与最近一篇JVM文章中引用的性能比相当)
以下是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)
基于这些,您必须决定选择什么。:)
我知道这是一篇老帖子,但我真的不敢相信没有人提到LinkedList实现了Deque。只需查看Deque(和Queue)中的方法;如果您希望进行公平的比较,请尝试对ArrayDeque运行LinkedList,并进行功能比较。
正确或不正确:请在本地执行测试并自行决定!
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);
}
}
首先使用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年前相比,你可能失败。