DSA — Doubly Linked Lists

What is a Doubly Linked List?

A linked list where each node has pointers to both next and previous nodes.

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

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

Insert Operations

def insert_at_head(self, data):
    new_node = Node(data)
    new_node.next = self.head
    if self.head:
        self.head.prev = new_node
    self.head = new_node

def insert_at_tail(self, data):
    new_node = Node(data)
    if not self.head:
        self.head = new_node
        return
    current = self.head
    while current.next:
        current = current.next
    current.next = new_node
    new_node.prev = current

Delete Operation

def delete(self, data):
    current = self.head
    while current:
        if current.data == data:
            if current.prev:
                current.prev.next = current.next
            else:
                self.head = current.next
            if current.next:
                current.next.prev = current.prev
            return
        current = current.next

Traversal

def display_forward(self):
    current = self.head
    while current:
        print(current.data, end=" <-> ")
        current = current.next
    print("None")

def display_backward(self):
    current = self.head
    while current.next:
        current = current.next
    while current:
        print(current.data, end=" <-> ")
        current = current.prev
    print("None")

Mini Practice

1. Implement a doubly linked list
2. Insert and delete operations
3. Traverse forward and backward
4. Compare with singly linked list

Up Next

Continue with Circular Linked Lists — circular linked list.