[Follow here] for daily coding insights.

DSA SERIES – DOUBLY LINKED LIST (Python Version)

1. Introduction to Doubly Linked List in Python

A Doubly Linked List (DLL) is a dynamic data structure where each node has:

data → value stored
prev → pointer to previous node
next → pointer to next node

Why Python DLL?

Python lists are dynamic, but DLL is still required in interviews & system-level design because:

Faster insertions/deletions in middle
Better for implementing LRU Cache
Browser history navigation
Undo/Redo system
Doubly-ended operations

2. Node Class in Python

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

Explanation

self.data: stores the value
self.prev: pointer to previous node
self.next: pointer to next node
Python does not need manual memory management, unlike C

3. Doubly Linked List Class

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

Starts with an empty list
head stores the first node

4. Insert at Beginning

def insert_at_begin(self, data):
    new_node = Node(data)
    new_node.next = self.head

    if self.head is not None:
        self.head.prev = new_node

    self.head = new_node

Explanation

Create new node
Link new node’s next → old head
Update old head’s prev
Move head to new node
T.C = O(1)

5. Insert at End

def insert_at_end(self, data):
    new_node = Node(data)

    if self.head is None:
        self.head = new_node
        return

    temp = self.head
    while temp.next:
        temp = temp.next

    temp.next = new_node
    new_node.prev = temp

Explanation

Traverse till last node
Attach new node
T.C = O(n)

6. Insert at Any Position

def insert_at_pos(self, data, pos):
    if pos <= 0:
        print("Invalid Position")
        return

    new_node = Node(data)

    if pos == 1:
        self.insert_at_begin(data)
        return

    temp = self.head
    for _ in range(pos - 2):
        if temp is None:
            print("Position out of range")
            return
        temp = temp.next

    new_node.next = temp.next
    new_node.prev = temp

    if temp.next:
        temp.next.prev = new_node

    temp.next = new_node

7. Delete from Beginning

def delete_begin(self):
    if self.head is None:
        print("List Empty")
        return

    temp = self.head
    self.head = self.head.next

    if self.head:
        self.head.prev = None

    del temp

8. Delete from End

def delete_end(self):
    if self.head is None:
        print("List Empty")
        return

    temp = self.head

    if temp.next is None:
        self.head = None
        del temp
        return

    while temp.next:
        temp = temp.next

    temp.prev.next = None
    del temp

9. Delete at Any Position

def delete_at_pos(self, pos):
    if self.head is None:
        print("List Empty")
        return

    temp = self.head

    if pos == 1:
        self.delete_begin()
        return

    for _ in range(pos - 1):
        if temp is None:
            print("Position out of range")
            return
        temp = temp.next

    temp.prev.next = temp.next

    if temp.next:
        temp.next.prev = temp.prev

    del temp

10. Forward Traversal

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

11. Reverse Traversal

def display_reverse(self):
    temp = self.head
    if temp is None:
        print("None")
        return

    while temp.next:
        temp = temp.next

    while temp:
        print(temp.data, end=" <-> ")
        temp = temp.prev
    print("None")

12. Complete Working Program (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 insert_at_begin(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_end(self, data):
        new_node = Node(data)

        if not self.head:
            self.head = new_node
            return

        temp = self.head
        while temp.next:
            temp = temp.next

        temp.next = new_node
        new_node.prev = temp

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

    def display_reverse(self):
        temp = self.head
        if temp is None:
            print("None")
            return

        while temp.next:
            temp = temp.next

        while temp:
            print(temp.data, end=" <-> ")
            temp = temp.prev
        print("None")


# Driver Code
dll = DoublyLinkedList()
dll.insert_at_begin(30)
dll.insert_at_begin(20)
dll.insert_at_begin(10)
dll.insert_at_end(40)
dll.insert_at_end(50)

print("Forward:")
dll.display_forward()

print("Reverse:")
dll.display_reverse()

13. Time & Space Complexity

Operation	Time	Space
Insert begin	O(1)	O(1)
Insert end	O(n)	O(1)
Insert pos	O(n)	O(1)
Delete begin	O(1)	O(1)
Delete end	O(n)	O(1)
Delete pos	O(n)	O(1)
Forward Traverse	O(n)	O(1)
Reverse Traverse	O(n)	O(1)