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

Concept Flow - Insert at Beginning of Doubly Linked List

Create new node

↓

Set new_node.next = head

↓

If head != null

↓

Set head.prev = new_node

↓

Set head = new_node

↓

Done

Insert a new node at the start by linking it before the current head and updating pointers.

Execution Sample

DSA Python

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

def insert_at_beginning(head, data):
    new_node = Node(data)
    new_node.next = head
    if head:
        head.prev = new_node
    head = new_node
    return head

This code inserts a new node with given data at the beginning of a doubly linked list.

Execution Table

Step	Operation	Nodes in List	Pointer Changes	Visual State
1	Start with list: 10 <-> 20 <-> 30	10, 20, 30	head → Node(10)	┌────────┐ ┌────────┐ ┌────────┐ │ data:10│ │ data:20│ │ data:30│ │ prev:∅ │←── │ prev:10│←── │ prev:20│ │ next:20│──→ │ next:30│──→ │ next:∅ │ └────────┘ └────────┘ └────────┘ head
2	Create new node with data=5	5 (new), 10, 20, 30	new_node created with data=5	new_node: ┌────────┐ │ data:5 │ │ prev:∅ │ │ next:∅ │ └────────┘
3	Set new_node.next = head (Node 10)	5, 10, 20, 30	new_node.next → Node(10)	new_node: ┌────────┐ ┌────────┐ ┌────────┐ ┌────────┐ │ data:5 │ │ data:10│ │ data:20│ │ data:30│ │ prev:∅ │ │ prev:∅ │←── │ prev:10│←── │ prev:20│ │ next:10│──→ │ next:20│──→ │ next:30│──→ │ next:∅ │ └────────┘ └────────┘ └────────┘ └────────┘ new_node head
4	Since head != null, set head.prev = new_node	5, 10, 20, 30	Node(10).prev → new_node	┌────────┐ ┌────────┐ ┌────────┐ ┌────────┐ │ data:5 │ │ data:10│ │ data:20│ │ data:30│ │ prev:∅ │←── │ prev:5 │←── │ prev:10│←── │ prev:20│ │ next:10│──→ │ next:20│──→ │ next:30│──→ │ next:∅ │ └────────┘ └────────┘ └────────┘ └────────┘ new_node head
5	Set head = new_node	5, 10, 20, 30	head → new_node	┌────────┐ ┌────────┐ ┌────────┐ ┌────────┐ │ data:5 │ │ data:10│ │ data:20│ │ data:30│ │ prev:∅ │←── │ prev:5 │←── │ prev:10│←── │ prev:20│ │ next:10│──→ │ next:20│──→ │ next:30│──→ │ next:∅ │ └────────┘ └────────┘ └────────┘ └────────┘ head
6	Return new head	5, 10, 20, 30	head points to new_node	Final list: 5 <-> 10 <-> 20 <-> 30

💡 Insertion complete, new node is now the head of the list.

Variable Tracker

Variable	Start	After Step 2	After Step 3	After Step 4	After Step 5	Final
head	Node(10)	Node(10)	Node(10)	Node(10)	Node(5)	Node(5)
new_node	None	Node(5)	Node(5)	Node(5)	Node(5)	Node(5)
new_node.next	None	None	Node(10)	Node(10)	Node(10)	Node(10)
head.prev	None	None	None	Node(5)	None	None

Key Moments - 3 Insights

Why do we set new_node.next = head before changing head?

Because we need to link the new node to the current first node before updating head, as shown in step 3 of the execution_table.

Why do we check if head is not null before setting head.prev?

If the list is empty (head is null), there is no node to update prev pointer for. This is shown in step 4 where we only update head.prev if head exists.

What happens to the old head's prev pointer after insertion?

It points back to the new node, maintaining the doubly linked structure, as seen in step 4 where Node(10).prev is set to new_node.

Visual Quiz - 3 Questions

Look at the execution_table at step 3, what does new_node.next point to?

A Null

B Node with data 5

C Node with data 10

D Node with data 20

💡 Hint

Check the 'Pointer Changes' and 'Visual State' columns at step 3.

At which step does the head pointer change to the new node?

A Step 2

B Step 5

C Step 4

D Step 6

💡 Hint

Look at the 'Pointer Changes' column to see when head points to new_node.

If the original list was empty (head = null), which step would be skipped?

A Step 4 (set head.prev = new_node)

B Step 5 (set head = new_node)

C Step 3 (set new_node.next = head)

D Step 6 (return head)

💡 Hint

Refer to the condition check before setting head.prev in the code and execution_table.

Concept Snapshot

Insert at Beginning of Doubly Linked List:
- Create new node
- Set new_node.next to current head
- If head exists, set head.prev to new_node
- Update head to new_node
- New node becomes the first element
- Maintains prev and next pointers correctly

Full Transcript

To insert a node at the beginning of a doubly linked list, first create a new node with the given data. Then set the new node's next pointer to the current head of the list. If the list is not empty, update the current head's prev pointer to point back to the new node. Finally, update the head pointer to the new node. This process ensures the new node is the first in the list and the doubly linked structure is maintained with correct prev and next pointers.