LinkedList is the JDK's second implementation of List and probably the most misunderstood class in the whole Framework. The sentence repeated in tutorials, in job interviews and in code comments is always the same: "use ArrayList to access by index and LinkedList to insert and delete, which is O(1)". That sentence, exactly as it sounds, is false, and believing it leads to writing considerably slower code while thinking you are optimising.

In this lesson you are going to understand exactly what a doubly linked list is, which operations are really O(1) and under what precise condition, and why in practice —even in the cases that look like its home ground— ArrayList usually wins. You will also see where LinkedList does make sense: not so much as a List, but as a Deque, that is, as a double-ended queue. And you will finish with the one BiblioTech case where its semantics really fit: the queue of pending reservations, consumed at one end and grown at the other.

This lesson is not just about a class. It is about learning to reason honestly about data structures, telling apart what the theory says from what the processor does.

1. The structure: doubly linked nodes
2. What it implies for memory and for the cache
3. The nuance almost everybody explains badly
4. ArrayList versus LinkedList, operation by operation
5. The honest, up-to-date conclusion
6. LinkedList as a Deque
7. ListIterator: two-way traversal and insertion
8. Measuring performance honestly
9. When LinkedList is the right choice: the reservation queue
10. Common Mistakes and Tips
11. Exercises

An ArrayList keeps its elements in a contiguous block of memory. A LinkedList keeps nothing contiguous: it keeps a chain of nodes, each in its own corner of the heap, joined by references.

This is the JDK's actual node, and it fits in five lines:

And the list itself keeps only three fields:

The solid arrows are the next links; the dotted ones, the prev links. Having links in both directions is what makes it doubly linked, and it has two important consequences: it can be traversed backwards, and from a node you can remove that node without knowing the previous one.

Its two fundamental characteristics follow immediately from this structure:

There are no indices. The nodes are not numbered nor placed at computable positions. To reach element 500 you have to start at first and jump 500 times. There is no way of doing it faster, and there lies the structural weakness of LinkedList.

There is no capacity. Each node is created when it is needed and discarded when it is removed. There are no resizes, no copies, no internal array to fill. Adding the millionth element costs exactly the same as adding the second.

Seeing how a node is inserted in the middle explains the rest:

The operation consists of creating node X and changing four references: A.next = X, X.prev = A, X.next = B, B.prev = X. Four assignments. No element moves, neither the first nor the millionth. That is what "O(1) insertion" means. And now comes the nuance.

Before the nuance, two costs that complexity tables do not show and that in practice weigh more than the O() itself.

In an ArrayList, each element takes up one reference in the internal array: 4 bytes with compressed pointers, 8 without.

In a LinkedList, each element needs a complete Node object:

Against the ~4 bytes per element of a well-sized ArrayList, that is about seven times more memory in infrastructure alone, without counting the objects pointed at. For a million elements: about 4 MB versus about 28 MB. And every node is an object the garbage collector has to trace (module 10-07).

This is the decisive factor and the one most people ignore. As 05-01 explained, the processor does not read memory byte by byte: it brings in 64-byte blocks to its cache. In an ArrayList, reading element 0 also brings in the next 15 for free; walking the list is practically a sequential read, the pattern the hardware likes best.

In a LinkedList, each node can be anywhere on the heap. If you created them in order they may be close together, but after a while of additions and removals, and after several collector passes, they end up scattered. Traversing then means one unpredictable memory jump per element, and every jump that misses the cache costs on the order of a hundred times more than a cached access.

The result, measured again and again: walking a LinkedList is usually between 2 and 10 times slower than walking an ArrayList of the same size, even though both operations are O(n). O() notation ignores constants, and here the constant matters enormously.

Let us repeat the popular claim: "inserting and deleting in a LinkedList is O(1)".

The correct statement is: inserting and deleting is O(1) IF YOU ALREADY HAVE THE POSITION, that is, if you already hold a reference to the node (or you are at one end). Getting to that position costs O(n).

