Java LinkedList

Discover how LinkedList uses nodes connected by links, making it perfect for frequent insertions and deletions in your Java programs.

What is LinkedList?

LinkedList is a doubly-linked list implementation in Java from the java.util package. Unlike ArrayList which uses an array internally, LinkedList stores elements as nodes where each node contains data and references to both the previous and next nodes.

Imagine a chain where each link knows about its neighbors on both sides - that's how LinkedList works!

  • Node-Based Structure: Each element is stored in a node with links to previous and next nodes
  • Fast Insertions/Deletions: Adding or removing elements at the beginning or middle is efficient
  • Doubly-Linked: Can traverse in both forward and backward directions
  • No Indexed Access: Must traverse from the beginning to reach a specific position

💡 Key Point: LinkedList is ideal when you need frequent insertions and deletions, especially at the beginning or middle of the list. For random access by index, ArrayList is faster.

Creating and Using LinkedList

Here's how to create a LinkedList and perform basic operations:

Example: LinkedList Basic Operations

import java.util.LinkedList;

public class LinkedListExample {
    public static void main(String[] args) {
        // Creating a LinkedList of Strings
        LinkedList cities = new LinkedList<>();
        
        // Adding elements at the end
        cities.add("Mumbai");
        cities.add("Delhi");
        cities.add("Bangalore");
        
        // Adding at specific positions
        cities.addFirst("Chennai");  // Add at beginning
        cities.addLast("Kolkata");   // Add at end
        cities.add(2, "Pune");       // Add at index 2
        
        // Display LinkedList
        System.out.println("Cities: " + cities);
        
        // Accessing elements
        System.out.println("First city: " + cities.getFirst());
        System.out.println("Last city: " + cities.getLast());
        System.out.println("City at index 2: " + cities.get(2));
        
        // Removing elements
        cities.removeFirst();        // Remove first
        cities.removeLast();         // Remove last
        System.out.println("After removal: " + cities);
        
        // Size
        System.out.println("Total cities: " + cities.size());
    }
}
Output: 
Cities: [Chennai, Mumbai, Pune, Delhi, Bangalore, Kolkata]
First city: Chennai
Last city: Kolkata
City at index 2: Pune
After removal: [Mumbai, Pune, Delhi, Bangalore]
Total cities: 4

Explanation:

  • LinkedList<String> - Creates a LinkedList that stores String objects
  • addFirst() / addLast() - Adds elements at the beginning or end efficiently
  • add(index, element) - Inserts element at specified position
  • getFirst() / getLast() - Quick access to first/last elements
  • removeFirst() / removeLast() - Fast removal from ends
  • get(index) - Access by index (slower than ArrayList for this)

LinkedList Special Methods

1. Queue Operations

LinkedList implements the Queue interface, making it perfect for queue-like behavior (FIFO - First In First Out).

Methods: offer(), poll(), peek(), element()

2. Deque Operations

LinkedList implements Deque (Double-Ended Queue), allowing insertion and removal from both ends.

Methods: offerFirst(), offerLast(), pollFirst(), pollLast()

3. Stack Operations

Can be used as a stack with Last In First Out (LIFO) behavior.

Methods: push(), pop(), peek()

4. List Operations

Standard list operations similar to ArrayList for general-purpose use.

Methods: add(), remove(), get(), set(), size(), clear()

LinkedList as Queue and Stack

LinkedList's versatility allows it to function as both a Queue and a Stack:

Example: Queue and Stack Operations

import java.util.LinkedList;

public class QueueStackExample {
    public static void main(String[] args) {
        
        // Using LinkedList as a Queue (FIFO)
        System.out.println("=== Queue Operations ===");
        LinkedList queue = new LinkedList<>();
        
        queue.offer("First");    // Add to queue
        queue.offer("Second");
        queue.offer("Third");
        System.out.println("Queue: " + queue);
        
        System.out.println("Poll: " + queue.poll());  // Remove from front
        System.out.println("Peek: " + queue.peek());  // View front
        System.out.println("Queue now: " + queue);
        
        // Using LinkedList as a Stack (LIFO)
        System.out.println("\n=== Stack Operations ===");
        LinkedList stack = new LinkedList<>();
        
        stack.push("Bottom");    // Push to stack
        stack.push("Middle");
        stack.push("Top");
        System.out.println("Stack: " + stack);
        
        System.out.println("Pop: " + stack.pop());    // Remove from top
        System.out.println("Peek: " + stack.peek());  // View top
        System.out.println("Stack now: " + stack);
    }
}
Output: 
=== Queue Operations ===
Queue: [First, Second, Third]
Poll: First
Peek: Second
Queue now: [Second, Third]

=== Stack Operations ===
Stack: [Top, Middle, Bottom]
Pop: Top
Peek: Middle
Stack now: [Middle, Bottom]

Explanation:

  • Queue (FIFO): Use offer() to add and poll() to remove from the front
  • Stack (LIFO): Use push() to add and pop() to remove from the top
  • peek() - Views the next element without removing it (works for both)

ArrayList vs LinkedList

Choosing between ArrayList and LinkedList depends on your specific use case:

Performance Comparison

Operation           ArrayList         LinkedList
──────────────────────────────────────────────────────────
Access by index     Fast O(1)         Slow O(n)
Add at end          Fast O(1)         Fast O(1)
Add at beginning    Slow O(n)         Fast O(1)
Add in middle       Slow O(n)         Fast O(1)*
Remove at end       Fast O(1)         Fast O(1)
Remove at beginning Slow O(n)         Fast O(1)
Remove in middle    Slow O(n)         Fast O(1)*
Memory usage        Less overhead     More overhead

* After reaching the position

🎯 Quick Decision Guide:
Use ArrayList: When you need fast random access and mostly add/remove at the end
Use LinkedList: When you frequently insert/delete at the beginning or middle, or need queue/stack behavior

Practical Example: Task Manager

Here's a real-world example showing LinkedList's strength in managing a task queue:

Example: Task Queue Management

import java.util.LinkedList;

public class TaskManager {
    public static void main(String[] args) {
        LinkedList taskQueue = new LinkedList<>();
        
        // Adding tasks to the queue
        taskQueue.add("Complete homework");
        taskQueue.add("Study for exam");
        taskQueue.add("Clean room");
        
        // Urgent task - add at front
        taskQueue.addFirst("Attend meeting");
        
        // Low priority - add at end
        taskQueue.addLast("Watch movie");
        
        System.out.println("Task Queue: " + taskQueue);
        System.out.println("Total tasks: " + taskQueue.size());
        
        // Process tasks one by one
        System.out.println("\nProcessing tasks...");
        while (!taskQueue.isEmpty()) {
            String currentTask = taskQueue.removeFirst();
            System.out.println("✓ Completed: " + currentTask);
            System.out.println("  Remaining: " + taskQueue.size());
        }
        
        System.out.println("\nAll tasks completed!");
    }
}
Output: 
Task Queue: [Attend meeting, Complete homework, Study for exam, Clean room, Watch movie]
Total tasks: 5

Processing tasks...
✓ Completed: Attend meeting
  Remaining: 4
✓ Completed: Complete homework
  Remaining: 3
✓ Completed: Study for exam
  Remaining: 2
✓ Completed: Clean room
  Remaining: 1
✓ Completed: Watch movie
  Remaining: 0

All tasks completed!

Explanation:

  • LinkedList efficiently handles adding urgent tasks at the beginning
  • isEmpty() checks if there are any tasks remaining
  • removeFirst() processes tasks in order (FIFO queue behavior)
  • Perfect for scenarios where priority can change and tasks need reordering