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

Inserting at the Tail of a Doubly Linked List

Appending a new node at the end using the tail pointer and updating bidirectional links.

Inserting at the Tail of a Doubly Linked List

You'll learn how to add a new node at the end of a doubly linked list efficiently using the tail pointer.

When you insert at the tail of a doubly linked list, you're appending a new node to the very end. Unlike singly linked lists where you only update one "next" link, doubly linked lists require updating both forward and backward connections.

The Core Process

Think of it like adding a new caboose to a train. The current last car needs to point forward to the new caboose, and the new caboose needs to point backward to what was previously the last car.

Here's what happens step-by-step:

  1. Create the new node with your data
  2. Check if the list is empty (tail is NULL)
    • If empty: set both head and tail to the new node
  3. If not empty:
    • Set the new node's prev pointer to the current tail
    • Set the current tail's next pointer to the new node
    • Update the tail pointer to point to the new node

Why This Matters

Because you maintain a tail pointer, inserting at the end is O(1) — constant time! You don't need to traverse the entire list like you would in a singly linked list without a tail pointer. You jump straight to the end, update a few links, and you're done.

The bidirectional links mean both the old tail and new tail "know about" each other, preserving the ability to traverse backward from the end.

Key Takeaway: Inserting at the tail of a doubly linked list with a tail pointer is a constant-time O(1) operation that requires updating both the forward (next) and backward (prev) links to maintain bidirectional connectivity.