Mastering Doubly Linked Lists in Python: A Step-by-Step Approach

Introduction

Welcome to the world of data structures! Today, we’re diving into the realm of doubly linked lists. If you’ve just started your programming journey, understanding the difficulties of data structures is key to becoming a proficient coder. In this blog post, we’ll unravel the mysteries of doubly linked lists, exploring their structure, benefits, and implementation in Python.

What is a Doubly Linked List?

A doubly linked list is a type of linked list in which each node contains data and two pointers, one pointing to the next node in the sequence (as in a singly linked list), and another pointing to the previous node. This bidirectional linkage allows for more flexible traversal and manipulation of the list.

Basic Components of a Doubly Linked List

Node

Just like in a single linked list, the basic building block of a doubly linked list is the node. However, a doubly linked list node has two pointers:

• Data: The actual information stored in the node.

• Next: A reference to the next node in the sequence.

• Prev: A reference to the previous node.

Let’s represent a doubly linked list node in Python:

class Node:
    def __init__(self, data=None):
        self.data = data
        self.next_node = None
        self.prev_node = None

DoublyLinkedList

The DoublyLinkedList class serves as the container for the nodes. It contains a reference to both the first node (head) and the last node (tail), providing methods for common operations.

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

Operations on Doubly Linked Lists

1. Insertion

Inserting a new node can be done at the beginning, end, or at a specific position in the list.

Insert at the Beginning

def insert_at_beginning(self, data):
    new_node = Node(data)
    if not self.head:
        self.head = self.tail = new_node
    else:
        new_node.next_node = self.head
        self.head.prev_node = new_node
        self.head = new_node

Insert at the End

def insert_at_end(self, data):
    new_node = Node(data)
    if not self.head:
        self.head = self.tail = new_node
    else:
        new_node.prev_node = self.tail
        self.tail.next_node = new_node
        self.tail = new_node

2. Deletion

Deletion can be performed by removing a node with a specific value or at a given position.

Delete by Value

def delete_by_value(self, value):
    current_node = self.head
    while current_node:
        if current_node.data == value:
            if current_node.prev_node:
                current_node.prev_node.next_node = current_node.next_node
            else:
                self.head = current_node.next_node
            if current_node.next_node:
                current_node.next_node.prev_node = current_node.prev_node
            else:
                self.tail = current_node.prev_node
            return
        current_node = current_node.next_node

Delete at Position

def delete_at_position(self, position):
    current_node = self.head
    count = 0
    while current_node and count != position:
        current_node = current_node.next_node
        count += 1
    if current_node:
        if current_node.prev_node:
            current_node.prev_node.next_node = current_node.next_node
        else:
            self.head = current_node.next_node
        if current_node.next_node:
            current_node.next_node.prev_node = current_node.prev_node
        else:
            self.tail = current_node.prev_node

3. Traversal

def traverse_forward(self):
    current_node = self.head
    while current_node:
        print(current_node.data, end=" <-> ")
        current_node = current_node.next_node
    print("None")

def traverse_backward(self):
    current_node = self.tail
    while current_node:
        print(current_node.data, end=" <-> ")
        current_node = current_node.prev_node
    print("None")

Putting It All Together

Now, let’s demonstrate the usage of the doubly linked list with a simple example:

# Creating a doubly linked list
doubly_linked_list = DoublyLinkedList()

# Inserting elements
doubly_linked_list.insert_at_end(1)
doubly_linked_list.insert_at_end(2)
doubly_linked_list.insert_at_end(3)

# Traversing the list forward and backward
print("Original Doubly Linked List:")
doubly_linked_list.traverse_forward()
doubly_linked_list.traverse_backward()

# Deleting a node
doubly_linked_list.delete_by_value(2)

# Traversing again after deletion
print("\nDoubly Linked List after Deletion:")
doubly_linked_list.traverse_forward()
doubly_linked_list.traverse_backward()