Course contentsShow
← Computer Science
Lesson 329 of 2,8728. Linked Data StructuresFree lesson

Inserting at the Tail

Appending a node at the end by traversing to the last node and updating its next pointer.

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

  1. Create your new node (just like inserting at the head)
  2. Check if the list is empty — if it is, the new node becomes the head
  3. Start at the head and traverse using a temporary pointer
  4. Walk to the end by following next pointers until you find a node whose next is NULL (that's the current tail)
  5. Update that node's next to point to your new node
  6. Your new node's next is already NULL (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.