LinkedList

#Introduction

LinkedList is one of the most misunderstood classes in the Java Collections Framework. Many developers believe:

"LinkedList is always faster than ArrayList."

This is not true. A 5+ years Java developer is expected to know when LinkedList is better, when ArrayList is better, and how LinkedList works internally.

#What is LinkedList?

LinkedList is a doubly linked list implementation of the List interface.

Package:

java.util.LinkedList

Declaration:

public class LinkedList<E>
        extends AbstractSequentialList<E>
        implements List<E>,
                   Deque<E>,
                   Cloneable,
                   Serializable

Notice: unlike ArrayList, LinkedList implements List, Queue and Deque. That makes it much more versatile.

#Position in Collection Hierarchy

#Characteristics

• Maintains insertion order
• Allows duplicates
• Allows multiple null values
• Dynamic size
• Fast insertion/deletion after locating the position
• Slow random access
• Higher memory consumption
• Not thread-safe

#Internal Structure

Unlike ArrayList, LinkedList does NOT use an array. It uses Nodes. Each node stores:

• Data
• Previous node reference
• Next node reference

Node Class (Simplified)

Internally Java has something similar to:

private static class Node<E> {
    E item;
    Node<E> next;
    Node<E> prev;

    Node(Node<E> prev, E element, Node<E> next) {
        this.item = element;
        this.prev = prev;
        this.next = next;
    }
}

Every element becomes a Node.

#Memory Representation

list.add("A");
list.add("B");
list.add("C");

#Why a Doubly Linked List?

Suppose Java used a singly linked list. Backward traversal would not be possible, and removing a node would require finding its previous node. A doubly linked list allows:

• Forward traversal
• Backward traversal
• Easier deletion

#Head and Tail References

LinkedList stores:

Node<E> first;
Node<E> last;

These references allow efficient insertion/removal at both ends.

#Adding Elements

LinkedList<Integer> list = new LinkedList<>();
list.add(10);
list.add(20);
list.add(30);

#Accessing Elements

list.get(5);

Can LinkedList jump directly to index 5? No. It must traverse.

Optimization Inside LinkedList

Java is smarter. If you need list.get(98) and the total size is 100, Java starts from the tail instead of the head. For list.get(2) it starts from the head.

if (index < size / 2)
    start from head
else
    start from tail

#Insertion

Adding at the beginning

list.addFirst(100);

Adding at the end

list.addLast(40);   // O(1)

Adding in the middle

Traversal is needed first.

list.add(5, 100);

#Deletion

#Why is Insertion Faster?

ArrayList — inserting at the beginning of A B C D needs shifting to get 100 A B C D. All elements move.

LinkedList — 100 → A → B → C → D. Only references change.

#Queue Operations

LinkedList implements Deque. Therefore these are available:

offer(), offerFirst(), offerLast(), poll(), pollFirst(), pollLast(), peek(), peekFirst(), peekLast()

#Stack Operations

LinkedList can also behave as a Stack with push(), pop() and peek().

LinkedList<Integer> stack = new LinkedList<>();
stack.push(10);
stack.push(20);
System.out.println(stack.pop());

20

#Null Values and Duplicates

Nulls are allowed:

list.add(null);
list.add(null);

Duplicates are allowed:

list.add("Java");
list.add("Java");

[Java, Java]

#Thread Safety

#Internal Source Code (Simplified)

Adding last:

void linkLast(E e) {
    Node<E> l = last;
    Node<E> newNode = new Node<>(l, e, null);
    last = newNode;
    if (l == null)
        first = newNode;
    else
        l.next = newNode;
}

Only references change.

#Memory Usage

Interview favourite. Each node stores data plus a previous and next reference. Compared to ArrayList, memory usage is higher.

Extra references consume additional memory.

#Cache Locality

• ArrayList — A B C D E stored contiguously. CPU cache-friendly.
• LinkedList — nodes are scattered in memory. Poor cache locality.

Hence iteration is generally slower than ArrayList. (Interview favourite.)

#ArrayList vs LinkedList

*Amortized O(1)

#When Should You Use LinkedList?

Use LinkedList when:

• Frequent insertions/removals at the beginning or end
• Queue implementation
• Deque implementation
• Stack implementation (though ArrayDeque is generally preferred)
• Sequential traversal

Avoid LinkedList when:

• Frequent random access
• Read-heavy applications
• Memory optimization is important

#Time Complexity