LinkedList

LinkedList Structure

LinkedList is a doubly linked list implementation of the List and Deque interfaces. Each element is a Node containing the data and pointers to both the previous and next nodes.

Node structure:

[prev | data | next] <-> [prev | data | next] <-> [prev | data | next]

Key characteristics:

• Doubly linked — can traverse forward and backward
• No internal array — elements are scattered in memory
• Each node has overhead: two pointers (prev/next) plus the data
• Implements both List and Deque interfaces

import java.util.*;

public class LinkedListStructureDemo {
    public static void main(String[] args) {
        // Create LinkedList
        LinkedList<String> list = new LinkedList<>();

        // Adding elements
        list.add("C");
        list.add("D");
        list.addFirst("B");
        list.addLast("E");
        list.add(0, "A"); // insert at beginning
        System.out.println("List: " + list); // [A, B, C, D, E]

        // Accessing elements
        System.out.println("First: " + list.getFirst()); // A
        System.out.println("Last: " + list.getLast()); // E
        System.out.println("Element at 2: " + list.get(2)); // C

        // Removing elements
        list.removeFirst(); // removes A
        list.removeLast(); // removes E
        list.remove("C"); // removes first occurrence of C
        System.out.println("After removes: " + list); // [B, D]

        // Deque operations
        LinkedList<Integer> deque = new LinkedList<>();
        deque.push(1);    // same as addFirst
        deque.push(2);    // same as addFirst
        deque.push(3);    // same as addFirst
        System.out.println("Deque: " + deque); // [3, 2, 1]
        System.out.println("Pop: " + deque.pop()); // 3 (same as removeFirst)
        System.out.println("Peek: " + deque.peek()); // 2 (same as getFirst)

        // Queue operations
        Queue<String> queue = new LinkedList<>();
        queue.offer("First");
        queue.offer("Second");
        queue.offer("Third");
        System.out.println("Queue: " + queue);
        System.out.println("Poll: " + queue.poll()); // First
        System.out.println("Peek: " + queue.peek()); // Second
    }
}

Memory overhead: Each node in a LinkedList takes approximately 24-32 bytes of overhead (two pointers + object header) plus the data. For small data types, this overhead can be significant. An ArrayList is much more memory-efficient for primitive types.

Deque Operations

LinkedList implements the Deque (double-ended queue) interface, making it a versatile data structure that can function as both a queue and a stack.

Queue operations (FIFO):

• offer(e) / add(e) — insert at tail
• poll() / remove() — remove from head
• peek() / element() — view head

Stack operations (LIFO):

• push(e) — insert at head
• pop() — remove from head
• peek() — view head

import java.util.*;

public class DequeOperationsDemo {
    public static void main(String[] args) {
        // LinkedList as a Deque
        Deque<String> deque = new LinkedList<>();

        // Adding to both ends
        deque.addFirst("Front1");
        deque.addLast("Back1");
        deque.addFirst("Front2");
        deque.addLast("Back2");
        System.out.println("Deque: " + deque); // [Front2, Front1, Back1, Back2]

        // Removing from both ends
        System.out.println("removeFirst: " + deque.removeFirst()); // Front2
        System.out.println("removeLast: " + deque.removeLast()); // Back2
        System.out.println("After: " + deque); // [Front1, Back1]

        // Peek without removing
        System.out.println("peekFirst: " + deque.peekFirst()); // Front1
        System.out.println("peekLast: " + deque.peekLast()); // Back1

        // Stack behavior (LIFO)
        Deque<Integer> stack = new LinkedList<>();
        stack.push(10);  // addFirst
        stack.push(20);  // addFirst
        stack.push(30);  // addFirst
        System.out.println("Stack: " + stack); // [30, 20, 10]
        System.out.println("Pop: " + stack.pop()); // 30
        System.out.println("Pop: " + stack.pop()); // 20
        System.out.println("Peek: " + stack.peek()); // 10

        // Queue behavior (FIFO)
        Deque<String> queue = new LinkedList<>();
        queue.offer("Job1");
        queue.offer("Job2");
        queue.offer("Job3");
        System.out.println("\nQueue: " + queue);
        System.out.println("Poll: " + queue.poll()); // Job1
        System.out.println("Poll: " + queue.poll()); // Job2

        // Checking emptiness
        System.out.println("isEmpty: " + queue.isEmpty());
        System.out.println("size: " + queue.size());

        // Iterating
        Deque<String> iterate = new LinkedList<>(Arrays.asList("A", "B", "C", "D"));
        System.out.println("\nForward:");
        Iterator<String> it = iterate.iterator();
        while (it.hasNext()) {
            System.out.print(it.next() + " ");
        }
        System.out.println("\nBackward:");
        Iterator<String> rit = iterate.descendingIterator();
        while (rit.hasNext()) {
            System.out.print(rit.next() + " ");
        }
    }
}

Use cases for Deque:

• Stack: browser back/forward, undo/redo, expression evaluation
• Queue: task scheduling, breadth-first search, print jobs
• Deque: sliding window, palindrome checking, work-stealing

