LinkedList Class in Java - Quiz

LinkedList is a doubly linked list with no array inside. Every element lives in a separate node object, Node — a static nested class with the fields item (the element itself), next (the next node) and prev (the previous node). The list itself keeps only references to the first (first) and the last (last) node and the element count (size). The first node has prev == null, the last one has next == null.

private static class Node<E> {
    E item;
    Node<E> next;
    Node<E> prev;
}

Older books call the node Entry, with an element field, and describe a circular list closed through an empty header node — that was the design up to Java 6 inclusive. Since Java 7 the class uses Node, first and last; the doubly linked list principle has not changed.

get(index) cannot jump straight to a cell the way an array does: the internal node() method walks the references from node to node. To shorten the path, it starts from the nearer end — from first if the index is in the first half and from last if it is in the second. So get(0) and get(size() - 1) are instant, while an element in the middle takes up to n/2 steps — that is O(n). set(i, e), add(i, e) and remove(i) go through the same node().

The loop for (int i = 0; i < list.size(); i++) list.get(i); searches for every node again, and the pass becomes O(n²): about n²/4 hops in total, about 2.5 billion for 100,000 elements. A for-each loop, forEach() and an explicit iterator remember the current node and pass through the list in O(n) — the same 100,000 steps.

Only when the node has already been found. The relinking itself costs O(1): to remove B from A–B–C, it is enough to point A.next to C and C.prev to A, and the other nodes are not touched. But add(i, e), remove(i) and remove(Object) first find the node by walking the chain, so in total that is O(n).

A real O(1) happens in two cases: at the ends of the list (addFirst(), addLast(), removeFirst(), removeLast()) and at the current position of a ListIterator, which already stands on the node:

List<String> list = new LinkedList<>(List.of("A", "B", "C", "D"));
ListIterator<String> it = list.listIterator();
while (it.hasNext()) {
    String s = it.next();
    if (s.equals("B")) it.add("B2");     // insert after B in O(1)
    else if (s.equals("C")) it.remove(); // remove C in O(1)
}
System.out.println(list); // [A, B, B2, D]

ArrayList stores elements in an Object[] array, while LinkedList stores them in linked Node objects. That gives different complexity:

• get(i), set(i, e): O(1) in ArrayList, O(n) in LinkedList, up to n/2 hops;
• add(0, e), remove(0): O(n) in ArrayList (the array is shifted), O(1) in LinkedList;
• add(i, e), remove(i) in the middle: O(n) in both (in LinkedList — to find the node);
• insertion/removal through a ListIterator: O(n) in ArrayList, O(1) in LinkedList.

In practice ArrayList is often faster even where LinkedList has the better estimate: array elements sit next to each other in memory and fit the CPU cache well, and System.arraycopy() shifts references very quickly. A LinkedList node takes about 24 bytes, nodes are scattered across the heap, and every hop along next is a potential cache miss.

So ArrayList is the default for a list, and LinkedList is for frequent insertions and removals through an iterator or at both ends, once a measurement confirms the advantage. Even the author of the class, Joshua Bloch, admitted: “I wrote it, and I never use it”.

There are two constructors. LinkedList() creates an empty list (first == last == null, size == 0); nodes appear only when elements are added. LinkedList(Collection<? extends E> c) copies the elements of c in the order of its iterator; if c == null, it throws NullPointerException, while null elements inside c are allowed. There is no capacity constructor: new LinkedList<>(100) does not compile.

LinkedList implements both List and Deque, so the variable is declared with the interface you need: List<String> list = new LinkedList<>(); for index-based work, Deque<String> deque = new LinkedList<>(); for a queue or a stack. Through a List variable the Deque methods (push(), pollLast()) are not available. As a stack, push() and pop() work with the head, while add() and offer() append to the tail.

It can store null: the element lives in the item field of a separate node, and null there gets in nobody's way (unlike ArrayDeque, which marks empty array cells with null). contains(null) and indexOf(null) find it. But in the role of a queue it is risky: poll() and peekFirst() also return null for an empty list, and the two cases cannot be told apart.

It is not thread-safe: with concurrent writes from several threads the node references can get out of sync and elements are lost. The simple option is Collections.synchronizedList(new LinkedList<>()); for a queue shared between threads ConcurrentLinkedDeque or LinkedBlockingDeque is a better fit.

LinkedList iterators are fail-fast: if you call list.add() or list.remove() inside an iteration, the next it.next() throws ConcurrentModificationException. Change the list during iteration only through the iterator's own methods.