Choosing: ArrayList vs LinkedList vs ArrayDeque

Written Explanation

Three classes, three shapes

The JDK documentation describes LinkedList as a doubly linked list that implements both List and Deque. ArrayDeque is a Deque backed by a resizable array. Both documentation pages describe ArrayList and ArrayDeque in terms of arrays, which is why their costs follow what you learned in Lessons 1 and 2.

The decision table

Reasons behind the cells:

• ArrayList.get(i) is the array arithmetic from Lesson 1; the ArrayList documentation says get runs in constant time and add in amortized constant time.
• ArrayList front operations shift every item, as in Lesson 1.
• LinkedList.get(i) has to walk. The documentation says index operations traverse from the beginning or the end, whichever is closer, which halves the walk at best but is still O(n).
• LinkedList middle insert is O(1) only once you are already at the node, for example through an iterator. Finding it costs O(n). If you must search first, you pay the search.
• ArrayDeque has no index methods at all, which is deliberate: it is designed for the ends. Trying d.get(0) on a Deque does not compile, and javac reports cannot find symbol ... method get(int).

Why LinkedList disappoints in practice

On paper the linked list wins at the front and in the middle. In practice it is rarely the best choice:

• Each item needs a node object plus references, so it uses more memory per item than an array.
• To use the "O(1) in the middle" advantage you need to already hold the position, which most programs do not.
• For stacks and queues, ArrayDeque covers the ends just as well. Its documentation says it is likely to be faster than LinkedList when used as a queue, and faster than Stack when used as a stack.
• Arrays keep items next to each other in memory, which processors usually handle well. How much this matters depends on the machine and the program, so treat it as a reason to measure, not as a guarantee.

The module's rule of thumb is: ArrayList for lists, ArrayDeque for stacks and queues, LinkedList only when you have a specific reason you can explain.

Decide by the operation you do most

Ask three questions in order:

1. Do I need to read by position? (get(i), set(i, x).) Yes: ArrayList.
2. Do I only add and remove at the ends, newest-first (stack) or oldest-first (queue)? Yes: ArrayDeque.
3. Do I need to remove or insert in the middle often, while already holding a position? Maybe LinkedList, but first check whether a different structure (a Set or Map from the Collections module) fits better.

If none of these decide it, use ArrayList. Its documentation describes the constant-time operations that cover most everyday code.

Measure before claiming

A claim like "X is faster than Y" is only worth something with a measurement for your data and your machine. Quick timings written by hand in a main method are easily wrong, because the JVM warms up and optimizes as it runs. For this course, rely on the Big O reasoning above to choose, and use a proper benchmarking tool such as JMH in later work if performance really matters. Never write "linked lists are faster for insertion" as a blanket statement: it is true for the relinking step only.

Code against the interface

Declare variables with the interface, and choose the class once:

List<String> names = new ArrayList<>();
Deque<Integer> undo = new ArrayDeque<>();
Queue<String> jobs = new ArrayDeque<>();

If a measurement later shows a different class would fit, you change one line. Writing ArrayList<String> names everywhere would spread the choice through the code.