☕ JavaCollections Framework

LinkedList

LinkedList is a doubly-linked list implementation of both the List and Deque interfaces. Each element is stored in a separate Node object that holds the element value plus references to the previous and next nodes in the chain. LinkedList provides O(1) insertion and removal at the beginning and end of the list, making it suitable as a stack, queue, or deque. However, it provides O(n) random access by index, making it unsuitable for indexed access patterns.

How LinkedList Works Internally

LinkedList stores each element in a private Node object. A Node has three fields: the element value (item), a reference to the previous Node (prev), and a reference to the next Node (next). The LinkedList itself holds references only to the first Node (first) and the last Node (last), plus the size count. There is no array — elements are scattered across the heap connected by references. This structure is the opposite of ArrayList in memory terms. ArrayList stores elements in a contiguous block, making cache performance excellent for sequential and random access. LinkedList elements are spread throughout the heap — each Node is a separate heap allocation. Walking from element to element requires following pointer references, which can cause many cache misses because the nodes are not adjacent in memory. This is why LinkedList is often slower than ArrayList in practice for sequential iteration, despite having the same O(n) asymptotic complexity. Adding to the head or tail is O(1) because LinkedList directly holds references to first and last, and updating these references with new nodes is a constant-time operation. Removing from the head or tail is also O(1) for the same reason. These are the operations where LinkedList genuinely outperforms ArrayList. Adding or removing at an arbitrary position requires traversing to that position, which is O(n). LinkedList optimises this by checking whether the index is in the first or second half of the list and traversing from the closer end, but this remains O(n) in the worst case. ListIterator maintains a current Node reference and provides O(1) insertion and removal at the current position — this is the only way to take full advantage of LinkedList's structural strengths for mid-list operations.

Java

// ── Internal Node structure: ─────────────────────────────────────────
// private static class Node<E> {
//     E item;
//     Node<E> next;
//     Node<E> prev;
// }
//
// LinkedList<E> {
//     transient Node<E> first;   // head of list
//     transient Node<E> last;    // tail of list
//     transient int size;
// }
//
// After adding "A", "B", "C":
//
//   first ──▶ [prev=null | "A" | next] ──▶ [prev | "B" | next] ──▶ [prev | "C" | next=null] ◀── last
//             Node                          Node                          Node

// ── Creating a LinkedList: ────────────────────────────────────────────
LinkedList<String> ll = new LinkedList<>();
List<String>       list   = new LinkedList<>();   // as List
Deque<String>      deque  = new LinkedList<>();   // as Deque
Queue<String>      queue  = new LinkedList<>();   // as Queue

// ── Head/tail operations — O(1): ──────────────────────────────────────
ll.addFirst("first");      // insert at head
ll.addLast("last");        // insert at tail
ll.add("appended");        // same as addLast

String head = ll.getFirst();  // peek head — does not remove
String tail = ll.getLast();   // peek tail — does not remove

ll.removeFirst();             // remove head
ll.removeLast();              // remove tail

// ── Deque operations — both ends: ─────────────────────────────────────
Deque<Integer> dq = new LinkedList<>();
dq.push(1);         // add to front (stack push)
dq.push(2);
dq.push(3);
System.out.println(dq.pop());    // 3 — LIFO stack behaviour

dq.offerLast(10);   // add to back (queue enqueue)
dq.offerLast(20);
System.out.println(dq.pollFirst()); // 2 — FIFO dequeue from front

LinkedList as List, Queue, Stack, and Deque

LinkedList's most distinctive feature is that it simultaneously implements List and Deque, giving it the complete API of both interfaces. This makes LinkedList a versatile structure that can serve as a double-ended queue, a stack, a FIFO queue, and an indexed list — all with the same object. No other standard Java collection spans all four roles. As a Queue (FIFO — first in, first out), use offer() to enqueue at the tail and poll() to dequeue from the head. offer() returns false if the queue cannot accept the element (unlikely for LinkedList which has no capacity limit). poll() returns null if the queue is empty rather than throwing as remove() would. As a Stack (LIFO — last in, first out), use push() to push to the head and pop() to pop from the head. LinkedList.push() is equivalent to addFirst(), and pop() is equivalent to removeFirst(). Note that Java's legacy Stack class extends Vector — for new code, prefer using Deque as a stack via LinkedList or ArrayDeque. As a Deque (double-ended queue), use offerFirst()/offerLast() for adding, pollFirst()/pollLast() for removing, and peekFirst()/peekLast() for viewing without removing. ArrayDeque is actually preferred over LinkedList for pure queue and stack uses. ArrayDeque is backed by a resizable array, has better cache performance than LinkedList for most operations, and consumes less memory because it does not allocate a separate Node object for each element. Use LinkedList when you specifically need both List and Deque semantics simultaneously, or when you are using a ListIterator to perform O(1) insertions at the current position.

Java

LinkedList<String> ll = new LinkedList<>();

// ── As a FIFO Queue: ─────────────────────────────────────────────────
Queue<String> queue = new LinkedList<>();
queue.offer("first");    // enqueue — returns false on failure (never for LinkedList)
queue.offer("second");
queue.offer("third");

System.out.println(queue.peek());    // "first" — view head without removing
System.out.println(queue.poll());    // "first" — remove and return head
System.out.println(queue.poll());    // "second"
System.out.println(queue.size());    // 1

