How to Implement Doubly Linked List in Python: Simple Guide

To implement a doubly linked list in Python, create a Node class with data, prev, and next attributes, then build a DoublyLinkedList class to manage nodes by linking them forward and backward. This allows traversal in both directions and easy insertion or deletion of nodes.

Syntax

A doubly linked list uses two classes: Node and DoublyLinkedList.

• Node holds the data and links to the previous and next nodes.
• DoublyLinkedList manages the list, including adding and removing nodes.

Each Node has three parts: data (the value), prev (link to previous node), and next (link to next node).

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
        last = self.head
        while last.next:
            last = last.next
        last.next = new_node
        new_node.prev = last

Example

This example shows how to create a doubly linked list, add nodes, and print the list forward and backward.

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
        last = self.head
        while last.next:
            last = last.next
        last.next = new_node
        new_node.prev = last

    def print_forward(self):
        current = self.head
        while current:
            print(current.data, end=' ')
            last = current
            current = current.next
        print()
        return last  # Return last node for backward printing

    def print_backward(self, tail):
        current = tail
        while current:
            print(current.data, end=' ')
            current = current.prev
        print()

# Usage
dll = DoublyLinkedList()
dll.append(10)
dll.append(20)
dll.append(30)

print('Forward:')
tail = dll.print_forward()
print('Backward:')
dll.print_backward(tail)

Output

Forward:
10 20 30 
Backward:
30 20 10 

Common Pitfalls

Common mistakes when implementing doubly linked lists include:

• Not updating the prev pointer when adding or removing nodes, which breaks backward traversal.
• Forgetting to handle the empty list case when appending or deleting nodes.
• Not updating the head when removing the first node.

Always carefully update both next and prev pointers to keep the list consistent.

python

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

    # Wrong: Does not update prev pointer
    def append_wrong(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
        # Missing: new_node.prev = last

    # Correct: Updates prev pointer
    def append_right(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

Quick Reference

Remember these key points when working with doubly linked lists:

• Node: Holds data, prev, and next.
• Append: Add new node at the end, update prev and next links.
• Traversal: Forward uses next, backward uses prev.
• Edge cases: Handle empty list and single-node list carefully.

Key Takeaways

A doubly linked list node stores data and links to both previous and next nodes.

Always update both prev and next pointers when adding or removing nodes.

Handle empty and single-node lists carefully to avoid errors.

Use forward and backward traversal to navigate the list in both directions.

Test your list operations to ensure links remain consistent.