Circular Doubly Linked List 🎯

Welcome to our deep dive into the world of Data Structures and Algorithms! Today, we're going to explore a fascinating topic - the Circular Doubly Linked List. This data structure is a variation of the traditional Doubly Linked List, and it's used in real-world applications for efficient memory management. Let's get started!

What is a Circular Doubly Linked List? 📝

A Circular Doubly Linked List is a data structure that consists of nodes connected in a circular manner, where each node contains a data part and two links (one for the previous node and one for the next node). The last node's next pointer points to the first node, creating a circular structure.

Why Use a Circular Doubly Linked List? 💡

Memory Efficiency: Since the last node's next pointer points to the first node, the last node doesn't need an extra field to store NULL. This results in a space-efficient data structure.
Easy Traversal: By traversing from any node, we can traverse the entire list, making it suitable for applications requiring traversal without the need for a sentinel node.

Understanding the Nodes 📝

Each node in a Circular Doubly Linked List consists of the following components:

Data: This is the information stored in the node.
Next: A pointer pointing to the next node in the list.
Prev: A pointer pointing to the previous node in the list.

Implementing a Circular Doubly Linked List 💡

Here's a simple implementation of a Circular Doubly Linked List in Python:

python

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

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

    def add_node(self, data):
        if not self.head:
            self.head = Node(data)
            self.head.next = self.head
            self.head.prev = self.head
        else:
            new_node = Node(data)
            current = self.head
            while current.next != self.head:
                current = current.next
            current.next = new_node
            new_node.prev = current
            new_node.next = self.head
            self.head.prev = new_node

    def display(self):
        if not self.head:
            print("List is empty.")
            return
        current = self.head
        while current.next != self.head:
            print(current.data, end=" -> ")
            current = current.next
        print(self.head.data)

Practical Application 💡

Circular Doubly Linked Lists can be used in real-world applications like implementing a queue, a stack, or even a buffer in operating systems.

Quiz Time! 🎯

That's it for our first lesson on Circular Doubly Linked Lists! In the next lesson, we'll dive deeper into the practical applications and common operations performed on Circular Doubly Linked Lists. Stay tuned! 🚀