DSAverse

Basics & Data Structures

Loading Data Structures...

Array Access

array[0..5]indexed access

Array

Stack

Queue

DSAverse

Initializing Sorting Algorithms...

Sorting

Trees

Graphs

Preparing interactive visualizations...

Back to Basics

Intermediate

Doubly Linked List

Each node stores both a prev and a next pointer. Traverse in either direction and delete any node in O(1) given a pointer to it.

Bidirectional Traversal

O(1) Tail Delete

Interactive Operations

Doubly Linked List

Each node has a ← prev and a next → pointer. HEAD.prev = NULL, TAIL.next = NULL.

Color Legend

DefaultTraversingTarget foundComplete

Speed:

List is empty — insert to begin

Size

–

HEAD

–

TAIL

Insert at head/tail/index, delete, search, or traverse backward to begin.

Complexity

O(1)

Insert Head / Tail

O(n)

Insert at Index

O(1)*

Delete (with ptr)

O(n)

Search by Value

O(n) Space

n nodes × (value + prev ptr + next ptr)

*O(1) delete requires a pointer to the node; traversal to find it is O(n).

Key Properties

.prev pointer

Each node knows its predecessor — enables backward traversal and O(1) tail delete

.next pointer

Each node knows its successor — standard forward traversal

HEAD + TAIL

Two sentinel pointers — O(1) access and insert at both ends

4 ptr updates

Each insert in the middle touches prev and next of both neighbors

vs Singly Linked List

Backward traversal in O(n)

Singly requires rebuilding a reversed copy or recursion

O(1) tail deletion

Singly needs O(n) to find the node before tail

O(1) delete with known pointer

Singly still needs to traverse to predecessor

Extra memory per node

One additional pointer field — doubles pointer overhead

More pointer updates per op

4 updates for middle insert vs 2 for singly

Test Yourself

Q1/3

What is the time complexity of deleting a node when you already have a direct pointer to it in a doubly linked list?

Python Implementation

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
        self.size = 0

    def insert_head(self, value):        # O(1)
        node = Node(value)
        if not self.head:
            self.head = self.tail = node
        else:
            node.next = self.head
            self.head.prev = node
            self.head = node
        self.size += 1

    def insert_tail(self, value):        # O(1)
        node = Node(value)
        if not self.tail:
            self.head = self.tail = node
        else:
            self.tail.next = node
            node.prev = self.tail
            self.tail = node
        self.size += 1

    def insert_at(self, index, value):   # O(n) traverse
        if index == 0:
            self.insert_head(value); return
        if index == self.size:
            self.insert_tail(value); return
        node = Node(value)
        cur = self.head
        for _ in range(index - 1):
            cur = cur.next
        node.prev, node.next = cur, cur.next  # 4 pointer updates
        cur.next.prev = node
        cur.next = node
        self.size += 1

    def delete(self, index):             # O(n) traverse, O(1) unlink
        cur = self.head
        for _ in range(index):
            cur = cur.next
        if cur.prev: cur.prev.next = cur.next
        else:        self.head = cur.next
        if cur.next: cur.next.prev = cur.prev
        else:        self.tail = cur.prev
        self.size -= 1
        return cur.value

    def traverse_backward(self):         # O(n)
        cur = self.tail
        while cur:
            yield cur.value
            cur = cur.prev

DSAverse

Basics & Data Structures

Loading Data Structures...

Array Access

array[0..5]indexed access

Array

Stack

Queue

Back to Basics

Intermediate

Doubly Linked List

Each node stores both a prev and a next pointer. Traverse in either direction and delete any node in O(1) given a pointer to it.

Bidirectional Traversal

O(1) Tail Delete

Interactive Operations

Doubly Linked List

Each node has a ← prev and a next → pointer. HEAD.prev = NULL, TAIL.next = NULL.

Color Legend

DefaultTraversingTarget foundComplete

Speed:

List is empty — insert to begin

Size

–

HEAD

–

TAIL

Insert at head/tail/index, delete, search, or traverse backward to begin.

Complexity

O(1)

Insert Head / Tail

O(n)

Insert at Index

O(1)*

Delete (with ptr)

O(n)

Search by Value

O(n) Space

n nodes × (value + prev ptr + next ptr)

*O(1) delete requires a pointer to the node; traversal to find it is O(n).

Key Properties

.prev pointer

Each node knows its predecessor — enables backward traversal and O(1) tail delete

.next pointer

Each node knows its successor — standard forward traversal

HEAD + TAIL

Two sentinel pointers — O(1) access and insert at both ends

4 ptr updates

Each insert in the middle touches prev and next of both neighbors

vs Singly Linked List

Backward traversal in O(n)

Singly requires rebuilding a reversed copy or recursion

O(1) tail deletion

Singly needs O(n) to find the node before tail

O(1) delete with known pointer

Singly still needs to traverse to predecessor

Extra memory per node

One additional pointer field — doubles pointer overhead

More pointer updates per op

4 updates for middle insert vs 2 for singly

Test Yourself

Q1/3

What is the time complexity of deleting a node when you already have a direct pointer to it in a doubly linked list?

Python Implementation

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
        self.size = 0

    def insert_head(self, value):        # O(1)
        node = Node(value)
        if not self.head:
            self.head = self.tail = node
        else:
            node.next = self.head
            self.head.prev = node
            self.head = node
        self.size += 1

    def insert_tail(self, value):        # O(1)
        node = Node(value)
        if not self.tail:
            self.head = self.tail = node
        else:
            self.tail.next = node
            node.prev = self.tail
            self.tail = node
        self.size += 1

    def insert_at(self, index, value):   # O(n) traverse
        if index == 0:
            self.insert_head(value); return
        if index == self.size:
            self.insert_tail(value); return
        node = Node(value)
        cur = self.head
        for _ in range(index - 1):
            cur = cur.next
        node.prev, node.next = cur, cur.next  # 4 pointer updates
        cur.next.prev = node
        cur.next = node
        self.size += 1

    def delete(self, index):             # O(n) traverse, O(1) unlink
        cur = self.head
        for _ in range(index):
            cur = cur.next
        if cur.prev: cur.prev.next = cur.next
        else:        self.head = cur.next
        if cur.next: cur.next.prev = cur.prev
        else:        self.tail = cur.prev
        self.size -= 1
        return cur.value

    def traverse_backward(self):         # O(n)
        cur = self.tail
        while cur:
            yield cur.value
            cur = cur.prev