The Java LinkedList Class: A Comprehensive Guide

The LinkedList class in Java’s Collections Framework is a powerful and flexible implementation of both the List and Deque interfaces. Unlike ArrayList, which is a dynamic array, LinkedList is a doubly-linked list structure. This fundamental difference dictates its performance characteristics and ideal use cases.

What is a Doubly-Linked List?

A LinkedList stores its elements in individual nodes. Each node contains three parts:

The data (the element itself).
A pointer to the next node in the sequence.
A pointer to the previous node in the sequence.

Because it is a doubly-linked list, traversal can happen in both forward and backward directions.

Internal Structure Visualization

HEAD                               TAIL
  ↓                                 ↓
[null|Data1|→] ↔ [←|Data2|→] ↔ [←|Data3|null]

Hierarchy

The LinkedList class extends AbstractSequentialList<E> and implements the following core interfaces:

List<E>: Provides standard sequence operations (ordered collection).
Deque<E> (Double-Ended Queue): Allows elements to be added or removed from both the beginning and the end. This means a LinkedList can be easily used as a Queue, Stack, or Deque.
Cloneable: Supports shallow copying via clone().
Serializable: Can be serialized for persistence or network transmission.

Key Features of `LinkedList` 🌟

Feature	Description
Structure	Doubly-linked list implementation.
Order	Maintains the insertion order of elements.
Elements	Permits duplicates and `null` values.
Random Access	Does not implement the `RandomAccess` interface. Elements can only be accessed sequentially (no fast `get(index)`).
Memory Overhead	Higher than `ArrayList` due to storage of two references per node.
Cache Locality	Poor cache performance compared to array-based structures.
Synchronization	Not synchronized. Must be externally synchronized for concurrent access (e.g., using `Collections.synchronizedList(new LinkedList())`).
Fail-Fast	Iterators are fail-fast, throwing a `ConcurrentModificationException` if the list is structurally modified while being iterated.

Performance and Use Cases 🚀

The choice between ArrayList and LinkedList often comes down to performance trade-offs.

Performance Comparison

Operation	`LinkedList` Time Complexity	`ArrayList` Time Complexity
Insert/Delete (at ends)	O(1) (Fastest)	O(n) for front, O(1) for end
Get Element (by index)	O(n) (Slower)	O(1) (Fastest)
Insert/Delete (in middle)	O(n) to find + O(1) to modify	O(n)
Search (by value)	O(n)	O(n)
Memory Usage	Higher (3 references per node)	Lower (just array + size)

When to Use `LinkedList`

LinkedList should be your collection of choice when your application involves a high frequency of element insertions and deletions at the beginning or end of the list, and a low frequency of random access (using get(index)).

Practical Use Cases:

Implementing Stacks & Queues: The Deque methods like addFirst(), removeLast(), offer(), and poll() make it perfect for these data structures.
Undo/Redo Functionality: The sequence of actions can be stored, and the doubly-linked nature simplifies moving forward (Redo) and backward (Undo).
Browser History: Navigating between Next and Previous pages is a classic doubly-linked list problem.
LRU (Least Recently Used) Cache: Often implemented using a LinkedList (to track usage order) paired with a HashMap (for O(1) lookups).
Music/Video Playlist: Where users frequently add/remove songs and navigate forward/backward.
Text Editor Buffer: Managing text operations with efficient insertion/deletion.

When NOT to Use `LinkedList`

Frequent Random Access: If you need get(index) operations frequently, use ArrayList.
Memory-Constrained Environments: The overhead of maintaining two pointers per element can be significant.
Small Collections: For small lists, the overhead often outweighs benefits.

Comprehensive Method Reference 📝

Core List Methods

Method	Description	Time Complexity
`add(E element)`	Appends an element to the end	O(1)
`add(int index, E element)`	Inserts element at specified position	O(n)
`addAll(Collection<? extends E> c)`	Appends all elements from collection	O(m) where m = collection size
`get(int index)`	Returns element at specified position	O(n)
`set(int index, E element)`	Replaces element at specified position	O(n)
`remove(int index)`	Removes element at specified position	O(n)
`remove(Object o)`	Removes first occurrence of element	O(n)
`clear()`	Removes all elements	O(n)
`contains(Object o)`	Checks if list contains element	O(n)
`indexOf(Object o)`	Returns index of first occurrence	O(n)
`size()`	Returns number of elements	O(1)

