25. LinkedLists: The Alternative

[!NOTE] The ArrayList is the default dynamic list for 90% of use cases. But what if you are building an application where you are rapidly inserting or deleting thousands of items from the middle of a list constantly?

If you have an ArrayList of 10,000 items, and you command it to delete the item at index 1... the CPU must painstakingly shift the remaining 9,999 items backwards one by one in memory to fill the gap. This is devastatingly slow.

The LinkedList Architecture

The LinkedList class is an almost identical twin to the ArrayList. They implement the exact same core Interfaces, meaning you interact with them using identical methods (.add(), .get(), .remove()).

However, under the hood, they are wildly different.

A LinkedList does not store data in an unbroken contiguous block of memory. Instead, it stores elements in isolated "Nodes" scattered randomly across RAM.

Each Node contains two things:

The actual data (e.g., "BMW").
A direct memory pointer to the Next node in line, and the Previous node in line.

Why is this good?

If you want to insert a new car directly into the middle of a 10,000 car list, the LinkedList simply tells the node before it to point to the new car, and the new car to point to the node after it. It performs exactly two pointer updates in memory, taking 0.001 milliseconds! It does NOT have to shift 5,000 cars backwards.

Why is this bad?

If you want to read cars.get(5000), an ArrayList can do math and jump directly to that exact spot in memory instantly.

A LinkedList cannot. It has to start at Node 0, ask it where Node 1 is, jump to Node 1, ask it where Node 2 is... and physically traverse the chain 5,000 times until it reaches the target. Thus, Reading data from a LinkedList is extremely slow!

Syntax

The syntax is absolutely identical to an ArrayList.

import java.util.LinkedList;

public class Main {
  public static void main(String[] args) {
    LinkedList<String> cars = new LinkedList<String>();
    
    // Completely identical to ArrayList!
    cars.add("Volvo");
    cars.add("BMW");
    cars.add("Ford");
    cars.get(0);
    cars.remove(1);
    
    // Bonus methods exclusive to LinkedList!
    cars.addFirst("Mazda");
    cars.addLast("Toyota");
  }
}

[!IMPORTANT] Summary Table

Use an ArrayList if you plan to do massive amounts of Random Reading (.get()).

Use a LinkedList if you plan to do massive amounts of Inserting/Deleting in the middle or ends of the list.

LinkedList Is Rarely the Default Choice

LinkedList is useful to understand, but ArrayList is usually the better default in real Java code. Modern CPUs are very fast with contiguous array memory, and many programs read far more often than they insert in the middle.

When LinkedList Can Make Sense

You need frequent additions/removals at both ends.
You are using it through Deque behavior and understand the tradeoffs.
You rarely need random access by index.

Prefer ArrayDeque for Queues and Stacks

Deque<String> queue = new ArrayDeque<>();
queue.offer("first");
queue.offer("second");

System.out.println(queue.poll()); // first

For stack and queue behavior, ArrayDeque is usually faster and cleaner than LinkedList.

Common Mistakes

Assuming LinkedList is always faster because insertion can be cheap.
Using get(index) heavily on a linked list.
Ignoring memory overhead from node objects and pointers.
Choosing implementation classes before thinking about operations.

Mini Practice

Implement a simple waiting line using ArrayDeque. Add three names, serve two people, and print who remains.

Practice Lab: Waiting Line Queue

Practice queue-style operations and compare implementation choices.

Create a Deque<String> using ArrayDeque.
Add three customer names using offer.
Serve two customers using poll.
Print the remaining queue.
Repeat using LinkedList and compare the syntax.

Goal: Understand queue behavior and why ArrayDeque is often preferred for stack/queue tasks.

Revision Checkpoint

LinkedList: Node-based list with pointers.
Random access: Slower than ArrayList.
End operations: Can be useful for queue-like behavior.
ArrayDeque: Usually preferred for stack and queue tasks.
Decision habit: Choose by operations, not by class name.

Before the quiz: Explain why get(5000) is expensive in a linked list.