Look at it in the JDK's real code:

linkBefore is O(1): four assignments. But node(index) walks up to half the list. The complete method is O(n). The optimisation of starting from the nearest end only halves it: it is still O(n).

Direct consequence: this loop, which looks reasonable, is a disaster.

A thousand calls × 50,000 jumps = 50 million pointer jumps. The same loop with an ArrayList would do a thousand System.arraycopy calls of 50,000 references, which is the same O() but executed by a block-copy instruction optimised by the hardware: in practice, several times faster.

Only in three situations:

1. At the ends. addFirst, addLast, removeFirst, removeLast reach first and last directly. Genuinely O(1), with no traversal.

2. With an iterator already at the position.

The full traversal is O(n), but each individual insertion is O(1), and no elements are shifted. Here LinkedList really is theoretically superior to ArrayList, where every add(i, e) would shift the rest.

3. Iterator.remove() during a traversal. Same reasoning: the iterator already has the node.

The rule in summary, worth memorising:

In a LinkedList the operation is cheap; getting to the spot is expensive. In an ArrayList getting to the spot is free; the operation is expensive.

And since "getting to the spot" is what any indexed method does, the net result almost always favours ArrayList.

Pay special attention to the indexed for row, because it is a performance mistake that slips in easily:

If your method's parameter is a List and you do not know which implementation will arrive, always traverse with for-each. That is one of the reasons the RandomAccess marker interface exists (05-03): it lets a generic algorithm ask whether indexed access is cheap.

You will hardly ever write this in your own code —use for-each and be done with it— but it is useful to know why it exists.

This is the part of the lesson that departs most from the usual discourse, so it comes with names and arguments.

In practice, ArrayList wins almost always. Even in scenarios that appear to favour LinkedList, repeated measurements on modern JVMs give victory to the array, because:

1. Cache locality dominates. The difference between an L1 cache access and a miss that goes to main memory is two orders of magnitude. No algorithmic advantage survives that when the O() is the same.
2. System.arraycopy is a native instruction that copies blocks of memory at hardware speed. Shifting 10,000 contiguous references is surprisingly cheap; following 10,000 scattered pointers is not.
3. Nodes put pressure on the collector. A million elements are a million Node objects to trace, versus a single array.
4. Insertions "in the middle" are almost never really in the middle. In real code you insert at the end, or remove by criterion with removeIf, or sort. All of those operations favour ArrayList.

This is also the public opinion of Joshua Bloch, author of Effective Java and co-author of the Collections Framework itself, who has gone as far as to say that these days LinkedList does not add enough value to justify its general use.

So is LinkedList useless? It is useful, but not as a List: as a Deque. When what you want is a queue or a stack —add at one end, take from the other— LinkedList delivers real O(1) with no capacity to manage.

And even so, on that ground it has a better competitor: ArrayDeque, which you will see in 05-07, and which is faster and uses less memory because it uses a circular array. The JDK's official recommendation for queues and stacks is ArrayDeque, not LinkedList.

The practical summary, without beating about the bush:

There are three solid reasons for you to keep learning LinkedList: you will meet it in existing code, it is the canonical example of a linked list —a structure that turns up in a thousand places— and understanding why it is not the answer teaches you to reason about performance better than any memorised rule.

LinkedList implements two interfaces at once, and there lies its distinctive trait:

It is the only class in the JDK that is a List and a Deque simultaneously. That gives it access to the whole family of end operations, all genuinely O(1):

The distinction between the two families —throw an exception or return null— is an important design decision of Queue and Deque, and it is explained thoroughly in 05-07. For now, take away the rule: use peek/poll/offer when an empty collection is a normal situation; use getFirst/removeFirst/addFirst when empty means something is wrong.

An example with both semantics on the same class:

Notice the variable's type: here it is declared as a LinkedList because we need methods that List does not have. If you are only going to use it as a queue, the right thing according to the golden rule of 05-02 is to declare it by the interface that reflects its use:

