Doubly linked list in Data Structures Theory - Step-by-Step Execution

Concept Flow - Doubly linked list

Create new node

↓

Set new_node.prev to current tail

↓

Set current tail.next to new_node

↓

Update tail pointer to new_node

↓

If list empty, set head to new_node

↓

Done - node added at end

This flow shows how a new node is added at the end of a doubly linked list by updating pointers forward and backward.

Execution Sample

Data Structures Theory

1. Create node A (value=10)
2. Create node B (value=20)
3. Link A <-> B
4. Add node C (value=30) at end
5. Link B <-> C

This example adds three nodes to a doubly linked list, linking them forward and backward.

Analysis Table

Step	Operation	Nodes in List	Pointer Changes	Visual State
1	Create node A	A	head = A, tail = A	A(prev=None, next=None)
2	Create node B	A, B	B.prev = None, B.next = None	A(prev=None, next=None), B(prev=None, next=None)
3	Link A <-> B	A <-> B	A.next = B, B.prev = A, tail = B	A(prev=None, next=B) <-> B(prev=A, next=None)
4	Create node C	A <-> B, C	C.prev = None, C.next = None	A(prev=None, next=B) <-> B(prev=A, next=None), C(prev=None, next=None)
5	Add C at end	A <-> B <-> C	B.next = C, C.prev = B, tail = C	A(prev=None, next=B) <-> B(prev=A, next=C) <-> C(prev=B, next=None)
6	End	A <-> B <-> C	No changes	Final list with head=A and tail=C

💡 All nodes linked correctly; tail points to last node; list is doubly linked.

State Tracker

Variable	Start	After Step 1	After Step 3	After Step 5	Final
head	None	A	A	A	A
tail	None	A	B	C	C
A.prev	None	None	None	None	None
A.next	None	None	B	B	B
B.prev	None	None	A	A	A
B.next	None	None	None	C	C
C.prev	None	None	None	B	B
C.next	None	None	None	None	None

Key Insights - 3 Insights

Why do we need both prev and next pointers in a doubly linked list?

Because each node must link to both its previous and next nodes to allow traversal in both directions, as shown in steps 3 and 5 where both pointers are set.

What happens if the list is empty when adding the first node?

The head and tail both point to the new node, and its prev and next pointers are None, as shown in step 1.

Why do we update the tail pointer when adding a node at the end?

Because the tail must always point to the last node to allow efficient additions at the end, as updated in step 5.

Visual Quiz - 3 Questions

Look at the execution table at step 3. What is the value of A.next?

A B

B None

C A

D C

💡 Hint

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

At which step does the tail pointer change to node C?

A Step 1

B Step 3

C Step 5

D Step 6

💡 Hint

Look at the 'Pointer Changes' column for tail updates.

If we forget to set B.prev = A at step 3, what would happen?

A Tail pointer would be incorrect

B Traversal backward from B would fail

C Traversal forward from A would fail

D Head pointer would be None

💡 Hint

Consider the importance of the prev pointer for backward traversal.

Concept Snapshot

Doubly linked list nodes have two pointers: prev and next.
Each node links to its previous and next nodes.
Head points to first node; tail points to last node.
Adding at end updates tail and links both ways.
Allows traversal forward and backward efficiently.

Full Transcript

A doubly linked list is a chain of nodes where each node points to both its previous and next nodes. This allows moving forward and backward through the list. When adding a new node at the end, we create the node, link its prev pointer to the current tail, update the current tail's next pointer to the new node, and then update the tail pointer to the new node. If the list is empty, the new node becomes both head and tail. This structure supports efficient insertion and traversal in both directions.

Practice

1. What is a key feature of a doubly linked list compared to a singly linked list?

easy

A. It stores data in a fixed-size array

B. Nodes only link to the next node

C. Each node has links to both the previous and next nodes

D. It uses a stack structure internally

Solution

1. Step 1: Understand node links in doubly linked lists

   A doubly linked list node contains two links: one to the previous node and one to the next node.

2. Step 2: Compare with singly linked list

   A singly linked list node only has a link to the next node, not the previous one.

3. Final Answer:

   Each node has links to both the previous and next nodes -> Option C

