Circular Doubly Linked List in Python Data Structure in Python – Complete Tutorial with Examples

Step-by-Step Explanation

What Problem This Solves

It solves the “never-ending playlist with rewind” problem: you want songs to play one after another forever, and you also want to skip backward to the previous song, like a music player with both “next” and “previous” buttons.

Step-by-step walkthrough (beginner-friendly)

1. The song node

class SongNode:
    def __init__(self, title):
        self.title = title
        self.next = None
        self.prev = None

Each node contains three fields:

• title: the song’s name (e.g., "Track 1").
• next: link to the next song.
• prev: link to the previous song.

Each song can point both forward and backward.

2. Playlist class and fields

class FullFeaturedPlaylist:
    def __init__(self):
        self.current = None
        self.tail = None

The constructor initializes the playlist:

• self.current: the song that is currently playing (or the “now playing” position).
• self.tail: the last song in the list.

Because the list is circular, self.tail.next is always the first song.

When the playlist is empty, both are None.

3. Adding a song

def add_song(self, title):
    new_song = SongNode(title)
    if self.current is None:
        new_song.next = new_song.prev = new_song
        self.current = self.tail = new_song
    else:
        new_song.prev = self.tail
        new_song.next = self.tail.next
        self.tail.next.prev = new_song
        self.tail.next = new_song
        self.tail = new_song

Case 1: First song

If self.current is None:

• The new song points to itself in both directions.
• Both current and tail point to this song.

The circle is: [current/tail] ⇄ [same song]

Case 2: Additional songs

If songs already exist:

• new_song.prev = self.tail - new song points backward to old tail.
• new_song.next = self.tail.next - new song points forward to the first song (because tail.next is the head).
• self.tail.next.prev = new_song - the first song points backward to the new song.
• self.tail.next = new_song - old tail points forward to the new song.
• self.tail = new_song - the new song becomes the new last song.

The circular order becomes: first ⇄ ... ⇄ old_tail ⇄ new_song ⇄ first

4. Play the next song

def play_next(self):
    self.current = self.current.next   # never runs out - loops automatically
    print(f"Now playing: {self.current.title}")

• Move self.current forward by one node: self.current = self.current.next.
• Print the song title stored in the new current node.

Because the list is circular, after the last song, current.next goes back to the first song, so playback repeats forever.

5. Play the previous song

def play_previous(self):
    self.current = self.current.prev   # new capability vs. the circular doubly linked version
    print(f"Now playing: {self.current.title}")

• Move self.current backward by one node: self.current = self.current.prev.
• Print the song title stored in the new current node.

Because the list is circular, before the first song, current.prev goes back to the last song, so backward navigation also loops forever.

Why a circular doubly linked list fits this problem

A circular doubly linked list naturally models an endless repeating order in both directions: after the last song comes the first, and before the first comes the last. The prev pointer enables backward navigation, which a circular doubly linked list cannot do directly.

Visual text-diagram

(Successful example: add Track 1, 2, 3; play next 3 times; play previous once)

Initial state

current = None
tail = None

After add_song("Track 1")

Node(Track 1): next → itself, prev → itself

current → Node(Track 1)
tail    → Node(Track 1)

Track 1 ⇄ Track 1 (self-loop)

After add_song("Track 2")

Node(Track 1).next → Node(Track 2)
Node(Track 2).prev → Node(Track 1)
Node(Track 2).next → Node(Track 1)
Node(Track 1).prev → Node(Track 2)

current → Node(Track 1)
tail    → Node(Track 2)

Track 1 ⇄ Track 2 ⇄ Track 1 (circle)

After add_song("Track 3")

Node(Track 2).next → Node(Track 3)
Node(Track 3).prev → Node(Track 2)
Node(Track 3).next → Node(Track 1)
Node(Track 1).prev → Node(Track 3)

current → Node(Track 1)
tail    → Node(Track 3)

Track 1 ⇄ Track 2 ⇄ Track 3 ⇄ Track 1 (circle)

play_next() #1

Move current from Track 1 to Track 2.
Print “Now playing: Track 2”.
current → Track 2
tail    → Track 3

Output: Now playing: Track 2

play_next() #2

Move current from Track 2 to Track 3.
Print “Now playing: Track 3”.
current → Track 3

Output: Now playing: Track 3

play_next() #3

