Insert at End of Doubly Linked List in DSA Python - Execution Trace

Concept Flow - Insert at End of Doubly Linked List

Create new node with data

↓

Is list empty? head == None

↓

Set head = new

↓

Traverse to last node

↓

Set last.next = new

↓

Set new.prev = last

↓

Done

Create a new node, check if list is empty, if yes set head to new node. Otherwise, traverse to last node, link last node's next to new node, and new node's prev to last node.

Execution Sample

DSA Python

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

def insert_end(head, data):
    new_node = Node(data)
    if head is None:
        head = new_node
        return head
    current = head
    while current.next:
        current = current.next
    current.next = new_node
    new_node.prev = current
    return head

# Example usage:
head = Node(10)
second = Node(20)
third = Node(30)
head.next = second
second.prev = head
second.next = third
third.prev = second

# Insert 40 at end
head = insert_end(head, 40)

Insert a new node with value 40 at the end of a doubly linked list starting at head.

Execution Table

Step	Operation	Nodes in List	Pointer Changes	Visual State
1	Create new node with data=40	10 <-> 20 <-> 30	new_node.prev = None, new_node.next = None	┌────────┐ ┌────────┐ ┌────────┐ │ data:10│ │ data:20│ │ data:30│ │ prev:∅ │ │ prev───┼──→ │ prev───┼──→ │ │ next───┼──→ │ next───┼──→ │ next:∅ │ └────────┘ └────────┘ └────────┘ head
2	Check if head is None	10 <-> 20 <-> 30	head is not None, proceed to traverse	Same as above
3	Traverse to last node (30)	10 <-> 20 <-> 30	current moves from 10 to 20 to 30	Same as above, pointer current at node 30
4	Set last.next = new_node	10 <-> 20 <-> 30	30.next = new_node	┌────────┐ ┌────────┐ ┌────────┐ ┌────────┐ │ data:10│ │ data:20│ │ data:30│ │ data:40│ │ prev:∅ │ │ prev───┼──→ │ prev───┼──→ │ prev:∅ │ │ next───┼──→ │ next───┼──→ │ next───┼──→ │ next:∅ │ └────────┘ └────────┘ └────────┘ └────────┘ head
5	Set new_node.prev = last node (30)	10 <-> 20 <-> 30 <-> 40	new_node.prev = 30	┌────────┐ ┌────────┐ ┌────────┐ ┌────────┐ │ data:10│ │ data:20│ │ data:30│ │ data:40│ │ prev:∅ │ │ prev───┼──→ │ prev───┼──→ │ prev───┼──→ 30 │ next───┼──→ │ next───┼──→ │ next───┼──→ │ next:∅ │ └────────┘ └────────┘ └────────┘ └────────┘ head
6	Insertion complete	10 <-> 20 <-> 30 <-> 40	Pointers stable	┌────────┐ ┌────────┐ ┌────────┐ ┌────────┐ │ data:10│ │ data:20│ │ data:30│ │ data:40│ │ prev:∅ │ │ prev───┼──→ │ prev───┼──→ │ prev───┼──→ │ next───┼──→ │ next───┼──→ │ next───┼──→ │ next:∅ │ └────────┘ └────────┘ └────────┘ └────────┘ head

💡 Insertion done after last node, new node's next is None

Variable Tracker

Variable	Start	After Step 1	After Step 3	After Step 4	After Step 5	Final
head	Node(10)	Node(10)	Node(10)	Node(10)	Node(10)	Node(10)
current	None	None	Node(30)	Node(30)	Node(30)	Node(30)
new_node	None	Node(40)	Node(40)	Node(40)	Node(40)	Node(40)

Key Moments - 3 Insights

Why do we check if head is None before inserting?

If head is None, the list is empty, so the new node becomes the head. This is shown in step 2 of the execution_table where we decide to traverse or set head.

Why do we set new_node.prev to last node?

Because in a doubly linked list, each node points back to its previous node. Step 5 shows setting new_node.prev to the last node to maintain backward links.

How do we know where the last node is?

We traverse starting from head until current.next is None, meaning current is the last node. Step 3 shows this traversal.

Visual Quiz - 3 Questions

Look at the execution_table, what is the value of 'current' after step 3?

A Node with data 20

B Node with data 30

C Node with data 40

D None

💡 Hint

Check the 'current' variable in variable_tracker after step 3

At which step is the new node's prev pointer set to the last node?

A Step 5

B Step 4

C Step 2

D Step 6

💡 Hint

Look at the Pointer Changes column in execution_table rows

If the list was empty initially, what would be the visual state after insertion?

A No nodes, head is None

B Two nodes linked together

C Single node with prev and next as None, head points to it

D New node with next pointing to head

💡 Hint

Refer to concept_flow branch when head is None

Concept Snapshot

Insert at End of Doubly Linked List:
- Create new node with data
- If list empty (head is None), set head = new node
- Else traverse to last node
- Set last.next = new node
- Set new_node.prev = last node
- New node's next = None
- List size increases by 1

Full Transcript

To insert a node at the end of a doubly linked list, first create the new node with the given data. Check if the list is empty by seeing if head is None. If empty, set head to the new node. Otherwise, start at head and move through the list until reaching the last node (where next is None). Then set the last node's next pointer to the new node, and set the new node's prev pointer back to the last node. The new node's next pointer is None, marking it as the new tail. This maintains the doubly linked structure with forward and backward links.