我一直是一个简单使用的人:
List<String> names = new ArrayList<>();
我使用接口作为可移植性的类型名称,这样当我问类似这样的问题时,我就可以修改代码。
LinkedList何时应用于ArrayList,反之亦然?
我一直是一个简单使用的人:
List<String> names = new ArrayList<>();
我使用接口作为可移植性的类型名称,这样当我问类似这样的问题时,我就可以修改代码。
LinkedList何时应用于ArrayList,反之亦然?
当前回答
以下是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)
基于这些,您必须决定选择什么。:)
其他回答
我在这里看到的一个测试只进行一次测试。但我注意到的是,您需要多次运行这些测试,最终它们的时间会收敛。基本上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扩展了AbstractList并实现了List接口。ArrayList是动态数组。可以说,它的创建基本上是为了克服数组的缺点LinkedList类扩展了AbstractSequentialList并实现了List、Deque和Queue接口。表演arraylist.get()是O(1),而linkedlist.getarraylist.add()为O(1),linkedlist.add)为0(1)arraylist.contains()为O(n),linkedlist.contans()为0(n)arraylist.next()为O(1),linkedlist.next()为0(1)arraylist.remove()是O(n),而linkedlist.remove()是0(1)在arraylistiterator.remove()是O(n),而在linkedlist迭代器.remove
ArrayList中的get(i)操作比LinkedList更快,因为:ArrayList:List接口的可调整大小的数组实现LinkedList:list和Deque接口的双重链接列表实现
索引到列表中的操作将从开始或结束遍历列表,以更接近指定索引的为准。
您可以根据对该特定列表执行的操作的时间复杂性,使用一个而不是另一个。
|---------------------|---------------------|--------------------|------------|
| 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几乎总是一个(性能)bug。
为什么LinkedList很糟糕:
它使用了大量小内存对象,因此影响了整个过程的性能。许多小对象不利于缓存位置。任何索引操作都需要遍历,即具有O(n)性能。这在源代码中并不明显,导致算法O(n)比使用ArrayList时慢。获得好的表现是很棘手的。即使big-O性能与ArrayList相同,它也可能会明显变慢。在源代码中看到LinkedList很刺耳,因为它可能是错误的选择。