Doubly Linked List

DSA · Linked Lists

Theory

In a doubly linked list each node has pointers to both the next and the previous node. This allows traversal in both directions and O(1) deletion of a node when you hold a reference to it, because you can reach its predecessor directly. It uses more memory per node and requires updating two pointers on every change.

Why we use it

It supports fast removal from anywhere and bidirectional movement, which is why browser history and LRU caches use it.

When to use it

Use it for LRU caches, browser back/forward navigation, music playlists, and deques.

How it works

  1. head <-> node <-> node <-> tail
  2. Each node stores prev, data and next
  3. Insert: link new node to both neighbours
  4. Delete: neighbours point to each other
  5. Traverse forwards or backwards

Syntax

class DNode:
    def __init__(self, v): self.val = v; self.prev = None; self.next = None

Remove node n:
  n.prev.next = n.next
  n.next.prev = n.prev     # O(1)

Example

class DNode:
    def __init__(self, val):
        self.val = val
        self.prev = None
        self.next = None

head = DNode("Home")
about = DNode("About")
blog = DNode("Blog")
head.next, about.prev = about, head
about.next, blog.prev = blog, about

page = blog
print("Current page:", page.val)
page = page.prev
print("Back:", page.val)
page = page.next
print("Forward:", page.val)

about.prev.next = about.next      # remove About in O(1)
about.next.prev = about.prev
print("After removal, Home.next =", head.next.val)

Key points

DSA topics

Introduction to DSA

Arrays and Searching

Sorting Algorithms

Linked Lists

Stacks and Queues

Hashing

Trees

Heaps

Graphs

Algorithm Techniques

Classic Algorithms

Dynamic Programming

T
Tech Town
Log InSign Up Free
Home SQL Python DSA Power BI Snowflake Databricks Spark Gen AI Practice Problems Contest Blog

Data Structures & Algorithms

The complete DSA roadmap: theory, why and when to use every structure and algorithm, Big O complexity, and Python code you can run right here in the browser.

{{ sectionCount }}
Sections
{{ topicCount }}
Topics
Free
Forever
Hands-on practice Practice DSA Online 251 problems across 13 patterns, with hidden tests and step-by-step optimal solutions. Start practising →
Section {{ sec.num }}

{{ sec.label }}

DSA  /  {{ current.sectionLabel }}  /  {{ current.name }}

{{ current.name }}

Theory

{{ current.def }}

Why we use it

{{ current.why }}

When to use it

{{ current.when }}

Flowchart — how {{ current.name }} works
{{ nd.text }}
{{ nd.text }}
◇ {{ nd.text }}
Yes → {{ nd.yes }}
No → {{ nd.no }}
Step-by-step visualisation
{{ cell.v }}
{{ cell.i }} {{ cell.tag }}
Step {{ vizStepLabel }}: {{ vizNote }}
■ comparing ■ swapping / moving ■ done / found ■ out of range
Complexity & Pseudocode
{{ current.syntax }}
Example Code
{{ current.example }}
▶ Try It Live — runs real Python 3 in your browser (first run loads the engine)
{{ liveOutput }}
{{ liveError }}
Key Points — click to check off as you learn
  • {{ pt.mark }} {{ pt.text }}

Share this topic