Why Doubly Linked List Over Singly Linked List in DSA Python - Why It Works

Concept Flow - Why Doubly Linked List Over Singly Linked List

Start with List

↓

Choose Operation

↓

Traverse Forward

↓

Access Next Node

↓

Traverse Backward

↓

Access Previous Node

↓

Perform Insert/Delete

↓

Update Pointers (next, prev)

↓

End Operation

Shows how doubly linked list allows moving forward and backward through nodes, unlike singly linked list which only moves forward.

Execution Sample

DSA Python

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

Defines a doubly linked list node with data, next pointer, and previous pointer.

Execution Table

Step	Operation	Nodes in List	Pointer Changes	Visual State
1	Create node A	A	head -> A	A(prev=None, next=None)
2	Create node B	A -> B	A.next -> B, B.prev -> A	A(prev=None, next=B) <-> B(prev=A, next=None)
3	Create node C	A -> B -> C	B.next -> C, C.prev -> B	A <-> B <-> C
4	Traverse forward from A	A -> B -> C	current = A.next (B)	Pointer at B
5	Traverse backward from C	A -> B -> C	current = C.prev (B)	Pointer at B
6	Insert node D after B	A -> B -> D -> C	B.next -> D, D.prev -> B, D.next -> C, C.prev -> D	A <-> B <-> D <-> C
7	Delete node B	A -> D -> C	A.next -> D, D.prev -> A	A <-> D <-> C
8	End	A -> D -> C	No changes	A <-> D <-> C

💡 Operations complete; doubly linked list allows forward and backward traversal and easy insert/delete.

Variable Tracker

Variable	Start	After 1	After 2	After 3	After 4	After 5	After 6	After 7	Final
head	None	A	A	A	A	A	A	A	A
A.next	None	None	B	B	B	B	B	D	D
A.prev	None	None	None	None	None	None	None	None	None
B.next	None	None	None	C	C	C	D	None	None
B.prev	None	None	A	A	A	A	A	None	None
C.next	None	None	None	None	None	None	None	None	None
C.prev	None	None	None	B	B	B	D	D	D
D.next	None	None	None	None	None	None	C	C	C
D.prev	None	None	None	None	None	B	A	A	A
current	None	None	None	None	B	B	B	B	B

Key Moments - 3 Insights

Why do we need the 'prev' pointer in a doubly linked list?

The 'prev' pointer lets us move backward through the list easily, as shown in steps 5 and 7 where traversal and deletion use it to access previous nodes.

How does insertion differ in doubly linked list compared to singly linked list?

Insertion requires updating both 'next' and 'prev' pointers for the new node and its neighbors, as seen in step 6 where node D is inserted after B by changing four pointers.

Why is deletion easier in doubly linked list?

Because each node knows its previous node, we can update pointers directly without traversing from head, as in step 7 where B is deleted by linking A and D directly.

Visual Quiz - 3 Questions

Look at the execution table, what is the visual state after step 3?

A A <-> B

B A -> B -> C

C A <-> B <-> C

D B <-> C

💡 Hint

Check the 'Visual State' column at step 3 showing all three nodes connected both ways.

At which step does the list first allow backward traversal?

A Step 5

B Step 2

C Step 4

D Step 6

💡 Hint

Look at the 'Operation' column where backward traversal is performed using 'prev' pointer.

If we remove the 'prev' pointer, which operation becomes difficult or impossible?

A Insert after a node

B Traverse backward

C Traverse forward

D Create nodes

💡 Hint

Refer to the 'Pointer Changes' and 'Visual State' columns showing backward traversal using 'prev' pointer.

Concept Snapshot

Doubly Linked List nodes have two pointers: next and prev.
Allows traversal forward and backward.
Insertion and deletion update both pointers.
Prev pointer enables easy backward moves and efficient deletions.
Singly linked list only moves forward, limiting operations.

Full Transcript

A doubly linked list is a chain of nodes where each node points to the next and previous nodes. This lets us move forward and backward through the list. When we insert or delete nodes, we update both next and prev pointers to keep the list connected. This is easier and more flexible than a singly linked list, which only points forward. For example, deleting a node in a doubly linked list doesn't require starting from the head to find the previous node. The prev pointer gives direct access. This makes doubly linked lists better for operations needing backward traversal or quick deletions.

Practice

1. Why might a doubly linked list be preferred over a singly linked list when you need to traverse the list backwards?

easy

A. Because doubly linked lists have pointers to both next and previous nodes, allowing backward traversal.

B. Because singly linked lists use less memory, making backward traversal faster.

C. Because singly linked lists have built-in backward pointers.

D. Because doubly linked lists store data twice for faster access.

Solution

1. Step 1: Understand pointer structure in doubly linked lists

   Doubly linked lists have two pointers per node: one to the next node and one to the previous node.

