The java.util.LinkedList class is a doubly-linked list implementation of the List and Deque interfaces. It stores each element as a Node, where each node contains the data and two pointers: one to the previous node and one to the next node in the sequence.
In an ArrayList, elements are neighbors in memory. In a LinkedList, elements can be scattered anywhere in the RAM. They stay connected because each element "knows" who its neighbors are.
class Node<E> {
E item;
Node<E> next;
Node<E> prev;
}
Choosing between these two is the most common decision a Java developer makes. It comes down to Access vs. Modification.
| Feature | ArrayList | LinkedList |
|---|---|---|
| Internal Storage | Resizable Array | Doubly Linked List |
| Random Access | $O(1)$ - Instant | $O(n)$ - Must walk the chain |
| Insertion/Deletion | $O(n)$ - Needs shifting | $O(1)$ - Just update pointers |
| Memory Overhead | Low (just data) | High (data + 2 pointers per node) |
One unique feature of the LinkedList class is that it implements both the List and the Deque (Double-Ended Queue) interfaces. This means it can behave as a standard list, a Stack (LIFO), or a Queue (FIFO).
add(), get(), remove()offer(), poll(), peek()push(), pop()If you ask a LinkedList for list.get(500), it cannot jump to that memory location. It must start at the Head (index 0) and follow the next pointers 500 times. Or, if the index is closer to the end, it starts at the Tail and follows prev pointers backward. Either way, it is a linear scan.
LinkedLists are perfect for "Undo" functionality where you frequently add to the beginning and remove from the end to maintain a specific history size.
Because every single element in a LinkedList is wrapped in a Node object, a LinkedList uses significantly more memory than an ArrayList. On a 64-bit JVM, each Node object can take up 24-32 bytes of overhead *plus* the actual data. If you are storing millions of small objects (like Integers), the memory waste can be massive.
Warning: Never use a standard for loop with list.get(i) to iterate through a LinkedList.
for(int i=0; i < list.size(); i++) { list.get(i); }
This results in $O(n^2)$ complexity because for every index i, the list walks the chain from the start. Always use an Iterator or Enhanced For-Loop, which moves from node to node in $O(n)$.
Q: When is LinkedList actually faster than ArrayList?
A: When you are constantly adding or removing elements from the beginning of the list. ArrayList has to shift the entire array ($O(n)$), while LinkedList just updates the Head pointer ($O(1)$).
Q: Does Java use a Singly or Doubly LinkedList?
A: Doubly. Each node has pointers to both its predecessor and successor, which allows for bidirectional traversal.
Q: What happens if you call list.get(-1) or an index out of bounds?
A: Like ArrayList, it throws an IndexOutOfBoundsException. The internal logic checks if (index >= 0 && index < size) before attempting to walk the chain.
The LinkedList is a specialized tool. In modern hardware, the cache-locality of ArrayList often makes it faster even for some insertions. However, when your logic requires a Queue, a Stack, or constant Head-modifications, the LinkedList is your best friend. Understand the "Node" philosophy, and you'll know exactly when to chain your data instead of packing it into an array.