4. Quick Check:

   Doubly linked list = two links per node [OK]

Hint: Remember: doubly means two links per node [OK]

Common Mistakes:

• Thinking nodes only link forward
• Confusing with arrays or stacks
• Assuming fixed size storage

2. Which of the following is the correct way to update links when inserting a new node newNode after a node current in a doubly linked list?

easy

A. newNode.next = current.next; newNode.prev = current; current.next.prev = newNode; current.next = newNode;

B. newNode.prev = current.next; newNode.next = current; current.prev = newNode; current.next = newNode;

C. current.next = newNode; newNode.next = current.prev; current.prev = newNode;

D. newNode.next = current.prev; newNode.prev = current.next; current.next = newNode;

Solution

1. Step 1: Set newNode's next and prev pointers

   newNode.next should point to current.next, and newNode.prev should point to current.

2. Step 2: Update surrounding nodes to link to newNode

   current.next.prev must point back to newNode, and current.next must point to newNode.

3. Final Answer:

   newNode.next = current.next; newNode.prev = current; current.next.prev = newNode; current.next = newNode; -> Option A

4. Quick Check:

   Update newNode links, then fix neighbors [OK]

Hint: Update new node links before neighbors [OK]

Common Mistakes:

• Mixing prev and next pointers
• Not updating current.next.prev
• Assigning pointers in wrong order

3. Consider the following doubly linked list nodes and code snippet:

Node1: data=10, prev=None, next=Node2
Node2: data=20, prev=Node1, next=Node3
Node3: data=30, prev=Node2, next=None

current = Node2
print(current.prev.data, current.data, current.next.data)

What will be the output?

medium

A. None 20 30

B. 30 20 10

C. 20 20 20

D. 10 20 30

Solution

1. Step 1: Identify current node and its neighbors

   current is Node2 with data 20; prev is Node1 with data 10; next is Node3 with data 30.

2. Step 2: Print data values of prev, current, and next nodes

   Output will be 10 (prev), 20 (current), 30 (next).

3. Final Answer:

   10 20 30 -> Option D

4. Quick Check:

   Prev, current, next data = 10, 20, 30 [OK]

Hint: Prev and next data surround current data [OK]

Common Mistakes:

• Confusing prev and next nodes
• Assuming None has data
• Printing node references instead of data

4. The following code attempts to delete a node current from a doubly linked list. What is the error?

current.prev.next = current.next
current.next.prev = current.prev
current = None

medium

A. It should only update current.prev.next, not current.next.prev

B. It does not handle the case when current is the head node

C. It should update current.next.next instead of current.prev.next

D. It incorrectly sets current to None instead of deleting

Solution

1. Step 1: Analyze pointer updates for deletion

   The code updates the previous node's next pointer and the next node's prev pointer to bypass current.

2. Step 2: Check edge cases for head or tail nodes

   If current is the head (no prev), current.prev is None, so current.prev.next causes an error.

3. Final Answer:

   It does not handle the case when current is the head node -> Option B

4. Quick Check:

   Deleting head needs special handling [OK]

Hint: Check for None before updating neighbors [OK]

Common Mistakes:

• Ignoring head or tail node cases
• Assuming current is always in middle
• Confusing which pointers to update

5. You want to reverse a doubly linked list by swapping the next and prev pointers of each node. Which of the following steps is correct to achieve this?

hard

A. For each node, swap its next and prev pointers, then move to the new prev node

B. For each node, swap its next and prev pointers, then move to the new next node

C. For each node, only swap next pointers and ignore prev pointers

D. For each node, set next to None and prev to head

Solution

1. Step 1: Swap next and prev pointers for each node

   Swapping next and prev reverses the direction of links.

2. Step 2: Move to the new prev node after swapping

   After swapping, the original next is now prev, so move to node.prev to continue.

3. Final Answer:

   For each node, swap its next and prev pointers, then move to the new prev node -> Option A

4. Quick Check:

   Swap links, then follow new prev to reverse [OK]

Hint: After swapping, move to node.prev to continue [OK]

Common Mistakes:

• Moving to node.next after swapping
• Swapping only one pointer
• Setting pointers to None incorrectly