Queue and stack usage in detail are lessons 05-07 and 05-08.

ListIterator is an extension of Iterator exclusive to lists, and it is the correct way of inserting or replacing elements while you traverse. Its API:

The conceptual key: a ListIterator does not point at an element, it points at a gap between elements (a cursor). next() steps over the element to its right and returns its value; previous() steps over the one to its left.

The ^ marks are the possible cursor positions. With the cursor at ^1, next() returns B and leaves the cursor at ^2; previous() would return A and leave it at ^0.

This is the use that justifies its existence:

Three details to understand:

1. it.add(x) inserts at the cursor's position, which after next() is right behind the element returned. That is why the notice appears after the drop.
2. The inserted element is not visited again. add advances the cursor past what was inserted, so there is no infinite loop. Check it: if add did not do that, the new element would be examined and could generate another, indefinitely.
3. There is no ConcurrentModificationException. The iterator is the one doing the modifying, so it updates its own expectedModCount (05-02).

Trying the same with a for-each and list.add(...) would give the exception immediately. And doing it with indices over an ArrayList would force you to recompute the position after every insertion, a classic generator of bounds bugs.

Equivalent to replaceAll when the condition is simple, but it allows arbitrary logic and deciding element by element.

On a LinkedList this is efficient thanks to the prev links; on an ArrayList it is too, because indexed access is O(1). In both cases it is clearer than a decreasing for when you also need to insert or remove.

Important warning: mixing a ListIterator with direct modifications of the list breaks everything. While an iterator is alive, all changes must go through it.

Let us compare the two implementations with a simple experiment. First, a warning to be taken seriously.

Microbenchmarks in Java are treacherous. The JVM compiles the code as it runs (JIT), so the first iterations are much slower than the later ones; the garbage collector may kick in halfway through the measurement; and the compiler may remove entirely a loop whose result is not used, giving you times of zero. The right tool is JMH (Java Microbenchmark Harness), OpenJDK's official library, which handles warm-up, iterations and consuming the results. What follows is an illustrative approximation, useful for seeing orders of magnitude, not for publishing figures.

Typical results on a desktop machine, with the order of magnitude as the only reliable information:

The last row sums up the lesson: the only clear case in favour of LinkedList is inserting at the start, and for that there is a better structure.

And an equally valuable methodological conclusion: measure before optimising. If somebody swaps an ArrayList for a LinkedList "because it inserts faster" without having measured, there is a good chance they have made the program worse.

Here comes BiblioTech's real case. When a material is on loan, an employee can reserve it. Reservations form a queue: they are served in order of arrival, added at the back and consumed at the front. It is the exact pattern where a linked list is appropriate: zero access by index, everything at the ends.

First, the Reservation class. Since it is a piece of data with its own identity and state (fulfilled), we model it as a class, not as a record (04-07):

And the reservation queue of a material:

Full usage:

Notice three deliberate decisions in this code:

• positionOf traverses with for-each, never with get(i). On a LinkedList, the indexed loop would be O(n²).
• cancelLatestOf uses descendingIterator and it.remove(): the iterator already has the node, so the removal is really O(1). It is the legitimate case from section 3.
• moveToFront is honest about its cost: the remove(Object) is O(n) because the reservation has to be located; only the addFirst is O(1). This method would be the first candidate for review if the queue grew a lot, and a PriorityQueue (05-07) would solve the urgency problem better.

And a final design note: although LinkedList works well here, the canonical declaration of a queue is Deque<Reservation> pending = new ArrayDeque<>(). LinkedList has been used because we also need removeIf and traversals, and because this was its natural case; in 05-07 you will see the ArrayDeque version and why it is usually better.

Traversing a LinkedList with an indexed for. for (int i = 0; i < list.size(); i++) list.get(i) is O(n²): every get walks the chain from one end. With 100,000 elements it goes from milliseconds to minutes. Always use for-each or an iterator.

