Create and Initialize Doubly Linked List in DSA Python

Mental Model

A doubly linked list is a chain of nodes where each node knows the one before and the one after it.

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

null ← [head] ↔ [node2] ↔ [node3] -> null
↑
current at head

Dry Run Walkthrough

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

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

Step 1: Create first node with value 1; set head and tail to this node

null ← [1] -> null
↑head, tail

Why: We start the list with the first node; it has no previous or next yet

Step 2: Create second node with value 2; link it after first node

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

Why: Add second node by connecting it to the first node both ways

Step 3: Create third node with value 3; link it after second node

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

Why: Add third node at the end, updating tail pointer

Result:

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

Annotated Code

DSA Python

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

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

    def append(self, value):
        new_node = Node(value)
        if self.head is None:
            self.head = new_node
            self.tail = new_node
            return
        self.tail.next = new_node
        new_node.prev = self.tail
        self.tail = new_node

    def __str__(self):
        values = []
        current = self.head
        while current:
            values.append(str(current.value))
            current = current.next
        return ' ↔ '.join(values) + ' -> null'

# Driver code
list_dll = DoublyLinkedList()
list_dll.append(1)
list_dll.append(2)
list_dll.append(3)
print(list_dll)

if self.head is None:

check if list is empty to initialize head and tail

self.head = new_node self.tail = new_node

set first node as both head and tail

self.tail.next = new_node new_node.prev = self.tail

link new node after current tail both ways

self.tail = new_node

update tail pointer to new last node

Output

1 ↔ 2 ↔ 3 -> null

Complexity Analysis

Time: O(n) to create n nodes because we append each node once

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

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

Edge Cases

Empty list before any append

Head and tail are None; first append sets both to new node

DSA Python

if self.head is None:

Appending only one node

List has one node with prev and next as None

DSA Python

self.head = new_node
self.tail = new_node

When to Use This Pattern

When you need to move forward and backward through a list easily, use a doubly linked list to keep track of both neighbors.

Common Mistakes

Mistake: Not updating the new node's prev pointer when appending
Fix: Set new_node.prev = self.tail before updating tail

Mistake: Not updating tail pointer after adding new node
Fix: Assign self.tail = new_node after linking

Summary

Creates a doubly linked list where each node points to the previous and next nodes.

Use it when you want to traverse a list in both directions efficiently.

Remember to update both next and prev pointers and keep track of head and tail.

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