LinkedList in Java

Analogy categoryAnalogies

1. Introduction

LinkedList is a doubly-linked list implementation in Java that implements both the List and Deque interfaces. Each element (node) stores a reference to the previous and next node, rather than being stored in a contiguous array like ArrayList.

🏏

Cricket analogy: A LinkedList is like a chain of fielders passing the ball hand to hand across the outfield relay, each only aware of the fielder before and after, unlike ArrayList's fixed row of numbered stumps in a contiguous line.

Because of this node-based structure, LinkedList excels at fast insertions and removals at the beginning or end of the list, and it can also be used as a stack, queue, or double-ended queue via its Deque methods.

🏏

Cricket analogy: A LinkedList is like a substitutes' bench where a new bowler can be added or removed from either end instantly, and the bench itself can double as a rotation queue or a last-in-first-out reserve pool.

2. Syntax

text

List<String> list = new LinkedList<>();
Deque<String> deque = new LinkedList<>();

list.add("A");
((LinkedList<String>) list).addFirst("Start");
((LinkedList<String>) list).addLast("End");
deque.offerFirst("X");
deque.offerLast("Y");
deque.pollFirst();

3. Explanation

LinkedList implements List, so it supports index-based operations like get(index), but this requires traversing the list node by node from the nearer end, making get(index) O(n) — significantly slower than ArrayList's O(1) index access.

🏏

Cricket analogy: Finding the 7th fielder in a LinkedList-style relay chain means tapping each fielder in sequence to reach them, an O(n) walk, unlike ArrayList where you can shout directly to fielder number 7 in O(1).

Where LinkedList shines is insertion and removal at the ends: addFirst(), addLast(), removeFirst(), and removeLast() are all O(1) because they only require updating a few pointers, with no shifting involved.

🏏

Cricket analogy: Adding a bowler to the front or back of the bench in a LinkedList is O(1), just relinking two pointers, unlike shifting every player down a slot the way an ArrayList would.

Exam trap: Do not assume LinkedList is always faster than ArrayList. For random-access-heavy workloads, ArrayList's O(1) get() beats LinkedList's O(n) get(). LinkedList only wins for insert/remove at the ends.

4. Example

java

import java.util.*;

public class LinkedListDemo {
    public static void main(String[] args) {
        LinkedList<String> tasks = new LinkedList<>();
        tasks.addLast("Task1");
        tasks.addLast("Task2");
        tasks.addFirst("UrgentTask");

        System.out.println("Tasks: " + tasks);
        System.out.println("First: " + tasks.getFirst());
        System.out.println("Last: " + tasks.getLast());

        tasks.removeFirst();
        System.out.println("After removeFirst: " + tasks);

        // Using as a Deque
        Deque<String> stack = new LinkedList<>();
        stack.push("A");
        stack.push("B");
        System.out.println("Stack pop: " + stack.pop());
    }
}

5. Output

text

Tasks: [UrgentTask, Task1, Task2]
First: UrgentTask
Last: Task2
After removeFirst: [Task1, Task2]
Stack pop: B

6. Key Takeaways

LinkedList is a doubly-linked list implementing both List and Deque.
get(index) is O(n) because it requires traversal from the nearer end.
addFirst()/addLast()/removeFirst()/removeLast() are O(1).
Contrast with ArrayList: LinkedList trades fast random access for fast end insertions.
Can be used as a Stack, Queue, or Deque via its interface methods.