Why Create and Initialize Doubly Linked List in DSA Python?

The Big Idea

What if you could manage a chain of items as easily as flipping pages in a book?

The Scenario

Imagine you have a long chain of paper clips linked together. You want to add a new clip in the middle or remove one from the end. Doing this by hand means unhooking and rehooking clips carefully, which can be tricky and slow.

The Problem

Trying to manage each paper clip manually is slow and easy to mess up. You might lose track of which clip connects to which, or accidentally break the chain. This makes adding or removing clips painful and error-prone.

The Solution

A doubly linked list is like a smart chain where each clip knows both its neighbor before and after. This lets you add or remove clips anywhere quickly and safely without breaking the chain.

Before vs After

✗ Before

clips = ['clip1', 'clip2', 'clip3']
# To add 'clip4' in middle, shift clips manually
clips = clips[:2] + ['clip4'] + clips[2:]

✓ After

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

class DoublyLinkedList:
    def __init__(self):
        self.head = None
        self.tail = None

What It Enables

With a doubly linked list, you can quickly add, remove, or move items anywhere in your list without losing track or breaking connections.

Real Life Example

Think of a music playlist where you can easily skip forward or backward between songs, add new songs anywhere, or remove songs without restarting the whole list.

Key Takeaways

Manual linking is slow and error-prone.

Doubly linked lists keep track of neighbors both ways.

This makes list updates fast and safe.

Practice

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

easy

A. A doubly linked list can only be traversed forward.

B. A doubly linked list stores data in arrays instead of nodes.

C. A doubly linked list has nodes with pointers to both next and previous nodes.

D. A doubly linked list does not have a head pointer.

Solution

1. Step 1: Understand node structure in doubly linked list

   Each node in a doubly linked list contains two pointers: one to the next node and one to the previous node.

2. Step 2: Compare with singly linked list

   A singly linked list node has only one pointer to the next node, so it can only be traversed forward.

3. Final Answer:

   A doubly linked list has nodes with pointers to both next and previous nodes. -> Option C

4. Quick Check:

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

Hint: Remember: doubly linked list nodes link both ways [OK]

Common Mistakes:

• Thinking doubly linked list uses arrays
• Assuming it can only go forward
• Confusing head pointer presence

2. Which of the following is the correct way to define a node class for 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 attributes for doubly linked list node

   A doubly linked list node must have data, a pointer to the next node, and a pointer to the previous node.

2. Step 2: Check each option for completeness

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

3. Final Answer:

   class Node with data, next, and prev attributes initialized -> Option A

4. Quick Check:

   Node needs data, next, prev = A [OK]

Hint: Doubly linked list node needs both next and prev pointers [OK]

Common Mistakes:

• Omitting prev pointer
• Omitting data attribute
• Defining next and prev but missing data

3. What will be the output of the following code that creates a doubly linked list with nodes containing 1, 2, 3?

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 display_forward(self):
        current = self.head
        result = []
        while current:
            result.append(current.data)
            current = current.next
        return result

dll = DoublyLinkedList()
dll.append(1)
dll.append(2)
dll.append(3)
print(dll.display_forward())

medium

A. [3, 2, 1]

B. []

C. [1, 3, 2]

D. [1, 2, 3]

Solution

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

   Nodes are added at the end. First node 1 becomes head, then 2 is linked after 1, then 3 after 2.

2. Step 2: Display nodes forward

   Starting from head, nodes are visited in order 1 -> 2 -> 3, collected in list [1, 2, 3].

3. Final Answer:

   [1, 2, 3] -> Option D

4. Quick Check:

   Appending nodes in order shows [1, 2, 3] [OK]

Hint: Appending adds nodes at end; display forward shows insertion order [OK]

Common Mistakes:

• Confusing order of nodes
• Printing empty list if head is null
• Mixing up forward and backward traversal

4. Identify the error in the following code that tries to append nodes to 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 self.head is None:
            self.head = new_node
        else:
            last = self.head
            while last.next:
                last = last.next
            last.next = new_node
            new_node.next = last

medium

A. new_node.next should be new_node.prev to link backward

B. Missing return statement after setting head

C. The while loop condition should be last.prev instead of last.next

D. Node class is missing data attribute

Solution

1. Step 1: Analyze append method's linking logic

   After finding last node, code sets last.next = new_node correctly, but sets new_node.next = last, which is wrong.

2. Step 2: Correct backward link pointer

   Backward link should be new_node.prev = last, not new_node.next = last.

3. Final Answer:

   new_node.next should be new_node.prev to link backward -> Option A

4. Quick Check:

   Backward link uses prev pointer = D [OK]

Hint: Backward link uses prev, not next pointer [OK]

Common Mistakes:

• Setting new_node.next instead of new_node.prev
• Forgetting to link backward pointer
• Confusing next and prev pointers

5. You want to create a doubly linked list from a Python list of values [10, 20, 30] and then print the list backward starting from the last node. Which code snippet correctly initializes the doubly linked list and prints the values backward?

hard

A. dll = DoublyLinkedList()
for val in [10, 20, 30]:
dll.append(val)
current = dll.head
while current.prev:
current = current.prev
while current:
print(current.data, end=' ')
current = current.next

B. dll = DoublyLinkedList()
for val in [10, 20, 30]:
dll.append(val)
current = dll.head
while current.next:
current = current.next
while current:
print(current.data, end=' ')
current = current.prev

C. dll = DoublyLinkedList()
for val in [10, 20, 30]:
dll.append(val)
current = dll.head
while current.next:
current = current.next
while current:
print(current.data, end=' ')
current = current.next

D. dll = DoublyLinkedList()
for val in [10, 20, 30]:
dll.append(val)
current = dll.head
while current.prev:
current = current.prev
while current:
print(current.data, end=' ')
current = current.prev

Solution

1. Step 1: Append values 10, 20, 30 to doubly linked list

   Values are appended in order, head points to 10, last node is 30.

2. Step 2: Move to last node by traversing next pointers

   Start at head, move forward while current.next exists to reach last node (30).

3. Step 3: Print backward by moving prev pointers

   From last node, print data and move backward using current.prev until null.

4. Final Answer:

   Traverse forward to the last node using next pointers, then print backward using prev pointers, producing 30 20 10 -> Option B

5. Quick Check:

   Traverse next to last, then prev backward = A [OK]

Hint: Go forward to last node, then traverse backward with prev [OK]

Common Mistakes:

• Trying to move backward from head
• Using next pointer to go backward
• Not moving to last node before backward print