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:

1. The actual data (e.g., "BMW").
2. 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.