// ── As a LIFO Stack: ─────────────────────────────────────────────────
Deque<Integer> stack = new LinkedList<>();
stack.push(10);   // push to front
stack.push(20);
stack.push(30);

System.out.println(stack.peek());  // 30 — top without removal
System.out.println(stack.pop());   // 30 — LIFO
System.out.println(stack.pop());   // 20

// ── As a Deque (both ends): ───────────────────────────────────────────
Deque<String> deque = new LinkedList<>();
deque.offerFirst("middle");
deque.offerFirst("front");
deque.offerLast("end");
// State: front → middle → end

System.out.println(deque.pollFirst());  // front
System.out.println(deque.pollLast());   // end
System.out.println(deque.peekFirst());  // middle

// ── ListIterator — O(1) insertion at current position: ────────────────
LinkedList<Integer> nums = new LinkedList<>(Arrays.asList(1, 2, 4, 5));
ListIterator<Integer> li = nums.listIterator();

while (li.hasNext()) {
    int n = li.next();
    if (n == 2) {
        li.add(3);   // O(1) insert after current — inserts 3 between 2 and 4
    }
}
System.out.println(nums);   // [1, 2, 3, 4, 5]

// ── ArrayDeque vs LinkedList for queue/stack: ─────────────────────────
// PREFER ArrayDeque for pure queue/stack — better performance:
Deque<String> arrayDeque = new ArrayDeque<>();
arrayDeque.push("first");
arrayDeque.push("second");
// ArrayDeque: no Node allocation overhead, better cache locality

// Use LinkedList when you need List operations alongside queue/stack.

When to Use LinkedList vs ArrayList

The choice between LinkedList and ArrayList is one of the most commonly asked questions in Java, and the answer is almost always ArrayList. Despite LinkedList's theoretical advantages for head insertions and midpoint insertions via iterator, in practice ArrayList is faster for most real-world workloads due to better cache locality. Modern CPUs are extremely effective at sequential array access because hardware prefetchers can predict and load upcoming cache lines. LinkedList's scattered Node allocations defeat this prefetching. LinkedList has measurably better performance than ArrayList in a narrow set of scenarios: when you have a large list and need to insert or remove many elements near the head; when you are implementing a deque or queue and the queue interface semantics are important; or when you are using a ListIterator to make incremental modifications as you traverse a large list. For all other scenarios — which is most Java code — ArrayList is the better choice. It uses less memory per element (no Node wrapper), has better cache performance, and is simpler to reason about. The Java standard library's own LinkedList is implemented and maintained, but the Javadoc for LinkedList itself acknowledges that operations indexing into the list will traverse the list from the beginning or end, whichever is closer, and suggests that ArrayList is usually more efficient. A common mistake is using LinkedList because "insertion is O(1)" — but this O(1) only applies when you already have a reference to the Node (e.g., via ListIterator). If you are inserting by index, it is O(n) to traverse to the position plus O(1) to insert, which is O(n) overall — the same as ArrayList, but with worse constant factors due to pointer chasing.

Java

// ── Performance comparison scenarios: ────────────────────────────────

// ── Scenario 1: Append 1 million elements — ArrayList wins: ──────────
long start = System.nanoTime();
List<Integer> arrayList = new ArrayList<>();
for (int i = 0; i < 1_000_000; i++) arrayList.add(i);
System.out.println("ArrayList append: " + (System.nanoTime() - start) + "ns");

start = System.nanoTime();
List<Integer> linkedList = new LinkedList<>();
for (int i = 0; i < 1_000_000; i++) linkedList.add(i);
System.out.println("LinkedList append: " + (System.nanoTime() - start) + "ns");
// ArrayList is typically faster due to cache locality

// ── Scenario 2: Random access — ArrayList vastly wins: ────────────────
int sum = 0;
for (int i = 0; i < arrayList.size(); i++) sum += arrayList.get(i); // O(1) each
// vs
sum = 0;
for (int i = 0; i < linkedList.size(); i++) sum += linkedList.get(i); // O(n) each — O(n²) total!

// ── Scenario 3: Sequential iteration — both similar: ─────────────────
for (Integer n : arrayList) sum += n;   // array traversal — fast
for (Integer n : linkedList) sum += n;  // pointer chasing — slower in practice

// ── Scenario 4: Frequent head insertion — LinkedList wins: ────────────
Deque<Integer> queue = new LinkedList<>();
for (int i = 0; i < 100_000; i++) {
    queue.addFirst(i);   // O(1)
}
// vs
List<Integer> al = new ArrayList<>();
for (int i = 0; i < 100_000; i++) {
    al.add(0, i);        // O(n) — shifts all elements each time
}

// ── Decision guide: ───────────────────────────────────────────────────
//
// Use ArrayList (default choice) when:
//   ✓ Mostly reading/accessing by index
//   ✓ Appending elements to the end
//   ✓ Sorting the list
//   ✓ Passing to methods expecting List
//
// Use LinkedList when:
//   ✓ Implementing a queue or stack (prefer ArrayDeque though)
//   ✓ Frequent insertions/deletions at head
//   ✓ Using ListIterator for O(1) insert at current position
//   ✓ Need both List and Deque APIs on same object

LinkedList

How LinkedList Works Internally

LinkedList as List, Queue, Stack, and Deque

When to Use LinkedList vs ArrayList

Related Topics in Collections Framework