Java LinkedList

The LinkedList class implements both List and Deque interfaces, making it versatile for lists, stacks, and queues. It uses a doubly-linked list structure internally.

How LinkedList Works

Each element is stored in a Node that contains:

• The actual data (element)
• A reference to the previous node
• A reference to the next node

// Internal Node structure (simplified)
private static class Node<E> {
    E item;
    Node<E> next;
    Node<E> prev;
}

ArrayList vs. LinkedList

Creating a LinkedList

import java.util.LinkedList;
import java.util.List;
import java.util.Deque;

// As a List
List<String> list = new LinkedList<>();

// As a Deque (Double-ended queue)
Deque<String> deque = new LinkedList<>();

// Direct type (for LinkedList-specific methods)
LinkedList<String> linkedList = new LinkedList<>();

Deque Methods (Double-Ended Queue)

LinkedList implements Deque, providing powerful head/tail operations:

Click Run to execute your code

Using LinkedList as Stack and Queue

LinkedList<String> stack = new LinkedList<>();

// Stack operations (LIFO - Last In First Out)
stack.push("First");    // Same as addFirst()
stack.push("Second");
stack.push("Third");
String top = stack.pop();  // "Third" - removeFirst()
String peek = stack.peek(); // "Second" - peekFirst()

// Queue operations (FIFO - First In First Out)
LinkedList<String> queue = new LinkedList<>();
queue.offer("First");   // Same as addLast()
queue.offer("Second");
queue.offer("Third");
String first = queue.poll(); // "First" - pollFirst()
String next = queue.peek();  // "Second" - peekFirst()

Efficient Iteration

LinkedList<String> list = new LinkedList<>();
list.addAll(Arrays.asList("A", "B", "C", "D", "E"));

// Good: Using Iterator (O(n) total)
Iterator<String> it = list.iterator();
while (it.hasNext()) {
    System.out.println(it.next());
}

// Good: For-each loop
for (String s : list) {
    System.out.println(s);
}

// BAD: Using get(i) - O(n²) total!
// Each get(i) traverses from head
for (int i = 0; i < list.size(); i++) {
    System.out.println(list.get(i)); // Slow!
}

// Good: Descending Iterator
Iterator<String> descIt = list.descendingIterator();
while (descIt.hasNext()) {
    System.out.println(descIt.next()); // E, D, C, B, A
}

Summary