Doubly Linked List Structure and Node Design in DSA Python

Mental Model

A doubly linked list is a chain of nodes where each node knows both its neighbor before and after it.

Analogy: Imagine a train where each carriage has a connector to the carriage in front and the one behind, so you can move forward or backward easily.

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

Dry Run Walkthrough

Input: Create a doubly linked list with nodes 1, 2, 3 linked in order

Goal: Build the doubly linked list so each node points to the next and previous nodes correctly

Step 1: Create node 1 with prev=null and next=null

null ← [1] -> null

Why: Start with the first node which has no neighbors yet

Step 2: Create node 2 and link node 1's next to node 2, node 2's prev to node 1

null ← [1] ↔ [2] -> null

Why: Connect second node so first node points forward and second points back

Step 3: Create node 3 and link node 2's next to node 3, node 3's prev to node 2

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

Why: Connect third node so the chain extends both ways

Result:

null ← 1 ↔ 2 ↔ 3 -> 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 append(self, data):
        new_node = Node(data)
        if not self.head:
            self.head = new_node
            return
        curr = self.head
        while curr.next:
            curr = curr.next
        curr.next = new_node
        new_node.prev = curr

    def print_list(self):
        curr = self.head
        result = []
        while curr:
            result.append(str(curr.data))
            curr = curr.next
        print(" ↔ ".join(result))

# Driver code
dll = DoublyLinkedList()
dll.append(1)
dll.append(2)
dll.append(3)
dll.print_list()

new_node = Node(data)

Create a new node with given data

if not self.head: self.head = new_node return

If list empty, new node becomes head

while curr.next: curr = curr.next

Traverse to the last node

curr.next = new_node new_node.prev = curr

Link new node after last node, set backward link

while curr: result.append(str(curr.data)) curr = curr.next

Traverse from head to tail collecting data for print

Output

1 ↔ 2 ↔ 3

Complexity Analysis

Time: O(n) because appending requires traversing to the end of the list

Space: O(n) because each node stores data and two pointers

vs Alternative: Compared to singly linked list, doubly linked list uses more space but allows backward traversal

Edge Cases

Empty list

Appending first node sets head correctly

DSA Python

if not self.head:
    self.head = new_node
    return

Single node list

Appending second node links both nodes forward and backward

DSA Python

curr = self.head
while curr.next:
    curr = curr.next

When to Use This Pattern

When you need to move forward and backward through a list easily, use a doubly linked list structure.

Common Mistakes

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

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

Summary

It creates a chain of nodes where each node links to the next and previous nodes.

Use it when you want to move both forward and backward through a list easily.

Remember each node has two pointers: one to the next node and one to the previous node.

Practice

1. What is the main difference between a doubly linked list node and a singly linked list node?

easy

A. A doubly linked list node does not store any data.

B. A doubly linked list node has pointers to both the previous and next nodes.

C. A doubly linked list node can only point to the next node.

D. A doubly linked list node stores data in a different format.

Solution

1. Step 1: Understand node pointers in singly linked list

   A singly linked list node has only one pointer to the next node.

2. Step 2: Understand node pointers in doubly linked list

   A doubly linked list node has two pointers: one to the previous node and one to the next node.

3. Final Answer:

   A doubly linked list node has pointers to both the previous and next nodes. -> Option B

4. Quick Check:

   Doubly linked list nodes have two pointers = D [OK]

Hint: Remember: doubly means two pointers, singly means one [OK]

Common Mistakes:

• Thinking doubly linked list nodes store data differently
• Confusing pointer count between singly and doubly linked lists
• Assuming doubly linked list nodes have only one pointer

2. Which of the following is the correct way to define a doubly linked list node class in Python?

easy

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

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

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

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

Solution

1. Step 1: Check for data storage and pointers

   A doubly linked list node must store data and have both prev and next pointers.

2. Step 2: Verify class definitions

   class Node: def __init__(self, data): self.data = data self.prev = None self.next = None correctly defines data, prev, and next attributes in __init__.

