LinkedList Internals
Explore the doubly-linked node structure of LinkedList and its time complexity profile.
LinkedList Internals
Java's LinkedList is a doubly-linked list: each node holds a reference to the previous and next node, plus the element value. Unlike ArrayList, there is no backing array — memory is allocated per node.
class Node<T> {
T data;
Node<T> prev;
Node<T> next;
Node(T data) { this.data = data; }
}Time Complexity Profile
LinkedList's performance characteristics differ significantly from ArrayList:
- addFirst / addLast: O(1)
- get(index): O(n) — must traverse from head or tail
- remove(index): O(n) to find, then O(1) to unlink
- Iterator traversal: O(n)
Use LinkedList when you need frequent head/tail insertions, not random access.