Move current from Track 3 to Track 1 (because Track 3.next → Track 1).
Print “Now playing: Track 1”.
current → Track 1

Output: Now playing: Track 1

play_previous()

Move current from Track 1 to Track 3 (because Track 1.prev → Track 3).
Print “Now playing: Track 3”.
current → Track 3

Output: Now playing: Track 3

Trace Table (Successful Run)

Trace table (successful run: Track 1, 2, 3; 3 nexts + 1 previous)

Printed sequence:

Now playing: Track 2
Now playing: Track 3
Now playing: Track 1
Now playing: Track 3

Trace for a Failing Example (No Songs Added, Then play_next)

Now try to play when the playlist is empty.

Setup

playlist = FullFeaturedPlaylist()
# current = None, tail = None

Operation

playlist.play_next()

Trace table (failure case)

It fails at step 2 because there is no song node to move to, so accessing .next on None causes an error.

Summary

This code keeps songs in a circular doubly linked list and advances a current pointer forward or backward around the circle so that playback loops forever in either direction.

Step-by-Step Explanation

What Problem This Solves

It solves the “fair turn-taking with priority awareness” problem: like a help desk that serves customers in order but also notes when a lower-priority request comes right after a higher-priority one, the scheduler cycles through tasks and highlights priority drops.

Step-by-step walkthrough (beginner-friendly)

1. The task node

class Task:
    def __init__(self, name, priority):
        self.name = name
        self.priority = priority
        self.next = None
        self.prev = None

Each task contains four fields:

• name: the task’s label (e.g., "Backup").
• priority: a number representing importance (lower = more important here).
• next: link to the next task.
• prev: link to the previous task.

Each task can point both forward and backward.

2. Scheduler class and fields

class SmartScheduler:
    def __init__(self):
        self.current = None
        self.tail = None

The constructor initializes the scheduler:

• self.current: the task that will run next.
• self.tail: the last task in the list.

Because the list is circular, self.tail.next is always the first task.

When no tasks are added yet, both are None.

3. Adding a task

def add_task(self, name, priority):
    new_task = Task(name, priority)
    if self.current is None:
        new_task.next = new_task.prev = new_task
        self.current = self.tail = new_task
    else:
        new_task.prev = self.tail
        new_task.next = self.tail.next
        self.tail.next.prev = new_task
        self.tail.next = new_task
        self.tail = new_task

Case 1: First task

If self.current is None:

• The new task points to itself in both directions.
• Both current and tail point to this task.

The circle is: [current/tail] ⇄ [same task]

Case 2: Additional tasks

If tasks already exist:

• new_task.prev = self.tail - new task points backward to old tail.
• new_task.next = self.tail.next - new task points forward to the first task (because tail.next is the head).
• self.tail.next.prev = new_task - the first task points backward to the new task.
• self.tail.next = new_task - old tail points forward to the new task.
• self.tail = new_task - the new task becomes the new last task.

The circular order becomes: first ⇄ ... ⇄ old_tail ⇄ new_task ⇄ first

4. Run the next task

def run_next(self):
    print(f"Running {self.current.name} (priority {self.current.priority})")
    if self.current.priority < self.current.prev.priority:
        print(f"  -> Low priority detected, double-checking previous task: {self.current.prev.name}")
    self.current = self.current.next

• Print the current task’s name and priority.
• Compare the current task’s priority with the previous task’s priority (self.current.prev.priority).
• If the current task’s priority is lower (numerically smaller), print a “low priority detected” note.
• Move self.current forward by one node: self.current = self.current.next.

Because the list is circular, after the last task, current.next goes back to the first task, so the scheduler cycles forever.

Why a circular doubly linked list fits this problem

A circular doubly linked list naturally models an endless repeating order: after the last task comes the first, and the prev pointer lets the scheduler easily look back at the previous task to compare priorities. This matches exactly how round-robin scheduling cycles through tasks repeatedly.

Visual text-diagram

(Successful example: add Backup(5), Cleanup(1), Report(3); run 3 times)

Initial state

current = None
tail = None

After add_task("Backup", 5)

Node(Backup): next → itself, prev → itself

current → Node(Backup)
tail    → Node(Backup)

Backup ⇄ Backup (self-loop)

After add_task("Cleanup", 1)

Node(Backup).next → Node(Cleanup)
Node(Cleanup).prev → Node(Backup)
Node(Cleanup).next → Node(Backup)
Node(Backup).prev → Node(Cleanup)

