什么时候在 Java 中使用 LinkedList 而不是 ArrayList?

我一直是一个简单使用的人:

List<String> names = new ArrayList<>();

我使用接口作为可移植性的类型名称,这样当我提出诸如此类的问题时,我就可以重新编写我的代码。

什么时候应该LinkedList 用于 ArrayList 反之亦然?

Thus far, nobody seems to have addressed the memory footprint of each of these lists besides the general consensus that a LinkedList is "lots more" than an ArrayList so I did some number crunching to demonstrate exactly how much both lists take up for N null references.

Since references are either 32 or 64 bits (even when null) on their relative systems, I have included 4 sets of data for 32 and 64 bit LinkedLists and ArrayLists.

Note: The sizes shown for the ArrayList lines are for trimmed lists - In practice, the capacity of the backing array in an ArrayList is generally larger than its current element count.

Note 2: (thanks BeeOnRope) As CompressedOops is default now from mid JDK6 and up, the values below for 64-bit machines will basically match their 32-bit counterparts, unless of course you specifically turn it off.



The result clearly shows that LinkedList is a whole lot more than ArrayList, especially with a very high element count. If memory is a factor, steer clear of LinkedLists.

The formulas I used follow, let me know if I have done anything wrong and I will fix it up. 'b' is either 4 or 8 for 32 or 64 bit systems, and 'n' is the number of elements. Note the reason for the mods is because all objects in java will take up a multiple of 8 bytes space regardless of whether it is all used or not.

ArrayList:

ArrayList object header + size integer + modCount integer + array reference + (array oject header + b * n) + MOD(array oject, 8) + MOD(ArrayList object, 8) == 8 + 4 + 4 + b + (12 + b * n) + MOD(12 + b * n, 8) + MOD(8 + 4 + 4 + b + (12 + b * n) + MOD(12 + b * n, 8), 8)

LinkedList:

LinkedList object header + size integer + modCount integer + reference to header + reference to footer + (node object overhead + reference to previous element + reference to next element + reference to element) * n) + MOD(node object, 8) * n + MOD(LinkedList object, 8) == 8 + 4 + 4 + 2 * b + (8 + 3 * b) * n + MOD(8 + 3 * b, 8) * n + MOD(8 + 4 + 4 + 2 * b + (8 + 3 * b) * n + MOD(8 + 3 * b, 8) * n, 8)

ArrayList is what you want. LinkedList is almost always a (performance) bug.

Why LinkedList sucks:

  • It uses lots of small memory objects, and therefore impacts performance across the process.
  • Lots of small objects are bad for cache-locality.
  • Any indexed operation requires a traversal, i.e. has O(n) performance. This is not obvious in the source code, leading to algorithms O(n) slower than if ArrayList was used.
  • Getting good performance is tricky.
  • Even when big-O performance is the same as ArrayList, it is probably going to be significantly slower anyway.
  • It's jarring to see LinkedList in source because it is probably the wrong choice.

As someone who has been doing operational performance engineering on very large scale SOA web services for about a decade, I would prefer the behavior of LinkedList over ArrayList. While the steady-state throughput of LinkedList is worse and therefore might lead to buying more hardware -- the behavior of ArrayList under pressure could lead to apps in a cluster expanding their arrays in near synchronicity and for large array sizes could lead to lack of responsiveness in the app and an outage, while under pressure, which is catastrophic behavior.

Similarly, you can get better throughput in an app from the default throughput tenured garbage collector, but once you get java apps with 10GB heaps you can wind up locking up the app for 25 seconds during a Full GCs which causes timeouts and failures in SOA apps and blows your SLAs if it occurs too often. Even though the CMS collector takes more resources and does not achieve the same raw throughput, it is a much better choice because it has more predictable and smaller latency.

ArrayList is only a better choice for performance if all you mean by performance is throughput and you can ignore latency. In my experience at my job I cannot ignore worst-case latency.

