Adding Elements to the Beginning
You'll learn how LinkedList efficiently adds elements at the start by updating just two references.
When you add an element to the beginning of a LinkedList, Java uses an internal method called linkFirst() that performs a surgical operation on the chain of nodes. Unlike ArrayList (which would need to shift every element), LinkedList only needs to adjust a couple of pointers.
How linkFirst() Works Step-by-Step
Here's what happens when you add an element to the beginning:
- Create a new node containing your data, with
prevset tonullandnextpointing to the current head - Update the old first node's prev pointer to point back to this new node
- Update the head reference to point to the new node instead of the old first node
Think of it like inserting yourself at the front of a line: you step in front of the first person, they acknowledge you're now ahead of them, and the doorman (head reference) now recognizes you as first in line. Only three things changed—no one else in line moved!
Why This Is O(1)
No matter how many elements are already in the list (10, 1000, or 1 million), adding to the beginning takes the same fixed time. You're not touching any existing nodes except the first one. This is LinkedList's superpower compared to ArrayList, where inserting at position 0 requires shifting every element one spot over.
The tail reference doesn't change at all during this operation (unless the list was empty, but that's a special case handled separately).
Key Takeaway: The linkFirst() method makes adding to the beginning of a LinkedList extremely efficient—just create one new node and update two pointers, regardless of list size.