Insert at End of Doubly Linked List in DSA Python

Mental Model

A doubly linked list has nodes connected forward and backward. To add a new node at the end, we link it after the last node and update pointers.

Analogy: Imagine a train where each carriage is connected to the one before and after. Adding a new carriage at the end means hooking it to the last carriage and making sure both know about each other.

head -> [1] ↔ [2] ↔ [3] -> null
null ← [1] ↔ [2] ↔ [3] ← tail

Dry Run Walkthrough

Input: list: 1 ↔ 2 ↔ 3, insert value 4 at end

Goal: Add a new node with value 4 at the end of the doubly linked list

Step 1: Create new node with value 4

head -> [1] ↔ [2] ↔ [3] -> null, new_node=[4] (isolated)

Why: We need a new node ready to insert

Step 2: Traverse from head to last node (3)

head -> [1] ↔ [2] ↔ [3 ↑] -> null, new_node=[4]

Why: We must find the last node to link new node after it

Step 3: Set last node's next pointer to new node

head -> [1] ↔ [2] ↔ [3] -> [4], new_node=[4]

Why: Link last node forward to new node

Step 4: Set new node's previous pointer to last node

head -> [1] ↔ [2] ↔ [3] ↔ [4] -> null

Why: Link new node backward to last node

Result:

head -> [1] ↔ [2] ↔ [3] ↔ [4] -> null

Annotated Code

DSA Python

class Node:
    def __init__(self, data):
        self.data = data
        self.prev = None
        self.next = None

class DoublyLinkedList:
    def __init__(self):
        self.head = None

    def insert_at_end(self, data):
        new_node = Node(data)  # create new node
        if self.head is None:  # empty list case
            self.head = new_node
            return
        curr = self.head
        while curr.next:  # traverse to last node
            curr = curr.next
        curr.next = new_node  # link last node to new node
        new_node.prev = curr  # link new node back to last node

    def __str__(self):
        nodes = []
        curr = self.head
        while curr:
            nodes.append(str(curr.data))
            curr = curr.next
        return ' ↔ '.join(nodes) + ' -> null'

# Driver code
dll = DoublyLinkedList()
dll.insert_at_end(1)
dll.insert_at_end(2)
dll.insert_at_end(3)
dll.insert_at_end(4)
print(dll)

new_node = Node(data) # create new node

create the new node to insert

if self.head is None: # empty list case

handle empty list by setting head to new node

while curr.next: # traverse to last node

move curr forward until last node

curr.next = new_node # link last node to new node

connect last node's next to new node

new_node.prev = curr # link new node back to last node

connect new node's prev to last node

Output

1 ↔ 2 ↔ 3 ↔ 4 -> null

Complexity Analysis

Time: O(n) because we traverse the list from head to the last node once

Space: O(1) because we only create one new node and use a few pointers

vs Alternative: Compared to inserting at the beginning (O(1)), inserting at end requires traversal, so it is slower for long lists

Edge Cases

empty list

new node becomes the head of the list

DSA Python

if self.head is None:  # empty list case

single element list

new node is linked after the only node, both nodes point to each other correctly

DSA Python

while curr.next:  # traverse to last node

When to Use This Pattern

When you need to add an element at the end of a doubly linked list, use the insert at end pattern to update both next and prev pointers correctly.

Common Mistakes

Mistake: Forgetting to update the new node's prev pointer to the last node
Fix: Always set new_node.prev = curr after linking curr.next = new_node

Mistake: Not handling the empty list case, causing errors when head is None
Fix: Check if head is None and set head to new node before traversal

Summary

Adds a new node at the end of a doubly linked list by updating next and prev pointers.

Use when you want to append data to the end of a doubly linked list.

Remember to link both directions: last node's next to new node and new node's prev to last node.