The Project | About Us | Contribute | Donations | License
HOME My courses Completed
◄ Previous
◄

Circular Lists

Next ►
►

Introduction to Circular Lists

Circular lists are a type of linked list where the last node points back to the first node, forming a circle. This structure allows for continuous traversal of the list without encountering a null reference, making it useful for applications that require a cyclic iteration through elements.

Key Concepts

  • Circular Singly Linked List: Each node points to the next node, and the last node points back to the first node.
  • Circular Doubly Linked List: Each node points to both the next and the previous node, and the last node points back to the first node while the first node points back to the last node.

Advantages of Circular Lists

  • Efficient Traversal: You can traverse the entire list starting from any node.
  • Useful for Round-Robin Scheduling: Ideal for tasks that require cyclic iteration, such as CPU scheduling.
  • No Null References: Since the last node points back to the first node, there are no null references, reducing the risk of null pointer exceptions.

Disadvantages of Circular Lists

  • Complexity: More complex to implement and manage compared to linear linked lists.
  • Infinite Loop Risk: Without proper termination conditions, traversing a circular list can lead to infinite loops.

Circular Singly Linked List

Structure

Node1 -> Node2 -> Node3 -> Node1

Implementation in Python

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

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

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

    def display(self):
        nodes = []
        current = self.head
        if self.head:
            while True:
                nodes.append(current.data)
                current = current.next
                if current == self.head:
                    break
        print(" -> ".join(map(str, nodes)))

# Example Usage
circular_list = CircularSinglyLinkedList()
circular_list.append(1)
circular_list.append(2)
circular_list.append(3)
circular_list.display()

Explanation

  • Node Class: Represents a single node in the list.
  • CircularSinglyLinkedList Class: Manages the circular singly linked list.
    • append(data): Adds a new node to the end of the list.
    • display(): Prints the elements of the list in a circular manner.

Circular Doubly Linked List

Structure

Node1 <-> Node2 <-> Node3 <-> Node1

Implementation in Python

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

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

    def append(self, data):
        new_node = Node(data)
        if not self.head:
            self.head = new_node
            self.head.next = self.head
            self.head.prev = self.head
        else:
            tail = self.head.prev
            tail.next = new_node
            new_node.prev = tail
            new_node.next = self.head
            self.head.prev = new_node

    def display(self):
        nodes = []
        current = self.head
        if self.head:
            while True:
                nodes.append(current.data)
                current = current.next
                if current == self.head:
                    break
        print(" <-> ".join(map(str, nodes)))

# Example Usage
circular_doubly_list = CircularDoublyLinkedList()
circular_doubly_list.append(1)
circular_doubly_list.append(2)
circular_doubly_list.append(3)
circular_doubly_list.display()

Explanation

  • Node Class: Represents a single node in the list with pointers to both the next and previous nodes.
  • CircularDoublyLinkedList Class: Manages the circular doubly linked list.
    • append(data): Adds a new node to the end of the list.
    • display(): Prints the elements of the list in a circular manner.

Practical Exercises

Exercise 1: Insert a Node at the Beginning

Task: Implement a method to insert a node at the beginning of a circular singly linked list.

class CircularSinglyLinkedList:
    # ... (existing methods)

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

# Example Usage
circular_list = CircularSinglyLinkedList()
circular_list.append(2)
circular_list.append(3)
circular_list.insert_at_beginning(1)
circular_list.display()

Solution Explanation

  • insert_at_beginning(data): Adds a new node at the beginning of the list.
    • If the list is empty, the new node becomes the head and points to itself.
    • Otherwise, the new node points to the current head, and the last node's next pointer is updated to point to the new head.

Exercise 2: Delete a Node

Task: Implement a method to delete a node with a specific value from a circular doubly linked list.

class CircularDoublyLinkedList:
    # ... (existing methods)

    def delete_node(self, key):
        if self.head:
            current = self.head
            while True:
                if current.data == key:
                    if current.next == current:  # Only one node in the list
                        self.head = None
                    else:
                        current.prev.next = current.next
                        current.next.prev = current.prev
                        if current == self.head:
                            self.head = current.next
                    return
                current = current.next
                if current == self.head:
                    break

# Example Usage
circular_doubly_list = CircularDoublyLinkedList()
circular_doubly_list.append(1)
circular_doubly_list.append(2)
circular_doubly_list.append(3)
circular_doubly_list.delete_node(2)
circular_doubly_list.display()

Solution Explanation

  • delete_node(key): Deletes the node with the specified value.
    • Traverses the list to find the node with the given value.
    • Updates the pointers of the previous and next nodes to bypass the node to be deleted.
    • If the node to be deleted is the head, updates the head pointer.

Conclusion

Circular lists, both singly and doubly linked, offer unique advantages for specific applications requiring cyclic iteration. Understanding their structure and implementation is crucial for leveraging their benefits in appropriate scenarios. The exercises provided reinforce the concepts and help in mastering the manipulation of circular lists.

◄ Previous
◄
Next ►
►
The Project | About Us | Contribute | Donations | License
© Copyright 2024. All rights reserved