Circular Doubly Linked List Tutorial

Circular Doubly Linked List

A Circular Doubly Linked List combines features of both circular and doubly linked lists. Each node has pointers to both the next and previous nodes, and the last node's next pointer points to the first node, while the first node's previous pointer points to the last node.

Key characteristics:

Bidirectional circular structure: Can be traversed in both directions without endpoints.
Each node has three components: data, next pointer, and previous pointer.
The first node's previous points to the last node, and the last node's next points to the first node.
Allows for efficient insertion and deletion at both ends of the list.

Key operations:

Insertion (at the beginning, end, and at a specific position)
Deletion (from any position)
Forward and backward traversal
Searching for an element

Real-world applications:

Implementation of advanced data structures like Fibonacci Heap
Managing multiple applications in a multi-tasking operating system
Implementing browser cache with efficient forward and backward navigation
Undo-redo functionality in applications
Designing music players with repeat-all functionality and bi-directional song navigation

Node Structure

java

xxxxxxxxxx
 
class Node {    int data;    Node next;    Node prev;        Node(int data) {        this.data = data;        this.next = null;        this.prev = null;    }}

Circular Doubly Linked List(CDLL) Operations: Pseudocode For Insertions

First we write the Pseudocode for Circular Doubly Linked List Operations

Add a node at the beginning.
Adding a node at the end.
Adding a node at a specific position.

Adding a node at a specific position.

java

xxxxxxxxxx
 
Function insertAt(index: Integer, data: Integer):    If index < 0:        Print "Invalid index"        Return    Create newNode with given data    Set current to head    Initialize counter j to 0    While j < index - 2:        If current is null:            Print "Invalid index"            Return        Set current to current.next        Increment j    If current.next is not null:        Set newNode.next to current.next        Set current.next.prev to newNode    Set newNode.prev to current    Set current.next to newNode

Add Node at First

java

xxxxxxxxxx
 
Function addNodeAtFirst(data: Integer):    Create newNode with given data    If head is null:        head = newNode        tail = newNode        Set head.next to newNode        Set head.prev to newNode        Return    Else:        Set newNode.next to head        Set head.prev to newNode        Set head.prev to tail        Set tail.next to newNode        Set head to newNode

Add Node at Last

java

xxxxxxxxxx
 
Function addNodeAtLast(data: Integer):    Create newNode with given data    If head is null:        head = newNode        tail = newNode        Set head.next to newNode        Set head.prev to newNode        Return    Else:        Set tail.next to newNode        Set newNode.prev to tail        Set newNode.next to head        Set head.prev to newNode        Set tail to newNode

Code for Insertions In Circular Doubly Linked List (CDLL)

Code for Insertions In Circular Doubly Linked List (CDLL):

Add a node at the beginning.
Adding a node at the end.
Adding a node at a specific position.
Print Circular Doubly Linked List Forward
Print Circular Doubly Linked List Reverse

Full Code

java

python

​x
 
public class OperationsOnCDLL{    private static CDLLNode cdllNodeHead;    private static CDLLNode cdllNodeTail;​    public static class CDLLNode {        int data;        CDLLNode next;        CDLLNode prev;​        CDLLNode(int data) {            this.data = data;            this.next = null;            this.prev = null;        }    }​    public static void addNodeAtLast(int data)    {        CDLLNode newNode = new CDLLNode(data);        if(cdllNodeHead == null)        {            cdllNodeHead = newNode;            cdllNodeTail = newNode;            cdllNodeHead.next = newNode;            cdllNodeHead.prev = newNode;            return;        }        cdllNodeTail.next = newNode;        newNode.prev = cdllNodeTail;        newNode.next = cdllNodeHead;        cdllNodeHead.prev = newNode;        cdllNodeTail = newNode;    }​    public static void addNodeAtFirst(int data)    {        CDLLNode newNode = new CDLLNode(data);        if(cdllNodeHead == null)        {            cdllNodeHead = newNode;            cdllNodeTail = newNode;            cdllNodeHead.next = newNode;            cdllNodeHead.prev = newNode;            return;        }        newNode.next = cdllNodeHead;        cdllNodeHead.prev = newNode;        newNode.prev = cdllNodeTail;        cdllNodeTail.next = newNode;        cdllNodeHead = newNode;    }​    public static void printCDLLForward(CDLLNode head)    {        if (head == null) {            System.out.println("List is empty");            return;        }        CDLLNode curr = head;        do {            System.out.print(curr.data + "->");            curr = curr.next;        } while (curr != head);        System.out.print("null");    }​    public static void printCDLLReverse(CDLLNode tail)    {        if (tail == null) {            System.out.println("List is empty");            return;        }        CDLLNode curr = tail;        do {            System.out.print(curr.data + "->");            curr = curr.prev;        } while (curr != tail);        System.out.print("null");    }​    public static void main(String[] args)    {        OperationsOnCDLL.addNodeAtLast(10);        OperationsOnCDLL.addNodeAtLast(5);        OperationsOnCDLL.addNodeAtLast(15);        OperationsOnCDLL.addNodeAtFirst(20);​        System.out.println("Forward Direction");        OperationsOnCDLL.printCDLLForward(cdllNodeHead);​        System.out.println();        System.out.println("Reverse Direction");        OperationsOnCDLL.printCDLLReverse(cdllNodeTail);    }}

Code Output

Forward Direction
20->10->5->15->null
Reverse Direction
15->5->10->20->null