Deque-Specific Methods (Head/Tail Operations)

Method	Description	Time Complexity
`addFirst(E element)`	Inserts element at the beginning	O(1)
`addLast(E element)`	Appends element to the end	O(1)
`getFirst()`	Returns first element (throws exception if empty)	O(1)
`getLast()`	Returns last element (throws exception if empty)	O(1)
`removeFirst()`	Removes and returns first element	O(1)
`removeLast()`	Removes and returns last element	O(1)
`peekFirst()`	Returns first element (returns null if empty)	O(1)
`peekLast()`	Returns last element (returns null if empty)	O(1)
`pollFirst()`	Removes and returns first element (null if empty)	O(1)
`pollLast()`	Removes and returns last element (null if empty)	O(1)

Queue Methods

Method	Description	Throws Exception	Returns Special Value
Insert	`add(e)`	`offer(e)`	Returns false
Remove	`remove()`	`poll()`	Returns null
Examine	`element()`	`peek()`	Returns null

Stack Methods

Method	Stack Operation	Description
`push(E element)`	Push	Adds element to front
`pop()`	Pop	Removes and returns first element
`peek()`	Peek	Returns first element without removing

Advanced Examples and Patterns 💻

Example 1: Basic Operations

import java.util.LinkedList;

public class LinkedListBasics {
    public static void main(String[] args) {
        // 1. Creation and Basic Additions
        LinkedList<String> cars = new LinkedList<>();
        cars.add("Toyota");
        cars.add("Honda");
        System.out.println("Initial List: " + cars); 
        // Output: [Toyota, Honda]

        // 2. Using Deque methods (add to front and back)
        cars.addFirst("BMW"); 
        cars.addLast("Audi");
        System.out.println("After addFirst/addLast: " + cars); 
        // Output: [BMW, Toyota, Honda, Audi]

        // 3. Removing elements
        cars.removeFirst(); // Removes BMW
        cars.removeLast();  // Removes Audi
        System.out.println("After removing ends: " + cars); 
        // Output: [Toyota, Honda]
        
        // 4. Checking existence and size
        boolean containsHonda = cars.contains("Honda");
        System.out.println("Contains Honda? " + containsHonda); 
        // Output: true
        System.out.println("Total elements: " + cars.size());  
        // Output: 2
    }
}

Example 2: Using LinkedList as a Queue

import java.util.LinkedList;
import java.util.Queue;

public class QueueExample {
    public static void main(String[] args) {
        Queue<String> taskQueue = new LinkedList<>();
        
        // Enqueue operations
        taskQueue.offer("Task 1");
        taskQueue.offer("Task 2");
        taskQueue.offer("Task 3");
        
        System.out.println("Queue: " + taskQueue);
        // Output: [Task 1, Task 2, Task 3]
        
        // Peek at head without removing
        System.out.println("Next task: " + taskQueue.peek());
        // Output: Task 1
        
        // Dequeue operations
        while (!taskQueue.isEmpty()) {
            String task = taskQueue.poll();
            System.out.println("Processing: " + task);
        }
        // Output:
        // Processing: Task 1
        // Processing: Task 2
        // Processing: Task 3
    }
}

Example 3: Using LinkedList as a Stack

import java.util.LinkedList;

public class StackExample {
    public static void main(String[] args) {
        LinkedList<String> browserHistory = new LinkedList<>();
        
        // Push operations (visiting pages)
        browserHistory.push("google.com");
        browserHistory.push("github.com");
        browserHistory.push("stackoverflow.com");
        
        System.out.println("History Stack: " + browserHistory);
        // Output: [stackoverflow.com, github.com, google.com]
        
        // Peek at current page
        System.out.println("Current Page: " + browserHistory.peek());
        // Output: stackoverflow.com
        
        // Pop operations (going back)
        System.out.println("Going back from: " + browserHistory.pop());
        System.out.println("Now at: " + browserHistory.peek());
        // Output: 
        // Going back from: stackoverflow.com
        // Now at: github.com
    }
}

Example 4: Iterator and Enhanced For Loop

import java.util.LinkedList;
import java.util.Iterator;
import java.util.ListIterator;

