LinkedList

TL;DR

• LinkedList is a doubly-linked list implementation of the List and Deque interfaces.
• Elements are not stored in contiguous memory; they are nodes containing a value and pointers to the previous/next nodes.
• Inserting/deleting is fast $O(1)$ if you already have a reference to the node, but random access via index is slow $O(n)$.

Concept

Unlike ArrayList, LinkedList has no underlying array, so it never has to undergo an expensive “resize” operation. Memory is allocated node-by-node on the heap.

However, because the nodes are scattered in memory, it suffers from poor CPU cache locality. To find the 500th element, the JVM must start at node 1, go to node 2, go to node 3… all the way to 500.

Interfaces Implemented

• List: For standard list operations (add, get, remove).
• Deque (Double Ended Queue): Provides operations to manipulate both ends of the list (addFirst, addLast, pollFirst, pollLast).

Examples

import java.util.LinkedList;

public class LinkedListExample {
    public static void main(String[] args) {
        // Using it as a standard List or Deque
        LinkedList<String> train = new LinkedList<>();
        
        // Appending
        train.add("Engine");
        train.add("Passenger Car 1");
        
        // Deque methods (O(1) operations)
        train.addFirst("Snowplow");
        train.addLast("Caboose");
        
        System.out.println(train); 
        // [Snowplow, Engine, Passenger Car 1, Caboose]
        
        // O(n) operation - has to traverse the links!
        String middle = train.get(2); 
    }
}

Interview Questions

Q: Is LinkedList faster than ArrayList for insertions and deletions?
A: In theory, yes. In a LinkedList, inserting a node is $O(1)$ because you just change two pointers. In an ArrayList, inserting in the middle is $O(n)$ because you have to shift all subsequent elements.
However, in modern practice, ArrayList often outperforms LinkedList even for middle insertions because of CPU caching. Contiguous arrays are highly optimized by modern hardware, whereas traversing a LinkedList to find the insertion point causes cache misses. LinkedList is rarely the best choice in modern Java.

Q: Why does Java’s LinkedList implement Deque?
A: Because a doubly-linked list naturally provides highly efficient $O(1)$ operations at both ends (the head and the tail). Implementing Deque allows developers to easily use LinkedList as a Queue (FIFO) or a Stack (LIFO).