0

I know that it's a never-ending question that comes back every now and then, but I'm really confused about these two. This is what I understand about them.

In theory:

  • LinkedList is faster at adding elements at both ends (since there is no need for occasional resizing and copying of the list, which guarantees O(1) time without any special cases,
  • Adding ONE ITEM to the middle of the list is O(n) in both cases, but still faster in ArrayList, since iterating over it is much faster
  • Adding many items to the middle is O(1) in LinkedList if we already have a reference to the middle Node

In practice:

  • LinkedList is slower at adding/removing from the end than ArrayList (I guess due to ArrayList using much less memory)

Which leaves me with one thought: LinkedList, in reality, is only better at adding/removing items from front and adding in the middle if we have a reference to the middle node. However, we can solve the problem of adding/removing in the beginning if we use ArrayDeque instead of it (as long as we don't care about random access). Then, LinkedList will be left with only one advantage - adding in the middle while having a reference there. If there is any other scenario, I should basically never use LinkedList. Is my thinking correct?

Improve this question
11
  • A main problem with linked-lists is the issue of memory locality (causing cache misses and therefore slow access). Commented Apr 27 at 15:08
  • @sebkaminski16 See my answer at cache locality - LinkedList is effectively never the right answer. It's not true that ArrayList is always a better answer. It often is, and in more cases than one might think, but not always. However, there are more lists than just LL and AL. There's ArrayDeque for example. The situations where LL is the best possible data type of all the ones available in java.* are more or less nonexistent. Commented Apr 27 at 22:04
  • 1
    @rzwitserloot I'd also like to add that your answer about cache locality was superb! I haven't read such an easy-to-understand explanation in a long time! Thank you a lot. Commented Apr 28 at 3:36
  • 2
    Even adding in the middle of a LinkedList via ListIterator is more expensive than you might have considered (even when we ignore cache locality). It requires allocating a node object and initializing its header, prev/next/element references, adjusting the next reference of the previous node and the prev reference of the next node, plus updating the iterator’s state, adding up to a dozen write operations. You’d have to insert a significant number of elements at that location to benefit from the time complexity but when you have to insert a lot of elements, ArrayList’s addAll may still win… Commented Apr 29 at 14:18
  • 1
    Correct, when adding to the end, the number of elements doesn’t matter. Since the capacity is doubled each time an increment is needed, the total number of per-element write operations is about log₂ n, actually far less because we do not start with a capacity of one and only the few elements added at the beginning are copied each time while the majority of the elements are copied far less, the last added are usually written only once, half of them only experienced at most one copy operation. So, when adding to the end, the total number of writes is always smaller than for LinkedList. Commented May 5 at 8:08

1 Answer 1

Reset to default
-1

In general you are right.
LinkedList is only in theory faster. Especially in Java, LinkedList has a memory overhead because of the 2 pointers (it is actually a double linkedlist). So the memory usage is worse and in practice degrades the performance.
ArrayList is almost always (there are only very few edge cases) faster and more efficient than LinkedList and also ArrayDeque. And you are right, for these Edge Cases, ArrayDeque is the better choice.
As a Bonus Point: ArrayList is backed by a single continguous array in memory. The CPUs are much faster in accessing sequential memory. The hotspot optimizations (the JIT compiler) are working better with the array like memory layouts.

Improve this answer
Sign up to request clarification or add additional context in comments.

7 Comments

I am not the downvoter but please note that ArrayList do not actually store the items contiguously, only the pointer to them. The items might be spread in memory. They are still often faster because CPUs can fetch multiple pointers concurrently reducing memory latency stalls meanwhile they cannot do that with LinkedList due to pointer chasing. This is not really a problem when data fits in the L1 cache but really bad when data do not fit in CPU caches. Both are much slower than a truly-contiguous array of native items (e.g. int[]).
Yes of course does the ArrayList only store the pointers to the objects. I never said that the actual data is stored that way.
Then "ArrayList is backed by a single continguous array in memory" is miss-leading IMHO and while "The CPUs are much faster in accessing sequential memory" is true in general, it is not what makes the ArrayList faster so it is not very relevent here. For example, it would still be fast with strided accesses (or even the structure mentioned by JayC667). What makes it mainly faster is actually the ILP (not present in LinkedLists). Reference packing might help so to make things more cache friendly but this should not be significant compared to object-related memory diffusion issues.
@JérômeRichard it would be interesting to see why ILP is present in ArrayList but not in LinkedList.
@k314159 This is due to pointer chasing: the CPU need to fetch a node so to know the next pointer and be able to fetch the next one. This is an inherently sequential process. Thus, you pay the cumulated cost of the latency of all fetches. This is not the case with ArrayList because the CPU can read multiple pointers of the array and fetch them concurrently. Modern mainstream CPUs can fetch at least a dozen of items concurrently (per core) so the latency per item fetched can be much lower (possibly an order of magnitude faster).
|

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.