Java LinkedList

Doubly-linked list implementation for efficient insertions and deletions

🔗 What is LinkedList?

LinkedList is a doubly-linked list implementation that excels at frequent insertions and deletions but slower for random access compared to ArrayList. 


// Creating and using LinkedList
import java.util.LinkedList;

LinkedList<String> queue = new LinkedList<>();
queue.addFirst("First");    // Add at beginning
queue.addLast("Last");      // Add at end
queue.add(1, "Middle");     // Add at specific position
System.out.println(queue);

Output:

[First, Middle, Last]

LinkedList Advantages

⚡

Fast Insertion

O(1) time for add/remove at ends 

list.addFirst("item");
list.addLast("item");
🔄

Implements Queue

Perfect for queue and deque operations 

list.offer("item");
list.poll();
💾

No Capacity Limit

Grows without array resizing 

// No capacity concerns
list.add("unlimited");
🎯

Bidirectional

Can traverse in both directions 

list.descendingIterator();

🔹 LinkedList Specific Methods

Methods unique to LinkedList for efficient operations: 

import java.util.*;

public class LinkedListMethods {
    public static void main(String[] args) {
        LinkedList<String> list = new LinkedList<>();
        
        // Adding at specific positions
        list.addFirst("Start");         // Add at beginning
        list.addLast("End");           // Add at end
        list.add("Middle");            // Add at end (same as addLast)
        
        System.out.println("After adding: " + list);
        
        // Accessing first and last elements
        System.out.println("First: " + list.getFirst());
        System.out.println("Last: " + list.getLast());
        
        // Peek methods (don't remove)
        System.out.println("Peek first: " + list.peekFirst());
        System.out.println("Peek last: " + list.peekLast());
        
        // Queue operations
        list.offer("Queued");          // Add to end (queue style)
        System.out.println("After offer: " + list);
        
        String polled = list.poll();   // Remove from beginning
        System.out.println("Polled: " + polled);
        System.out.println("After poll: " + list);
        
        // Stack operations
        list.push("Pushed");           // Add to beginning (stack style)
        String popped = list.pop();    // Remove from beginning
        System.out.println("Popped: " + popped);
        System.out.println("Final: " + list);
    }
}

Output:

After adding: [Start, End, Middle]
First: Start
Last: Middle
Peek first: Start
Peek last: Middle
After offer: [Start, End, Middle, Queued]
Polled: Start
After poll: [End, Middle, Queued]
Popped: Pushed
Final: [End, Middle, Queued]

🔹 LinkedList as Queue and Stack

LinkedList implements both Queue and Deque interfaces: 

import java.util.*;

public class LinkedListAsQueueStack {
    public static void main(String[] args) {
        // Using LinkedList as Queue (FIFO - First In, First Out)
        Queue<Integer> queue = new LinkedList<>();
        queue.offer(1);    // Add to rear
        queue.offer(2);
        queue.offer(3);
        
        System.out.println("Queue: " + queue);
        System.out.println("Poll: " + queue.poll()); // Remove from front
        System.out.println("After poll: " + queue);
        
        // Using LinkedList as Stack (LIFO - Last In, First Out)
        Deque<String> stack = new LinkedList<>();
        stack.push("Bottom");   // Add to top
        stack.push("Middle");
        stack.push("Top");
        
        System.out.println("Stack: " + stack);
        System.out.println("Pop: " + stack.pop());   // Remove from top
        System.out.println("After pop: " + stack);
        
        // Using as Deque (Double-ended queue)
        Deque<Character> deque = new LinkedList<>();
        deque.addFirst('A');    // Add to front
        deque.addLast('Z');     // Add to rear
        deque.addFirst('B');    // Add to front again
        
        System.out.println("Deque: " + deque);
        System.out.println("Remove first: " + deque.removeFirst());
        System.out.println("Remove last: " + deque.removeLast());
        System.out.println("Final deque: " + deque);
    }
}

Output:

Queue: [1, 2, 3]
Poll: 1
After poll: [2, 3]
Stack: [Top, Middle, Bottom]
Pop: Top
After pop: [Middle, Bottom]
Deque: [B, A, Z]
Remove first: B
Remove last: Z
Final deque: [A]

🔹 ArrayList vs LinkedList

When to choose LinkedList over ArrayList:

Performance Comparison:

Operation ArrayList LinkedList
Access by index O(1) ✅ O(n) ❌
Add at beginning O(n) ❌ O(1) ✅
Add at end O(1) ✅ O(1) ✅
Memory usage Lower ✅ Higher ❌ 
// Choose ArrayList for:
List<String> arrayList = new ArrayList<>();
// - Frequent random access by index
// - More reading than inserting/deleting
// - Memory efficiency is important

// Choose LinkedList for:
List<String> linkedList = new LinkedList<>();
// - Frequent insertions/deletions at beginning or middle
// - Using as Queue or Stack
// - Don't need random access by index

🧠 Test Your Knowledge

Which operation is faster in LinkedList compared to ArrayList?