public class IteratorExample {
    public static void main(String[] args) {
        LinkedList<Integer> numbers = new LinkedList<>();
        numbers.add(10);
        numbers.add(20);
        numbers.add(30);
        
        // 1. Enhanced for loop
        System.out.println("Using enhanced for loop:");
        for (Integer num : numbers) {
            System.out.print(num + " ");
        }
        System.out.println();
        
        // 2. Iterator (forward traversal)
        System.out.println("\nUsing Iterator:");
        Iterator<Integer> iterator = numbers.iterator();
        while (iterator.hasNext()) {
            System.out.print(iterator.next() + " ");
        }
        System.out.println();
        
        // 3. ListIterator (bidirectional traversal)
        System.out.println("\nUsing ListIterator (backward):");
        ListIterator<Integer> listIterator = 
            numbers.listIterator(numbers.size());
        while (listIterator.hasPrevious()) {
            System.out.print(listIterator.previous() + " ");
        }
        System.out.println();
        
        // 4. Descendingiterator
        System.out.println("\nUsing descendingIterator:");
        Iterator<Integer> descIterator = numbers.descendingIterator();
        while (descIterator.hasNext()) {
            System.out.print(descIterator.next() + " ");
        }
    }
}

Example 5: Implementing an LRU Cache

import java.util.LinkedList;
import java.util.HashMap;
import java.util.Map;

class LRUCache<K, V> {
    private final int capacity;
    private final LinkedList<K> accessOrder;
    private final Map<K, V> cache;
    
    public LRUCache(int capacity) {
        this.capacity = capacity;
        this.accessOrder = new LinkedList<>();
        this.cache = new HashMap<>();
    }
    
    public V get(K key) {
        if (!cache.containsKey(key)) {
            return null;
        }
        
        // Move to front (most recently used)
        accessOrder.remove(key);
        accessOrder.addFirst(key);
        
        return cache.get(key);
    }
    
    public void put(K key, V value) {
        // If key exists, remove it from order list
        if (cache.containsKey(key)) {
            accessOrder.remove(key);
        } else if (cache.size() >= capacity) {
            // Evict least recently used
            K lruKey = accessOrder.removeLast();
            cache.remove(lruKey);
        }
        
        // Add new entry
        cache.put(key, value);
        accessOrder.addFirst(key);
    }
    
    public void display() {
        System.out.println("Cache (MRU to LRU): " + accessOrder);
    }
}

public class LRUCacheDemo {
    public static void main(String[] args) {
        LRUCache<String, Integer> cache = new LRUCache<>(3);
        
        cache.put("A", 1);
        cache.put("B", 2);
        cache.put("C", 3);
        cache.display(); // [C, B, A]
        
        cache.get("A"); // Access A
        cache.display(); // [A, C, B]
        
        cache.put("D", 4); // Evicts B
        cache.display(); // [D, A, C]
    }
}

Example 6: Concurrent Access (Thread-Safe LinkedList)

import java.util.LinkedList;
import java.util.List;
import java.util.Collections;

public class SynchronizedListExample {
    public static void main(String[] args) {
        // Create a synchronized LinkedList
        List<String> syncList = Collections.synchronizedList(
            new LinkedList<>()
        );
        
        // Multiple threads can safely modify this list
        Thread thread1 = new Thread(() -> {
            for (int i = 0; i < 100; i++) {
                syncList.add("Thread1-" + i);
            }
        });
        
        Thread thread2 = new Thread(() -> {
            for (int i = 0; i < 100; i++) {
                syncList.add("Thread2-" + i);
            }
        });
        
        thread1.start();
        thread2.start();
        
        try {
            thread1.join();
            thread2.join();
        } catch (InterruptedException e) {
            e.printStackTrace();
        }
        
        System.out.println("Total elements: " + syncList.size());
        
        // IMPORTANT: When iterating, you still need manual synchronization
        synchronized(syncList) {
            for (String item : syncList) {
                System.out.println(item);
            }
        }
    }
}

Common Pitfalls and Best Practices ⚠️

Pitfalls to Avoid

Using get(index) in loops

   // ❌ BAD: O(n²) complexity
   for (int i = 0; i < list.size(); i++) {
       System.out.println(list.get(i));
   }
   
   // ✅ GOOD: O(n) complexity
   for (String item : list) {
       System.out.println(item);
   }

