Inserting at the Tail
What you'll learn: How to append a new node to the very end of a linked list.
The Core Idea
While inserting at the head is instant (you just update the head pointer), inserting at the tail requires more work. Since a linked list doesn't give you direct access to the last node, you must traverse the entire list from head to tail, then update the last node's next pointer to point to your new node.
Think of it like a train: to add a new car at the back, the conductor must walk the entire length of the train to reach the current last car, then attach the new one.
The Process
- Create your new node (just like inserting at the head)
- Check if the list is empty — if it is, the new node becomes the head
- Start at the head and traverse using a temporary pointer
- Walk to the end by following
nextpointers until you find a node whosenextisNULL(that's the current tail) - Update that node's
nextto point to your new node - Your new node's
nextis alreadyNULL(it's now the new tail)
Time Complexity
Inserting at the tail requires visiting every node in the list, so it takes O(n) time, where n is the number of nodes. This is much slower than the O(1) head insertion, but necessary unless you maintain a separate tail pointer (a future optimization).
Key Takeaway: Appending to the tail of a singly linked list requires O(n) traversal to find the last node before updating its next pointer.