Time Complexity of LinkedList

Operation	Time Complexity	Notes
get(index)	O(n)	Must traverse from head or tail
set(index, element)	O(n)	Must traverse to position
addFirst/addLast	O(1)	Direct pointer manipulation
add(index, element)	O(n)*	Find position O(n) + insert O(1)
removeFirst/removeLast	O(1)	Direct pointer manipulation
remove(int index)	O(n)	Find position O(n) + remove O(1)
remove(Object)	O(n)	Search + remove
contains(Object)	O(n)	Linear search
indexOf(Object)	O(n)	Linear search
size()	O(1)	Maintained as field
isEmpty()	O(1)	Size check

*add(index) is O(n) to find the position, then O(1) to insert.

import java.util.*;

public class LinkedListComplexityDemo {
    public static void main(String[] args) {
        LinkedList<Integer> list = new LinkedList<>();
        for (int i = 0; i < 5; i++) {
            list.add(i);
        }
        System.out.println("List: " + list); // [0, 1, 2, 3, 4]

        // O(1) - addFirst/addLast
        list.addFirst(-1);  // O(1)
        list.addLast(5);    // O(1)
        System.out.println("After O(1) adds: " + list); // [-1, 0, 1, 2, 3, 4, 5]

        // O(n) - get(index)
        System.out.println("O(n) get(3): " + list.get(3)); // 2
        // get(3) traverses 3 nodes from head (or 3 from tail)

        // O(n) - add(index)
        list.add(3, 99); // find position O(n), insert O(1)
        System.out.println("After O(n) insert: " + list);

        // O(n) - remove(index)
        list.remove(3); // find position O(n), remove O(1)
        System.out.println("After O(n) remove: " + list);

        // Comparison: when is LinkedList faster?
        // Adding/removing at both ends: O(1)
        // Random access: O(n) vs ArrayList O(1)
    }
}

Key insight: LinkedList's O(1) insert/delete at ends is why it implements Deque. But for random access (get by index), ArrayList is O(1) while LinkedList is O(n). This is the primary tradeoff.

LinkedList vs ArrayList

Both implement List, but their internal structures lead to very different performance profiles.

Aspect	ArrayList	LinkedList
Structure	Dynamic array	Doubly linked list
Random access	O(1)	O(n)
Add/remove at end	O(1) amortized	O(1)
Add/remove at beginning	O(n)	O(1)
Add/remove at middle	O(n)	O(n)*
Memory	Compact	Overhead per node
Cache locality	Excellent	Poor
Implements Deque	No	Yes

*LinkedList is O(n) to find the position, then O(1) to insert/remove.

import java.util.*;

public class LinkedListVsArrayListDemo {
    public static void main(String[] args) {
        int size = 100000;

        // Performance test: random access
        ArrayList<Integer> arrayList = new ArrayList<>();
        LinkedList<Integer> linkedList = new LinkedList<>();
        for (int i = 0; i < size; i++) {
            arrayList.add(i);
            linkedList.add(i);
        }

        long start = System.nanoTime();
        for (int i = 0; i < size; i++) {
            arrayList.get(i); // O(1)
        }
        long arrayListAccess = System.nanoTime() - start;

        start = System.nanoTime();
        for (int i = 0; i < size; i++) {
            linkedList.get(i); // O(n)!
        }
        long linkedListAccess = System.nanoTime() - start;

        System.out.println("Random access - ArrayList: " + arrayListAccess / 1_000_000 + "ms");
        System.out.println("Random access - LinkedList: " + linkedListAccess / 1_000_000 + "ms");

        // Performance test: add at beginning
        arrayList = new ArrayList<>(Arrays.asList(new Integer[size]));
        linkedList = new LinkedList<>(Arrays.asList(new Integer[size]));

        start = System.nanoTime();
        arrayList.add(0, -1); // O(n) - shift all
        long arrayListInsert = System.nanoTime() - start;

        start = System.nanoTime();
        linkedList.addFirst(-1); // O(1)
        long linkedListInsert = System.nanoTime() - start;

        System.out.println("\nAdd at beginning - ArrayList: " + arrayListInsert + " ns");
        System.out.println("Add at beginning - LinkedList: " + linkedListInsert + " ns");

        // Memory comparison
        System.out.println("\nMemory: ArrayList is ~3x more compact than LinkedList");
        System.out.println("due to node overhead in LinkedList (prev + next pointers)");

        // Practical recommendation
        System.out.println("\n--- Recommendation ---");
        System.out.println("Default: ArrayList");
        System.out.println("Use LinkedList when: frequent add/remove at both ends");
        System.out.println("Use ArrayDeque for stack/queue instead of LinkedList");
    }
}

Practical advice:

• Default to ArrayList for almost all use cases
• Use LinkedList when you need a Deque and ArrayDeque doesn't fit
• Never use LinkedList for random access patterns
• Consider ArrayDeque over LinkedList for stack/queue implementations (better cache locality)