Not handling ConcurrentModificationException

   // ❌ BAD: Causes ConcurrentModificationException
   for (String item : list) {
       if (item.equals("remove")) {
           list.remove(item); // Don't modify during iteration
       }
   }
   
   // ✅ GOOD: Use Iterator.remove()
   Iterator<String> it = list.iterator();
   while (it.hasNext()) {
       if (it.next().equals("remove")) {
           it.remove();
       }
   }

Choosing LinkedList when ArrayList would be better

   // ❌ BAD: Mostly random access operations
   LinkedList<String> list = new LinkedList<>();
   // ... many get(index) calls
   
   // ✅ GOOD: Use ArrayList for random access
   ArrayList<String> list = new ArrayList<>();

Best Practices

Use Deque interface when using as queue/stack

Deque<String> stack = new LinkedList<>(); // More flexible

Prefer Iterator over indexed access

for (String item : list) { /* ... */ }

Consider ArrayDeque for queue/stack operations

// ArrayDeque is often faster than LinkedList for queue operations
Deque<String> deque = new ArrayDeque<>();

Initialize with capacity estimate when possible

// Note: LinkedList doesn't have capacity constructor,
// but you can use addAll() for bulk initialization
LinkedList<String> list = new LinkedList<>(existingCollection);

LinkedList vs ArrayList: Decision Matrix 🤔

Scenario	Recommended Choice
Frequent insertions/deletions at ends	LinkedList
Frequent random access by index	ArrayList
Memory is limited	ArrayList
Implementing Queue or Stack	LinkedList or ArrayDeque
Unknown size with frequent adds	ArrayList
Maintaining insertion order with bidirectional traversal	LinkedList
Need fast search operations	ArrayList (better cache locality)

Conclusion 🎯

LinkedList is a specialized data structure that excels in specific scenarios:

✅ Use LinkedList when:

You need frequent insertions/deletions at both ends
You’re implementing queues, stacks, or deques
You need bidirectional traversal
Index-based access is rare

❌ Avoid LinkedList when:

You need frequent random access
Memory overhead is a concern
Your collection is small (< 100 elements)
You mostly append and iterate

Understanding these trade-offs will help you make informed decisions and write more efficient Java code!

@ankurm

The Java LinkedList Class: A Comprehensive Guide

What is a Doubly-Linked List?

Internal Structure Visualization

Hierarchy

Key Features of `LinkedList` 🌟

Performance and Use Cases 🚀

Performance Comparison

When to Use `LinkedList`

When NOT to Use `LinkedList`

Comprehensive Method Reference 📝

Core List Methods

Deque-Specific Methods (Head/Tail Operations)

Queue Methods

Stack Methods

Advanced Examples and Patterns 💻

Example 1: Basic Operations

Example 2: Using LinkedList as a Queue

Example 3: Using LinkedList as a Stack

Example 4: Iterator and Enhanced For Loop

Example 5: Implementing an LRU Cache

Example 6: Concurrent Access (Thread-Safe LinkedList)

Common Pitfalls and Best Practices ⚠️

Pitfalls to Avoid

Best Practices

LinkedList vs ArrayList: Decision Matrix 🤔

Conclusion 🎯

Related

Leave a ReplyCancel reply

{developer} > Java > PHP > WordPress > HTML-CSS-JS

What is a Doubly-Linked List?

Internal Structure Visualization

Hierarchy

Key Features of LinkedList 🌟

Performance and Use Cases 🚀

Performance Comparison

When to Use LinkedList

When NOT to Use LinkedList

Comprehensive Method Reference 📝

Core List Methods

Deque-Specific Methods (Head/Tail Operations)

Queue Methods

Stack Methods

Advanced Examples and Patterns 💻

Example 1: Basic Operations

Example 2: Using LinkedList as a Queue

Example 3: Using LinkedList as a Stack

Example 4: Iterator and Enhanced For Loop

Example 5: Implementing an LRU Cache

Example 6: Concurrent Access (Thread-Safe LinkedList)

Common Pitfalls and Best Practices ⚠️

Pitfalls to Avoid

Best Practices

LinkedList vs ArrayList: Decision Matrix 🤔

Conclusion 🎯

Related

Leave a ReplyCancel reply

{developer} > Java > PHP > WordPress > HTML-CSS-JS

Key Features of `LinkedList` 🌟

When to Use `LinkedList`

When NOT to Use `LinkedList`