current → Node(Backup)
tail    → Node(Cleanup)

Backup ⇄ Cleanup ⇄ Backup (circle)

After add_task("Report", 3)

Node(Cleanup).next → Node(Report)
Node(Report).prev → Node(Cleanup)
Node(Report).next → Node(Backup)
Node(Backup).prev → Node(Report)

current → Node(Backup)
tail    → Node(Report)

Backup ⇄ Cleanup ⇄ Report ⇄ Backup (circle)

run_next() #1

Running Backup (priority 5)
Compare: Backup(5) vs prev (Report, 3) → 5 < 3? No → no extra note.
Move current to Cleanup.

current → Cleanup

Output: Running Backup (priority 5)

run_next() #2

Running Cleanup (priority 1)
Compare: Cleanup(1) vs prev (Backup, 5) → 1 < 5? Yes → print low-priority note.
Move current to Report.

current → Report

Output:
Running Cleanup (priority 1)
  -> Low priority detected, double-checking previous task: Backup

run_next() #3

Running Report (priority 3)
Compare: Report(3) vs prev (Cleanup, 1) → 3 < 1? No → no extra note.
Move current to Backup.

current → Backup

Output: Running Report (priority 3)

Trace Table (Successful Run)

Trace table (successful run: Backup(5), Cleanup(1), Report(3); 3 runs)

Printed sequence:

Running Backup (priority 5)
Running Cleanup (priority 1)
  -> Low priority detected, double-checking previous task: Backup
Running Report (priority 3)

Trace for a Failing Example (No Tasks Added, Then run_next)

Now try to run when no tasks exist.

Setup

scheduler = SmartScheduler()
# current = None, tail = None

Operation

scheduler.run_next()

Trace table (failure case)

It fails at step 2 because there is no task node to read, so accessing .name on None causes an error.

Summary

This code keeps tasks in a circular doubly linked list and advances a current pointer around the circle so the scheduler cycles through tasks forever, printing each task’s priority and flagging when a lower-priority task follows a higher-priority one.

Step-by-Step Explanation

What Problem This Solves

It solves the “remember only the last few changes” problem: like a text editor that keeps only the most recent undo steps and forgets older ones when the history gets too long, this program stores a limited number of past states and evicts the oldest when the cap is reached.

Step-by-step walkthrough (beginner-friendly)

1. The history-state node

class HistoryState:
    def __init__(self, text):
        self.text = text
        self.next = None
        self.prev = None

Each state contains three fields:

• text: the saved document state (e.g., "Hello").
• next: link to the next (newer) state.
• prev: link to the previous (older) state.

Each state can point both forward and backward.

2. History class and fields

class BoundedUndoHistory:
    def __init__(self, max_states):
        self.max_states = max_states
        self.current = None
        self.tail = None
        self.count = 0

The constructor initializes the history manager:

• max_states: the maximum number of states to keep (e.g., 3).
• current: the most recently recorded state.
• tail: the oldest state in the circle (the one to evict next).
• count: how many states are currently stored.

When no states are recorded yet, current and tail are both None and count is 0.

3. Recording a new state

def record(self, text):
    new_state = HistoryState(text)
    if self.current is None:
        new_state.next = new_state.prev = new_state
        self.current = self.tail = new_state
        self.count = 1
        return

Case 1: First state

If self.current is None:

• The new state points to itself in both directions.
• Both current and tail point to this state.
• count becomes 1.

The circle is: [current/tail] ⇄ [same state]

Case 2: Additional states

If states already exist:

new_state.prev = self.current
new_state.next = self.current.next
self.current.next.prev = new_state
self.current.next = new_state
self.current = new_state
self.count += 1

• new_state.prev = self.current - new state points backward to the old current.
• new_state.next = self.current.next - new state points forward to whatever came after the old current.
• self.current.next.prev = new_state - the node after the old current points backward to the new state.
• self.current.next = new_state - the old current points forward to the new state.
• self.current = new_state - the new state becomes the current (most recent) state.
• self.count += 1 - increment the stored-state count.

4. Evicting the oldest state when the cap is exceeded

if self.count > self.max_states:
    oldest = self.tail
    self.tail = oldest.next
    oldest.prev.next = oldest.next
    oldest.next.prev = oldest.prev
    self.count -= 1
else:
    self.tail = new_state.next if self.tail is None else self.tail