2. Step 2: Compare with singly linked lists

   Singly linked lists only have a pointer to the next node, so they cannot move backwards easily.

3. Final Answer:

   Because doubly linked lists have pointers to both next and previous nodes, allowing backward traversal. -> Option A

4. Quick Check:

   Backward traversal needs previous pointers = A [OK]

Hint: Backward traversal needs previous pointers, only in doubly linked lists [OK]

Common Mistakes:

• Thinking singly linked lists can traverse backwards easily
• Confusing memory usage with traversal ability
• Assuming doubly linked lists duplicate data

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

easy

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

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

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

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

Solution

1. Step 1: Identify required pointers for doubly linked list node

   A doubly linked list node must have pointers to both next and previous nodes.

2. Step 2: Check each option for correct attributes

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

3. Final Answer:

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

4. Quick Check:

   Doubly linked list node needs next and prev = A [OK]

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

Common Mistakes:

• Omitting the prev pointer
• Defining only prev without next
• Not initializing data attribute

3. What will be the output of the following code snippet that uses a doubly linked list?

class Node:
    def __init__(self, data):
        self.data = data
        self.next = None
        self.prev = 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
        last = self.head
        while last.next:
            last = last.next
        last.next = new_node
        new_node.prev = last

    def print_reverse(self):
        current = self.head
        while current.next:
            current = current.next
        result = []
        while current:
            result.append(current.data)
            current = current.prev
        print(result)

dll = DoublyLinkedList()
dll.append(1)
dll.append(2)
dll.append(3)
dll.print_reverse()

medium

A. [1, 2, 3]

B. []

C. [1, 3, 2]

D. [3, 2, 1]

Solution

1. Step 1: Append nodes 1, 2, 3 to doubly linked list

   Nodes are added at the end, so list is 1 <-> 2 <-> 3.

2. Step 2: Traverse to last node and print in reverse

   print_reverse moves to last node (3), then collects data moving backward: 3, 2, 1.

3. Final Answer:

   [3, 2, 1] -> Option D

4. Quick Check:

   Reverse traversal collects nodes backward = B [OK]

Hint: Reverse print collects data from tail to head using prev pointers [OK]

Common Mistakes:

• Confusing forward and backward traversal
• Printing in insertion order instead of reverse
• Not updating prev pointers correctly

4. The following code tries to delete the last node from a doubly linked list but causes an error. What is the mistake?

def delete_last(self):
    if not self.head:
        return
    current = self.head
    while current.next:
        current = current.next
    current.prev.next = None
    current.prev = None

medium

A. It sets current.prev to None before removing the node.

B. It tries to delete the head node instead of the last node.

C. It does not handle the case when the list has only one node.

D. It does not update the head pointer after deletion.

Solution

1. Step 1: Analyze deletion logic for last node

   The code moves to the last node, then sets previous node's next to None to remove last node.

2. Step 2: Check edge case for single-node list

   If list has only one node, current.prev is None, so current.prev.next causes error.

3. Final Answer:

   It does not handle the case when the list has only one node. -> Option C

4. Quick Check:

   Single-node list needs special handling = C [OK]

Hint: Check for single-node list before accessing prev pointers [OK]

Common Mistakes:

• Ignoring empty or single-node list edge cases
• Assuming prev always exists
• Not updating head when list becomes empty

5. You want to implement a feature that allows moving both forward and backward through a playlist of songs efficiently. Why is a doubly linked list better than a singly linked list for this, and what is a key trade-off?

hard

A. Singly linked lists are better because they have prev pointers; trade-off is more CPU usage.

B. Doubly linked lists allow easy forward and backward moves; trade-off is extra memory for prev pointers.

C. Doubly linked lists use less memory and are faster; trade-off is complex code.

D. Singly linked lists allow backward moves with less memory; trade-off is slower forward moves.

Solution

1. Step 1: Understand traversal needs for playlist

   Moving forward and backward efficiently requires pointers in both directions.

2. Step 2: Compare singly vs doubly linked lists

   Doubly linked lists have next and prev pointers, enabling easy two-way traversal; singly linked lists only have next pointers.

3. Step 3: Identify trade-off

   Extra prev pointers in doubly linked lists use more memory compared to singly linked lists.

4. Final Answer:

   Doubly linked lists allow easy forward and backward moves; trade-off is extra memory for prev pointers. -> Option B

5. Quick Check:

   Two-way traversal needs prev pointers, costs extra memory = D [OK]

Hint: Two-way moves need prev pointers; extra memory is the cost [OK]

Common Mistakes:

• Thinking singly linked lists support backward moves easily
• Ignoring memory cost of extra pointers
• Confusing speed with memory trade-offs