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.