Believing add(i, e) is O(1) on a LinkedList. The insertion is; getting to index i is not. The complete method is O(n). Only the ends and insertions via an iterator are genuinely O(1).

Choosing LinkedList "because it inserts faster" without measuring. In practice it loses almost always on cache locality and memory consumption. Start with ArrayList and change only with data in hand.

Using LinkedList as a queue when ArrayDeque exists. ArrayDeque is faster and takes less space. The only reason to prefer LinkedList is needing List and Deque in the same variable, or accepting null elements.

Confusing get/remove with peek/poll. On an empty list, getFirst() and removeFirst() throw NoSuchElementException; peekFirst() and pollFirst() return null. Choose according to whether an empty queue is normal or is an error.

Modifying the list while a ListIterator is alive. Any direct list.add, list.remove or list.clear invalidates the iterator and causes ConcurrentModificationException on the next operation. While the iterator exists, everything goes through it.

Forgetting that it.add(x) does not revisit what was inserted. That is what avoids the infinite loop, and it is the right behaviour; but if you expected the new element to be evaluated, it will not be.

Sorting a LinkedList often. sort dumps to an array, sorts and rebuilds the whole node chain. If you are going to sort frequently, use ArrayList; if you need permanent ordering, TreeSet or PriorityQueue (05-06, 05-07).

Tip: declare by the interface that reflects the use. If it is a list, List<X> l = new ArrayList<>(). If it is a queue, Deque<X> d = new ArrayDeque<>(). Declaring LinkedList<X> is only justified when you need both faces at once.

Tip: LinkedList is a magnificent mental exercise. Implementing it by hand —with nodes, prev and next— teaches more about pointers and data structures than many books. But in production, ArrayList.

Write OperationHistory to hold the last N catalogue operations (strings such as "add:978-0000000001"), using a LinkedList as the internal structure:

• void register(String operation): adds at the end and, if the maximum is exceeded, removes the oldest (the first).
• String latest() and String oldest(): without removing them, returning null if it is empty.
• List<String> inReverseOrder(): from the most recent to the oldest, with descendingIterator.
• int removeByPrefix(String prefix): removes all those starting with that prefix and returns how many it took out.

Justify in comments which operations are really O(1) and which are not.

Write a static method void insertSeparators(List<Material> catalog) that walks a catalogue already sorted by type and inserts, before the first material of each type, a special separator Material (use a Book with the title "--- BOOKS ---" or create a small class Separator extends Material).

It must work with a ListIterator and without causing ConcurrentModificationException or infinite loops. Explain why the insertion is not visited again.

Then add a version insertSeparatorsWrong that tries the same with a for-each and document exactly what fails.

Write Benchmark to compare ArrayList and LinkedList in four scenarios, with prior warm-up and with protection against the JIT removing the code:

1. Adding N elements at the end.
2. Traversing with for-each and summing.
3. Inserting 10,000 elements at the start.
4. Removing by criterion with removeIf.

Print a table with the times and write, in a final comment, your reasoned conclusion and the warning about JMH.

Solution 1

A test:

This is LinkedList's ideal use case: a sliding window. Each entry adds at one end and removes at the other, both genuinely O(1). With an ArrayList, every remove(0) would shift the whole list. That said, the professional answer for a sliding window is ArrayDeque (05-07), which does the same with a circular array, without nodes and without pressure on the collector.

Solution 2

The sequence previous() → add(...) → next() deserves a careful explanation. After it.next() the cursor is behind the current material, but the separator has to go in front. previous() steps the cursor back to the previous position (and returns the same material, which we discard). add inserts there and leaves the cursor behind what was inserted, that is, still in front of the material. next() steps over it again to carry on.

That automatic cursor advance after add is exactly what prevents the infinite loop: the inserted element is never returned by next(). If add did not do it, the next next() would return the separator, whose type would not match previousType either, and another separator would be inserted, indefinitely.