• If count exceeds max_states, the oldest state (pointed to by tail) is removed.
• oldest = self.tail - grab the oldest state.
• self.tail = oldest.next - move the tail pointer to the next state.
• oldest.prev.next = oldest.next - bypass the oldest state by linking its prev directly to its next.
• oldest.next.prev = oldest.prev - bypass the oldest state from the other direction.
• self.count -= 1 - decrement the stored-state count.
• If the cap is not exceeded, the tail pointer is adjusted only if it was None (a fallback that normally doesn’t trigger after the first state).

The oldest state is removed from the circle, keeping the history bounded.

5. Example usage

history = BoundedUndoHistory(max_states=3)
history.record("Hello")
history.record("Hello World")
history.record("Hello World!")
history.record("Hello World! Extra")

• Record "Hello" → circle: Hello ⇄ Hello.
• Record "Hello World" → circle: Hello ⇄ Hello World ⇄ Hello.
• Record "Hello World!" → circle: Hello ⇄ Hello World ⇄ Hello World! ⇄ Hello.
• Record "Hello World! Extra" → count becomes 4, exceeding the cap of 3, so "Hello" is evicted.

Final circle: Hello World ⇄ Hello World! ⇄ Hello World! Extra ⇄ Hello World.

Why a circular doubly linked list fits this problem

A circular doubly linked list lets you move forward (redo direction) and backward (undo direction) through states, and the circular link means there’s no fixed “end” - the oldest state sits right after the newest, making eviction easy. This matches exactly how undo/redo history works in editors.

Visual text-diagram

(Successful example: record 4 states with max_states=3)

After record("Hello")

Node("Hello"): next → itself, prev → itself

current → Node("Hello")
tail    → Node("Hello")
count   = 1

Hello ⇄ Hello (self-loop)

After record("Hello World")

Node("Hello").next → Node("Hello World")
Node("Hello World").prev → Node("Hello")
Node("Hello World").next → Node("Hello")
Node("Hello").prev → Node("Hello World")

current → Node("Hello World")
tail    → Node("Hello")
count   = 2

Hello ⇄ Hello World ⇄ Hello (circle)

After record("Hello World!")

Node("Hello World").next → Node("Hello World!")
Node("Hello World!").prev → Node("Hello World")
Node("Hello World!").next → Node("Hello")
Node("Hello").prev → Node("Hello World!")

current → Node("Hello World!")
tail    → Node("Hello")
count   = 3

Hello ⇄ Hello World ⇄ Hello World! ⇄ Hello (circle)

After record("Hello World! Extra")

New state inserted after current ("Hello World!")
count becomes 4 > 3 → evict oldest ("Hello")

oldest = tail ("Hello")
tail = oldest.next ("Hello World")
oldest.prev.next = oldest.next
oldest.next.prev = oldest.prev

current → Node("Hello World! Extra")
tail    → Node("Hello World")
count   = 3

Hello World ⇄ Hello World! ⇄ Hello World! Extra ⇄ Hello World (circle)

Trace Table (Successful Run)

Trace table (successful run: 4 records with max_states=3)

Trace for a Failing Example (Recording When max_states is 0)

Now try to record when the history cap is zero.

Setup

history = BoundedUndoHistory(max_states=0)
# current = None, tail = None, count = 0

Operation

history.record("Hello")

Trace table (failure case)

It “fails” to retain any state because max_states=0 means no states are allowed to persist, so every recorded state is immediately evicted.

Summary

This code keeps a bounded undo history in a circular doubly linked list by inserting each new state after the current one and evicting the oldest state whenever the stored count exceeds the configured maximum.

Step-by-Step Explanation

What Problem This Solves

It solves the “reverse part of a circle” problem: imagine beads on a circular necklace, and you want to flip the order of a few consecutive beads without breaking the circle or rearranging the rest.

Step-by-step walkthrough (beginner-friendly)

1. The node idea

Each node has:

• value: the data (e.g., "A", "B", …).
• next: link to the next node in the circle.
• prev: link to the previous node in the circle.

The list is circular, so the last node’s next points back to the first node.

2. Function signature

def reverse_segment(start_node, length, forward=True):

• start_node: the node where the segment to reverse begins.
• length: how many nodes in the segment to reverse.
• forward: if True, walk using next; if False, walk using prev.

3. Prepare a stack and a pointer

stack = []
current = start_node