3. Final Answer:

   class Node:\n def __init__(self, data):\n self.data = data\n self.prev = None\n self.next = None -> Option D

4. Quick Check:

   Node class with data, prev, next = B [OK]

Hint: Doubly linked nodes need both prev and next pointers [OK]

Common Mistakes:

• Omitting the prev pointer
• Not initializing data attribute
• Defining only next pointer like singly linked list

3. What will be the output of the following code snippet?

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

head = Node(1)
second = Node(2)
third = Node(3)

head.next = second
second.prev = head
second.next = third
third.prev = second

current = third
result = []
while current:
    result.append(current.data)
    current = current.prev
print(result)

medium

A. [3, 2, 1]

B. [1, 2, 3]

C. [1, 3, 2]

D. [3, 1, 2]

Solution

1. Step 1: Understand the linked list connections

   Nodes are linked as 1 <-> 2 <-> 3 with prev and next pointers set correctly.

2. Step 2: Trace the while loop starting from third node

   Starting at node with data 3, append 3, move to prev (2), append 2, move to prev (1), append 1, then prev is None, loop ends.

3. Final Answer:

   [3, 2, 1] -> Option A

4. Quick Check:

   Traverse backward from third node = [3, 2, 1] [OK]

Hint: Backward traversal collects nodes in reverse order [OK]

Common Mistakes:

• Confusing next and prev pointers during traversal
• Starting traversal from head instead of third
• Appending data in wrong order

4. Identify the error in the following doubly linked list node insertion code and select the correct fix.

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

head = Node(1)
new_node = Node(2)

# Insert new_node after head
new_node.next = head.next
head.next.prev = new_node
head.next = new_node
new_node.prev = head

medium

A. No error; code inserts node correctly.

B. new_node.prev should be assigned before head.next.

C. head.next.prev causes AttributeError; fix by checking if head.next is not None before accessing prev.

D. new_node.next should be assigned after head.next.

Solution

1. Step 1: Analyze head.next before insertion

   Initially, head.next is None, so head.next.prev causes AttributeError.

2. Step 2: Fix by checking if head.next exists before accessing prev

   Adding a condition to check if head.next is not None before setting head.next.prev avoids error.

3. Final Answer:

   head.next.prev causes AttributeError; fix by checking if head.next is not None before accessing prev. -> Option C

4. Quick Check:

   Check for None before accessing prev pointer [OK]

Hint: Always check if next node exists before accessing its prev [OK]

Common Mistakes:

• Ignoring None check causing runtime error
• Assigning pointers in wrong order
• Assuming head.next is always valid

5. You want to insert a new node with value 4 between nodes with values 2 and 3 in a doubly linked list. Given the nodes are connected as 1 <-> 2 <-> 3, which sequence of pointer updates correctly inserts the new node?

hard

A. new_node.prev = node2; new_node.next = node3; node2.next = new_node; node3.prev = new_node

B. new_node.next = node2; new_node.prev = node3; node3.next = new_node; node2.prev = new_node

C. node2.next = new_node; new_node.next = node3; node3.next = new_node; new_node.prev = node2

D. node3.prev = new_node; new_node.prev = node2; node2.next = new_node; new_node.next = node2

Solution

1. Step 1: Set new_node pointers to neighbors

   new_node.prev should point to node2 and new_node.next to node3 to link correctly.

2. Step 2: Update neighbors to point to new_node

   node2.next must point to new_node and node3.prev must point to new_node to complete insertion.

3. Final Answer:

   new_node.prev = node2; new_node.next = node3; node2.next = new_node; node3.prev = new_node -> Option A

4. Quick Check:

   Set new_node pointers then update neighbors [OK]

Hint: Link new node to neighbors, then neighbors back to new node [OK]

Common Mistakes:

• Swapping prev and next pointers
• Updating neighbors before setting new_node pointers
• Forgetting to update one neighbor pointer