And about the incorrect version, there are two stacked failures: the ConcurrentModificationException and, more fundamentally, the fact that catalog.add(x) inserts at the end, not where you are traversing. It is a good reminder that the for-each does not know its own position.

Solution 3

Typical output (the absolute values vary a lot depending on the machine; what matters is the ratio):

Reasoned conclusion. LinkedList wins in a single scenario, number 3, and it wins by a lot: inserting at the start is its natural ground. In the other three it loses, and in traversal —the most frequent operation in any real program— it is about seven times slower with the same O(n) complexity: the difference is purely cache locality.

Scenario 4 is especially revealing. removeIf is O(n) on both and removes in O(1) on both (via the iterator), yet LinkedList still loses, because walking the scattered nodes dominates the total time.

And the decisive observation: if you add an ArrayDeque with addFirst to the test bench, scenario 3 drops to roughly 1 ms, beating them both. That is, even in the one case where LinkedList beats ArrayList, it is not the best tool available. That is why the practical recommendation is: ArrayList for lists, ArrayDeque for queues and stacks, LinkedList hardly ever.

Repeat the warning with every number you see: for real performance decisions, measure with JMH on your specific workload.

You now know what a doubly linked list is: a chain of nodes with prev, item and next, with no array, no capacity and no indices. You understand what that really implies: ~28 bytes per element against the ~4 of an ArrayList, and nodes scattered around the heap that destroy cache locality and make traversing it several times slower even though the complexity is the same O(n). You have seen in the JDK's own code that node(index) walks the chain, and with that you have dismantled the myth: inserting and deleting is O(1) only if you already have the position, which happens only at the ends and through an iterator; getting there by index costs O(n).

You have the operation-by-operation comparison table and the honest conclusion that follows from it: ArrayList wins almost always, because System.arraycopy is a native block instruction, because the cache dominates, because nodes put pressure on the collector and because insertions "in the middle" almost never are. You know that the Framework's own co-author considers it dispensable today, and that its real niche is not being a List but being a Deque, ground on which ArrayDeque beats it. You also know how to spot the performance mistake that slips in most often: an indexed for over a LinkedList is disguised O(n²).

You know its dual List + Deque nature and the whole family of end operations, with the distinction between the variant that throws an exception (getFirst, removeFirst) and the one that returns null (peekFirst, pollFirst) —which 05-07 will develop—. And you have mastered the ListIterator: the cursor that lives between elements, the two-way traversal, add and set during the traversal, why what is inserted is not visited again and why it is the only correct way of inserting while you traverse.

You know how to measure honestly: warm up the JVM, consume the results so that the JIT does not remove the loops, distrust absolute numbers and turn to JMH when the decision really matters. And above all, you have adopted the professional criterion: measure before optimising, because swapping ArrayList for LinkedList "because it inserts faster" is, almost always, making the program worse.

BiblioTech has gained the Reservation class and a ReservationQueue that enqueues at the back, serves at the front, cancels through a descending iterator in real O(1) and expires old reservations with removeIf. It is the only point in the project where a linked list was justified, and even so you have seen why in 05-07 you will rewrite it with ArrayDeque.

And one weakness remains that is becoming unbearable. Catalog.remove(reference) walks the whole list. LoanManager.returnItem(reference, day) walks the whole list. ReservationQueue.positionOf(employee) walks the whole list. Every time BiblioTech has to find something by its identifier, it looks at them one by one. With five materials it is free; with fifty thousand, every search is fifty thousand comparisons, and grouping loans by employee with nested loops is O(n²).

In the next lesson, HashMap, that ends. You will see the structure that finds an element by its key in constant time no matter how many there are: how the hash function works, what buckets are, what happens when two keys collide, why the load factor is 0.75 and what happens during a rehash. And there the promise made in module 3 will finally be kept: you will see with a practical demonstration why equals and hashCode always had to go together, and exactly what happens to an object that enters a map with one of the two badly implemented.