• stack: an empty list used as a stack (last-in, first-out).
• current: a moving pointer that will walk through the segment.

4. First pass: collect values into the stack

for _ in range(length):
    stack.append(current.value)
    current = current.next if forward else current.prev

Repeat length times:

• Push current.value onto the stack.
• Move current to the next node (using next if forward is True, else prev).

After this loop, the stack contains the segment’s values in original order from bottom to top.

Example with segment A → B → C and length = 3, forward=True:

• Push "A", then "B", then "C".
• Stack (bottom → top): ["A", "B", "C"].

5. Second pass: write values back in reverse

current = start_node
while stack:
    current.value = stack.pop()
    current = current.next if forward else current.prev

• Reset current to start_node.
• While the stack is not empty:
  • Pop the top value from the stack.
  • Overwrite current.value with that popped value.
  • Move current to the next node (same direction as before).

Because a stack is last-in, first-out, the values come out in reverse order, so the segment is reversed in place.

6. Example setup and call

node_a, node_b, node_c, node_d = Node("A"), Node("B"), Node("C"), Node("D")
node_a.next, node_b.next, node_c.next, node_d.next = node_b, node_c, node_d, node_a
node_a.prev, node_b.prev, node_c.prev, node_d.prev = node_d, node_a, node_b, node_c

reverse_segment(node_a, 3, forward=True)

Initial circle:

A ⇄ B ⇄ C ⇄ D ⇄ (back to A)

We reverse a segment of length 3 starting at A, walking forward, so A → B → C becomes C → B → A.

Expected final circle:

C ⇄ B ⇄ A ⇄ D ⇄ (back to C)

Reading four nodes from A gives: ["C", "B", "A", "D"].

Why a stack fits this problem

A stack naturally reverses the order of items: whatever goes in first comes out last. By pushing the segment’s values and then popping them back into the same nodes, the segment is reversed without changing the links.

Visual text-diagram

(Successful example: circle A⇄B⇄C⇄D, reverse 3 from A, forward)

Initial circle

node_a ("A") ⇄ node_b ("B") ⇄ node_c ("C") ⇄ node_d ("D") ⇄ (back to node_a)
^
start_node, current

First pass: collect 3 values

Step 1:
- Push "A"  
- Move to B

stack: ["A"]
current → B

Step 2:
- Push "B"  
- Move to C

stack: ["A", "B"]
current → C

Step 3:
- Push "C"  
- Move to D

stack: ["A", "B", "C"]   (top is "C")
current → D

Second pass: write back in reverse

Reset current = start_node (back to A).

Step 1:
- Pop "C"  
- Set A.value = "C"  
- Move to B

stack: ["A", "B"]
nodes: C ⇄ B ⇄ C ⇄ D ⇄ (back to C)
         ^ (A now holds "C")
current → B

Step 2:
- Pop "B"  
- Set B.value = "B" (unchanged visually, but logically overwritten)  
- Move to C

stack: ["A"]
nodes: C ⇄ B ⇄ C ⇄ D ⇄ (back to C)
               ^ (this node will get "A")
current → C

Step 3:
- Pop "A"  
- Set C.value = "A"  
- Move to D

stack: []
nodes: C ⇄ B ⇄ A ⇄ D ⇄ (back to C)
                     ^
current → D

Final circle:

C ⇄ B ⇄ A ⇄ D ⇄ (back to C)

Reading from node_a (which now holds "C"):

C → B → A → D → ...

Trace Table (Successful Run)

Trace table (successful run: A⇄B⇄C⇄D, reverse length=3 from A, forward)

Final printed list:

["C", "B", "A", "D"]

Trace for a Failing Example (Segment Longer Than Circle)

Suppose the circle has 3 nodes but we try to reverse a segment of length 4.

Setup

node_a, node_b, node_c = Node("A"), Node("B"), Node("C")
node_a.next, node_b.next, node_c.next = node_b, node_c, node_a
node_a.prev, node_b.prev, node_c.prev = node_c, node_a, node_b

reverse_segment(node_a, 4, forward=True)

Trace table (failure case)

The code does not crash, but it fails logically: the “segment” wrapped around the circle and included the same node twice, so the result is not a clean reversal of a distinct segment.

Summary

This function reverses a chosen segment of a circular doubly linked list by pushing its values onto a stack and then popping them back into the same nodes, which flips their order while leaving the circular links unchanged.