Update (Aug 27, 2021 -- 10 years later): This answer (my most historically upvoted answer on SO as well) is very likely wrong (for reasons outlined in the comments below). I'd like to add that ArrayList will optimize for sequential reading of memory and minimize cache-line and TLB misses, etc. The copying overhead when the array grows past the bounds is likely inconsequential by comparison (and can be done by efficient CPU operations). This answer is also probably getting worse over time given hardware trends. The only situations where a LinkedList might make sense would be something highly contrived where you had thousands of Lists any one of which might grow to be GB-sized, but where no good guess could be made at allocation-time of the List and setting them all to GB-sized would blow up the heap. And if you found some problem like that, then it really does call for reengineering whatever your solution is (and I don't like to lightly suggest reengineering old code because I myself maintain piles and piles of old code, but that'd be a very good case of where the original design has simply run out of runway and does need to be chucked). I'll still leave my decades-old poor opinion up there for you to read though. Simple, logical and pretty wrong.

If your code has add(0) and remove(0), use a LinkedList and it's prettier addFirst() and removeFirst() methods. Otherwise, use ArrayList.

And of course, Guava's ImmutableList is your best friend.

I know this is an old post, but I honestly can't believe nobody mentioned that LinkedList implements Deque. Just look at the methods in Deque (and Queue); if you want a fair comparison, try running LinkedList against ArrayDeque and do a feature-for-feature comparison.

Let's compare LinkedList and ArrayList w.r.t. below parameters:

1. Implementation

ArrayList is the resizable array implementation of list interface , while

LinkedList is the Doubly-linked list implementation of the list interface.


2. Performance

  • get(int index) or search operation

    ArrayList get(int index) operation runs in constant time i.e O(1) while

    LinkedList get(int index) operation run time is O(n) .

    The reason behind ArrayList being faster than LinkedList is that ArrayList uses an index based system for its elements as it internally uses an array data structure, on the other hand,

    LinkedList does not provide index-based access for its elements as it iterates either from the beginning or end (whichever is closer) to retrieve the node at the specified element index.

  • insert() or add(Object) operation

    Insertions in LinkedList are generally fast as compare to ArrayList. In LinkedList adding or insertion is O(1) operation .

    While in ArrayList, if the array is the full i.e worst case, there is an extra cost of resizing array and copying elements to the new array, which makes runtime of add operation in ArrayList O(n), otherwise it is O(1).

  • remove(int) operation

    Remove operation in LinkedList is generally the same as ArrayList i.e. O(n).

    In LinkedList, there are two overloaded remove methods. one is remove() without any parameter which removes the head of the list and runs in constant time O(1). The other overloaded remove method in LinkedList is remove(int) or remove(Object) which removes the Object or int passed as a parameter. This method traverses the LinkedList until it found the Object and unlink it from the original list. Hence this method runtime is O(n).

    While in ArrayList remove(int) method involves copying elements from the old array to new updated array, hence its runtime is O(n).


3. Reverse Iterator

LinkedList can be iterated in reverse direction using descendingIterator() while

there is no descendingIterator() in ArrayList , so we need to write our own code to iterate over the ArrayList in reverse direction.


4. Initial Capacity

If the constructor is not overloaded, then ArrayList creates an empty list of initial capacity 10, while

LinkedList only constructs the empty list without any initial capacity.


5. Memory Overhead

Memory overhead in LinkedList is more as compared to ArrayList as a node in LinkedList needs to maintain the addresses of the next and previous node. While

In ArrayList each index only holds the actual object(data).


Source

In addition to the other good arguments above, you should notice ArrayList implements RandomAccess interface, while LinkedList implements Queue.

So, somehow they address slightly different problems, with difference of efficiency and behavior (see their list of methods).

It depends upon what operations you will be doing more on the List.

ArrayList is faster to access an indexed value. It is much worse when inserting or deleting objects.

To find out more, read any article that talks about the difference between arrays and linked lists.