INTRODUCTION OF CIRCULAR LINK LIST

 INTRODUCTION OF CIRCULAR LINK LIST

A circular linked list is a variation of a linear linked list in which the last node points back to the first node instead of containing a null reference called a circular structure.

Each node has a link or a pointer to the next node in the sequence, and the last node points back to the first node.

 

Key characteristics of a circular linked list:

1. Circular Structure:

   - Unlike a linear linked list, where the last node points to null, in a circular linked list, the last node's link points back to the first node, creating a loop or cycle.

 

2. Traversal:

   - Traversal in a circular linked list involves starting from any node and moving through the nodes sequentially until reaching the starting node again. The loop continues indefinitely.

 

3. Insertions and Deletions:

   - Insertions and deletions in a circular linked list are similar to those in a linear linked list. However, special care is needed to update the link of the last node when inserting or deleting nodes.

 

4. Representation:

   - A circular linked list can be represented using a structure or a class that contains a data field and a link or pointer field pointing to the next node in the sequence.

 

5. Head Pointer:

   - In a circular linked list, the concept of a "head" is not as strictly defined as in a linear linked list. Any node can serve as a starting point for traversal.

 

6. Applications:

   - Circular linked lists are used in applications where cyclic behavior is natural, such as in round-robin scheduling algorithms, where tasks are performed in a circular sequence.

-----------------------------------------------------------------------

 Structure of a Circular linked Node:

Algorithm: CircularLinkedListNode

1. Create a structure/class for the node:

   - Define a structure/class named Node.

   - Include two fields: data (to store the value of the node) and next (a reference to the next node).

 

2. Initialize a node:

   - Create a function/method named createCircularNode(data) that takes the data for the node as a parameter.

   - Inside the function:

      - Create a new node.

      - Set the data field of the node to the provided data.

      - Set the next field to point to the node itself.

 

   Example (in Python):

   class Node:

       def __init__(self, data):

           self.data = data

           self.next = self  # Initialize next to point to itself

 

   def createCircularNode(data):

       return Node(data)

 

example:- (c++)

struct Node {

    int data;

    Node* next;

};

 

 Operations on Circular Linked List:

Insertion: The insertion operation can be performed in three ways.

·         Inserting At the Beginning of the list

·         Inserting at the end of the list

·         Inserting a specific location in the list

 

Deletion: The deletion operation can be performed in three ways.

They are as follows…

·         Deleting from the Beginning of the list

·         Deleting from the End of the list

·         Deleting a Specific Node

 

Search: It is a process of determining and retrieving a specific node either from the front, the end or anywhere in the list.

 Display: This process displays the elements of a Single-linked list.

 Updating: -

 

Detailed

 Insertion

Algorithm of Insertion at the beginning of the circular link list.

To insert a node at the beginning of a circular linked list, you need to follow these steps:

1. Create a new node with the given data.

2. If the circular linked list is empty, set the next pointer of the new node to itself.

3. If the circular linked list is not empty, find the last node in the list.

4. Set the next pointer of the last node to the new node.

5. Set the next pointer of the new node to the head of the circular linked list.

 

pseudocode:

Algorithm insertAtBeginningCircularLinkedList(data):

    1. Create a new node newNode with the given data.

    2. If the head is NULL (indicating an empty circular linked list):

        2.1 Set newNode.next to newNode (pointing to itself).

        2.2 Set head to newNode.

    3. Else (circular linked list is not empty):

        3.1 Find the last node in the circular linked list. Let's call it lastNode.

        3.2 Set lastNode.next to newNode.

        3.3 Set newNode.next to the head.

        3.4 Set head to newNode.

 

 C++ Example: cpp

#include <iostream>

 

// Node structure

struct Node {

    int data;

    Node* next;

};

 

// Function to insert at the beginning of a circular linked list

Node* insertAtBeginning(Node* head, int data) {

    Node* newNode = new Node;

    newNode->data = data;

    newNode->next = newNode;

 

    if (head == nullptr) {

        head = newNode;

    } else {

        Node* lastNode = head;

        while (lastNode->next != head) {

            lastNode = lastNode->next;

        }

        lastNode->next = newNode;

        newNode->next = head;

        head = newNode;

    }

 

    return head;

}

 

// Function to display the circular linked list

void displayList(Node* head) {

    if (head == nullptr) {

        std::cout << "Circular linked list is empty." << std::endl;

        return;

    }

 

    Node* current = head;

    do {

        std::cout << current->data << " ";

        current = current->next;

    } while (current != head);

 

    std::cout << std::endl;

}

 

int main() {

    Node* head = nullptr;

 

    // Insert at the beginning

    head = insertAtBeginning(head, 3);

    head = insertAtBeginning(head, 2);

    head = insertAtBeginning(head, 1);

 

    // Display the circular linked list

    std::cout << "Circular Linked List: ";

    displayList(head);

 

    return 0;

}

 

Output (C++):

Circular Linked List: 1 2 3

----------------------

 

 Python Example: python

class Node:

    def __init__(self, data):

        self.data = data

        self.next = None

 

# Function to insert at the beginning of a circular linked list

def insert_at_beginning(head, data):

    new_node = Node(data)

    new_node.next = new_node

 

    if head is None:

        head = new_node

    else:

        last_node = head

        while last_node.next != head:

            last_node = last_node.next

        last_node.next = new_node

        new_node.next = head

        head = new_node

 

    return head

 

# Function to display the circular linked list

def display_list(head):

    if head is None:

        print("Circular linked list is empty.")

        return

 

    current = head

    while True:

        print(current.data, end=" ")

        current = current.next

        if current == head:

            break

 

    print()

 

# Main function

if __name__ == "__main__":

    head = None

 

    # Insert at the beginning

    head = insert_at_beginning(head, 3)

    head = insert_at_beginning(head, 2)

    head = insert_at_beginning(head, 1)

 

    # Display the circular linked list

    print("Circular Linked List:", end=" ")

    display_list(head)

 

Output (Python):

Circular Linked List: 1 2 3

------------------------------------------

 

Insert a node at the end of a circular linked list:-


Follow these steps:

1. Create a new node with the given data.

2. If the circular linked list is empty, set the next pointer of the new node to itself and update the head.

3. If the circular linked list is not empty, find the last node in the list.

4. Set the next pointer of the last node to the new node.

5. Set the next pointer of the new node to the head of the circular linked list.

 

pseudocode:

Algorithm insertAtEndCircularLinkedList(data):

    1. Create a new node newNode with the given data.

    2. If head is NULL (indicating an empty circular linked list):

        2.1 Set newNode.next to newNode (pointing to itself).

        2.2 Set head to newNode.

    3. Else (circular linked list is not empty):

        3.1 Find the last node in the circular linked list. Let's call it lastNode.

        3.2 Set lastNode.next to newNode.

        3.3 Set newNode.next to head.

 

 C++ Example:cpp

#include <iostream>

 

// Node structure

struct Node {

    int data;

    Node* next;

};

 

// Function to insert at the end of a circular linked list

Node* insertAtEnd(Node* head, int data) {

    Node* newNode = new Node;

    newNode->data = data;

    newNode->next = newNode;

 

    if (head == nullptr) {

        head = newNode;

    } else {

        Node* lastNode = head;

        while (lastNode->next != head) {

            lastNode = lastNode->next;

        }

        lastNode->next = newNode;

        newNode->next = head;

    }

 

    return head;

}

 

// Function to display the circular linked list

void displayList(Node* head) {

    if (head == nullptr) {

        std::cout << "Circular linked list is empty." << std::endl;

        return;

    }

 

    Node* current = head;

    do {

        std::cout << current->data << " ";

        current = current->next;

    } while (current != head);

 

    std::cout << std::endl;

}

 

int main() {

    Node* head = nullptr;

 

    // Insert at the end

    head = insertAtEnd(head, 1);

    head = insertAtEnd(head, 2);

    head = insertAtEnd(head, 3);

 

    // Display the circular linked list

    std::cout << "Circular Linked List: ";

    displayList(head);

 

    return 0;

}

 

Output (C++):

Circular Linked List: 1 2 3

--------------------------

 

 Python Example: python

class Node:

    def __init__(self, data):

        self.data = data

        self.next = None

 

# Function to insert at the end of a circular linked list

def insert_at_end(head, data):

    new_node = Node(data)

    new_node.next = new_node

 

    if head is None:

        head = new_node

    else:

        last_node = head

        while last_node.next != head:

            last_node = last_node.next

        last_node.next = new_node

        new_node.next = head

 

    return head

 

# Function to display the circular linked list

def display_list(head):

    if head is None:

        print("Circular linked list is empty.")

        return

 

    current = head

    while True:

        print(current.data, end=" ")

        current = current.next

        if current == head:

            break

 

    print()

 

# Main function

if __name__ == "__main__":

    head = None

 

    # Insert at the end

    head = insert_at_end(head, 1)

    head = insert_at_end(head, 2)

    head = insert_at_end(head, 3)

 

    # Display the circular linked list

    print("Circular Linked List:", end=" ")

    display_list(head)

 

Output (Python):

Circular Linked List: 1 2 3

--------------------------------------------------

 

Algorithm of Inserting at Specific location of the list of the circular link list:-


 
To insert a node at a specific location in a circular linked list, you need to follow these steps:

1. Create a new node with the given data.

2. If the specified position is the beginning (position = 1), follow the steps for inserting at the beginning.

3. If the specified position is not the beginning, traverse the list to the node at position - 1.

4. Set the next pointer of the new node to the next node of the current node.

5. Set the next pointer of the current node to the new node.

 

pseudocode:

Algorithm insertAtPositionCircularLinkedList(data, position):

    1. Create a new node newNode with the given data.

    2. If the position is 1:

        2.1 Follow the steps for inserting at the beginning.

    3. Else (position is not 1):

        3.1 Create a variable current and set it to the head of the circular linked list.

        3.2 Traverse the list to the node at position - 1.

        3.3 Set newNode.next to the next node of the current node.

        3.4 Set the next pointer of the current node to the new node.

 

 C++ Example: cpp

#include <iostream>

 

// Node structure

struct Node {

    int data;

    Node* next;

};

 

// Function to insert at a specific position in a circular linked list

Node* insertAtPosition(Node* head, int data, int position) {

    Node* newNode = new Node;

    newNode->data = data;

    newNode->next = newNode;

 

    if (position == 1) {

        // Insert at the beginning

        newNode->next = head;

        head = newNode;

    } else {

        // Insert at the specified position

        Node* current = head;

        for (int i = 1; i < position - 1; ++i) {

            if (current == nullptr) {

                std::cout << "Invalid position." << std::endl;

                return head;

            }

            current = current->next;

        }

 

        newNode->next = current->next;

        current->next = newNode;

    }

 

    return head;

}

 

// Function to display the circular linked list

void displayList(Node* head) {

    if (head == nullptr) {

        std::cout << "Circular linked list is empty." << std::endl;

        return;

    }

 

    Node* current = head;

    do {

        std::cout << current->data << " ";

        current = current->next;

    } while (current != head);

 

    std::cout << std::endl;

}

 

int main() {

    Node* head = nullptr;

 

    // Insert at specific positions

    head = insertAtPosition(head, 1, 1);  // Insert at the beginning

    head = insertAtPosition(head, 3, 2);  // Insert at position 2

    head = insertAtPosition(head, 2, 2);  // Insert at position 2

 

    // Display the circular linked list

    std::cout << "Circular Linked List: ";

    displayList(head);

 

    return 0;

}

 

Output (C++):

Circular Linked List: 1 2 3

-------------------------------

 

 Python Example: python

class Node:

    def __init__(self, data):

        self.data = data

        self.next = None

 

# Function to insert at a specific position in a circular linked list

def insert_at_position(head, data, position):

    new_node = Node(data)

    new_node.next = new_node

 

    if position == 1:

        # Insert at the beginning

        new_node.next = head

        head = new_node

    else:

        # Insert at the specified position

        current = head

        for i in range(1, position - 1):

            if current is None:

                print("Invalid position.")

                return head

            current = current.next

 

        new_node.next = current.next

        current.next = new_node

 

    return head

 

# Function to display the circular linked list

def display_list(head):

    if head is None:

        print("Circular linked list is empty.")

        return

 

    current = head

    while True:

        print(current.data, end=" ")

        current = current.next

        if current == head:

            break

 

    print()

 

# Main function

if __name__ == "__main__":

    head = None

 

    # Insert at specific positions

    head = insert_at_position(head, 1, 1)  # Insert at the beginning

    head = insert_at_position(head, 3, 2)  # Insert at position 2

    head = insert_at_position(head, 2, 2)  # Insert at position 2

 

    # Display the circular linked list

    print("Circular Linked List:", end=" ")

    display_list(head)

 

Output (Python):

Circular Linked List: 1 2 3

---------------------------------------------------------------

Deletion

To delete a node at the beginning of a circular linked list:-

follow these steps:

1. If the circular linked list is empty (head is `nullptr` or `None`), print an error message or handle the empty list case.

2. If the circular linked list is not empty, check if it has only one node. If yes, set head to `nullptr` (for C++) or `None` (for Python).

3. If the circular linked list has more than one node, find the last node and update its `next` pointer to skip the first node.

4. Free the memory of the node to be deleted (optional in some languages like Python).

 

pseudocode:

Algorithm deleteAtBeginningCircularLinkedList():

    1. If head is NULL (indicating an empty circular linked list):

        1.1 Print an error message or handle the empty list case.

    2. Else (circular linked list is not empty):

        2.1 If head.next is equal to head (indicating only one node in the list):

            2.1.1 Set head to NULL (for C++) or None (for Python).

        2.2 Else (more than one node in the list):

            2.2.1 Find the last node in the circular linked list. Let's call it lastNode.

            2.2.2 Set lastNode.next to head.next.

            2.2.3 Free the memory of the node pointed to by head (optional in some languages).

            2.2.4 Set head to head.next.

 

 C++ Example: cpp

#include <iostream>

 

// Node structure

struct Node {

    int data;

    Node* next;

};

 

// Function to delete at the beginning of a circular linked list

Node* deleteAtBeginning(Node* head) {

    if (head == nullptr) {

        std::cout << "Cannot delete from an empty circular linked list." << std::endl;

    } else {

        if (head->next == head) {

            // Only one node in the list

            delete head;

            head = nullptr;

        } else {

            // More than one node in the list

            Node* lastNode = head;

            while (lastNode->next != head) {

                lastNode = lastNode->next;

            }

 

            lastNode->next = head->next;

            Node* temp = head;

            head = head->next;

            delete temp;

        }

    }

 

    return head;

}

 

// Function to display the circular linked list

void displayList(Node* head) {

    if (head == nullptr) {

        std::cout << "Circular linked list is empty." << std::endl;

        return;

    }

 

    Node* current = head;

    do {

        std::cout << current->data << " ";

        current = current->next;

    } while (current != head);

 

    std::cout << std::endl;

}

 

int main() {

    Node* head = nullptr;

 

    // Delete at the beginning

    head = deleteAtBeginning(head);

 

    // Insert some nodes

    head = new Node{1, nullptr};

    head->next = head;

    head = new Node{2, head};

    head = new Node{3, head};

 

    // Display the circular linked list

    std::cout << "Circular Linked List: ";

    displayList(head);

 

    // Delete at the beginning

    head = deleteAtBeginning(head);

 

    // Display the circular linked list after deletion

    std::cout << "Circular Linked List after deletion: ";

    displayList(head);

 

    return 0;

}

 

Output (C++):

Cannot delete from an empty circular linked list.

Circular Linked List: 3 2 1

Circular Linked List after deletion: 2 1

------------------------------------------------

  Python Example: python

class Node:

    def __init__(self, data):

        self.data = data

        self.next = None

 

# Function to delete at the beginning of a circular linked list

def delete_at_beginning(head):

    if head is None:

        print("Cannot delete from an empty circular linked list.")

    else:

        if head.next == head:

            # Only one node in the list

            del head

            head = None

        else:

            # More than one node in the list

            last_node = head

            while last_node.next != head:

                last_node = last_node.next

 

            last_node.next = head.next

            temp = head

            head = head.next

            del temp

 

    return head

 

# Function to display the circular linked list

def display_list(head):

    if head is None:

        print("Circular linked list is empty.")

        return

 

    current = head

    while True:

        print(current.data, end=" ")

        current = current.next

        if current == head:

            break

 

    print()

 

# Main function

if __name__ == "__main__":

    head = None

 

    # Delete at the beginning

    delete_at_beginning(head)

 

    # Insert some nodes

    head = Node(1)

    head.next = head

    head = Node(2, head)

    head = Node(3, head)

 

    # Display the circular linked list

    print("Circular Linked List:", end=" ")

    display_list(head)

 

    # Delete at the beginning

    head = delete_at_beginning(head)

 

    # Display the circular linked list after deletion

    print("Circular Linked List after deletion:", end=" ")

    display_list(head)

 

Output (Python):

Cannot delete from an empty circular linked list.

Circular Linked List: 3 2 1

Circular Linked List after deletion: 2 1

-------------------------------------------------------------

 To delete a node at the end of a circular linked list:-

Follow these steps:

1. If the circular linked list is empty (head is `nullptr` or `None`), print an error message or handle the empty list case.

2. If the circular linked list is not empty, check if it has only one node. If yes, delete the node and set head to `nullptr` (for C++) or `None` (for Python).

3. If the circular linked list has more than one node, find the second-to-last node in the list.

4. Set the `next` pointer of the second-to-last node to the head, making it the new last node.

5. Delete the last node (optional in some languages).

 

pseudocode:

Algorithm deleteAtEndCircularLinkedList():

    1. If head is NULL (indicating an empty circular linked list):

        1.1 Print an error message or handle the empty list case.

    2. Else (circular linked list is not empty):

        2.1 If head.next is equal to head (indicating only one node in the list):

            2.1.1 Delete the node pointed to by head.

            2.1.2 Set head to NULL (for C++) or None (for Python).

        2.2 Else (more than one node in the list):

            2.2.1 Create a variable current and set it to the head of the circular linked list.

            2.2.2 Traverse the list to the second-to-last node. Let's call it secondToLastNode.

            2.2.3 Delete the last node (optional in some languages).

            2.2.4 Set secondToLastNode.next to head.

 

 C++ Example: cpp

#include <iostream>

 

// Node structure

struct Node {

    int data;

    Node* next;

};

 

// Function to delete at the end of a circular linked list

Node* deleteAtEnd(Node* head) {

    if (head == nullptr) {

        std::cout << "Cannot delete from an empty circular linked list." << std::endl;

    } else {

        if (head->next == head) {

            // Only one node in the list

            delete head;

            head = nullptr;

        } else {

            // More than one node in the list

            Node* current = head;

            Node* secondToLastNode = nullptr;

 

            while (current->next != head) {

                secondToLastNode = current;

                current = current->next;

            }

 

            // Delete the last node (optional in some languages)

            delete current;

 

            // Update the second-to-last node's next pointer

            secondToLastNode->next = head;

        }

    }

 

    return head;

}

 

// Function to display the circular linked list

void displayList(Node* head) {

    if (head == nullptr) {

        std::cout << "Circular linked list is empty." << std::endl;

        return;

    }

 

    Node* current = head;

    do {

        std::cout << current->data << " ";

        current = current->next;

    } while (current != head);

 

    std::cout << std::endl;

}

 

int main() {

    Node* head = nullptr;

 

    // Delete at the end

    deleteAtEnd(head);

 

    // Insert some nodes

    head = new Node{1, nullptr};

    head->next = head;

    head = new Node{2, head};

    head = new Node{3, head};

 

    // Display the circular linked list

    std::cout << "Circular Linked List: ";

    displayList(head);

 

    // Delete at the end

    head = deleteAtEnd(head);

 

    // Display the circular linked list after deletion

    std::cout << "Circular Linked List after deletion: ";

    displayList(head);

 

    return 0;

}

 

Output (C++):

Cannot delete from an empty circular linked list.

Circular Linked List: 3 2 1

Circular Linked List after deletion: 3 2

---------------------------------

 

 Python Example: python

class Node:

    def __init__(self, data):

        self.data = data

        self.next = None

 

# Function to delete at the end of a circular linked list

def delete_at_end(head):

    if head is None:

        print("Cannot delete from an empty circular linked list.")

    else:

        if head.next == head:

            # Only one node in the list

            del head

            head = None

        else:

            # More than one node in the list

            current = head

            second_to_last_node = None

 

            while current.next != head:

                second_to_last_node = current

                current = current.next

 

            # Delete the last node (optional in some languages)

            del current

 

            # Update the second-to-last node's next pointer

            second_to_last_node.next = head

 

    return head

 

# Function to display the circular linked list

def display_list(head):

    if head is None:

        print("Circular linked list is empty.")

        return

 

    current = head

    while True:

        print(current.data, end=" ")

        current = current.next

        if current == head:

            break

 

    print()

 

# Main function

if __name__ == "__main__":

    head = None

 

    # Delete at the end

    delete_at_end(head)

 

    # Insert some nodes

    head = Node(1)

    head.next = head

    head = Node(2, head)

    head = Node(3, head)

 

    # Display the circular linked list

    print("Circular Linked List:", end=" ")

    display_list(head)

 

    # Delete at the end

    head = delete_at_end(head)

 

    # Display the circular linked list after deletion

    print("Circular Linked List after deletion:", end=" ")

    display_list(head)

 

Output (Python):

Cannot delete from an empty circular linked list.

Circular Linked List: 3 2 1

Circular Linked List after deletion: 3 2

---------------------------------------------------------

 

To delete a node at a specific position in a circular linked list,

Follow these steps:

1. If the circular linked list is empty (head is `nullptr` or `None`), print an error message or handle the empty list case.

2. If the circular linked list is not empty, check if the specified position is valid (greater than 0 and less than or equal to the length of the list).

3. If the specified position is 1, it is equivalent to deleting at the beginning, so follow the steps for deleting at the beginning.

4. If the specified position is not 1, traverse the list to the node at position - 1.

5. Save the reference to the node to be deleted (current->next).

6. Set the next pointer of the current node to skip the node to be deleted.

7. Free the memory of the node to be deleted (optional in some languages).

 

pseudocode:

Algorithm deleteAtPositionCircularLinkedList(position):

    1. If head is NULL (indicating an empty circular linked list):

        1.1 Print an error message or handle the empty list case.

    2. Else (circular linked list is not empty):

        2.1 Check if the specified position is valid (greater than 0 and less than or equal to the length of the list).

        2.2 If position is 1:

            2.2.1 Follow the steps for deleting at the beginning.

        2.3 Else (position is not 1):

            2.3.1 Create a variable current and set it to the head of the circular linked list.

            2.3.2 Traverse the list to the node at position - 1. Let's call it currentNode.

            2.3.3 Save the reference to the node to be deleted (tempNode = currentNode.next).

            2.3.4 Set currentNode.next to tempNode.next.

            2.3.5 Free the memory of the node pointed to by tempNode (optional in some languages).

 

C++ Example: cpp

#include <iostream>

 

// Node structure

struct Node {

    int data;

    Node* next;

};

 

// Function to delete at a specific position in a circular linked list

Node* deleteAtPosition(Node* head, int position) {

    if (head == nullptr) {

        std::cout << "Cannot delete from an empty circular linked list." << std::endl;

    } else {

        int length = 1;

        Node* current = head;

        while (current->next != head) {

            length++;

            current = current->next;

        }

 

        if (position < 1 || position > length) {

            std::cout << "Invalid position." << std::endl;

        } else {

            if (position == 1) {

                // Deleting at the beginning

                Node* lastNode = head;

                while (lastNode->next != head) {

                    lastNode = lastNode->next;

                }

                Node* temp = head;

                head = head->next;

                lastNode->next = head;

                delete temp;

            } else {

                // Deleting at the specified position

                Node* currentNode = head;

                for (int i = 1; i < position - 1; ++i) {

                    currentNode = currentNode->next;

                }

                Node* tempNode = currentNode->next;

                currentNode->next = tempNode->next;

                delete tempNode;

            }

        }

    }

 

    return head;

}

 

// Function to display the circular linked list

void displayList(Node* head) {

    if (head == nullptr) {

        std::cout << "Circular linked list is empty." << std::endl;

        return;

    }

 

    Node* current = head;

    do {

        std::cout << current->data << " ";

        current = current->next;

    } while (current != head);

 

    std::cout << std::endl;

}

 

int main() {

    Node* head = nullptr;

 

    // Delete at a specific position

    deleteAtPosition(head, 3);

 

    // Insert some nodes

    head = new Node{1, nullptr};

    head->next = head;

    head = new Node{2, head};

    head = new Node{3, head};

 

    // Display the circular linked list

    std::cout << "Circular Linked List: ";

    displayList(head);

 

    // Delete at a specific position

    head = deleteAtPosition(head, 2);

 

    // Display the circular linked list after deletion

    std::cout << "Circular Linked List after deletion: ";

    displayList(head);

 

    return 0;

}

 

Output (C++):

Cannot delete from an empty circular linked list.

Circular Linked List: 3 2 1

Circular Linked List after deletion: 3 1

-------------------------------

 

 Python Example: python

class Node:

    def __init__(self, data):

        self.data = data

        self.next = None

 

# Function to insert a node at the end of a circular linked list

def insert_at_end_circular_linked_list(head, data):

    new_node = Node(data)

    if head is None:

        head = new_node

        new_node.next = head

    else:

        current = head

        while current.next != head:

            current = current.next

        current.next = new_node

        new_node.next = head

    return head

 

# Function to delete a node at a specific location in a circular linked list

def delete_at_specific_location_circular_linked_list(head, position):

    if head is None:

        print("Circular linked list is empty.")

        return None

 

    if position < 1:

        print("Invalid position.")

        return head

 

    current = head

 

    if position == 1:

        last_node = head

        while last_node.next != head:

            last_node = last_node.next

 

        last_node.next = current.next

        if current.next == head:

            head = last_node.next

 

        del current

    else:

        for _ in range(position - 2):

            current = current.next

 

        temp_node = current.next

        current.next = temp_node.next

        del temp_node

 

    return head

 

# Function to display the circular linked list

def display_circular_linked_list(head):

    if head is None:

        print("Circular linked list is empty.")

        return

 

    current = head

    while True:

        print(current.data, end=" ")

        current = current.next

        if current == head:

            break

 

    print()

 

# Main function

if __name__ == "__main__":

    head = None

 

    # Insert some nodes into the circular linked list

    head = insert_at_end_circular_linked_list(head, 1)

    head = insert_at_end_circular_linked_list(head, 2)

    head = insert_at_end_circular_linked_list(head, 3)

    head = insert_at_end_circular_linked_list(head, 4)

 

    # Display the circular linked list before deletion

    print("Circular Linked List before deletion:")

    display_circular_linked_list(head)

 

    # Delete a node at a specific location

    position_to_delete = 2

    head = delete_at_specific_location_circular_linked_list(head, position_to_delete)

 

    # Display the circular linked list after deletion

    print("\nCircular Linked List after deletion at position", position_to_delete, ":")

    display_circular_linked_list(head)

 

output:-

Circular Linked List before deletion:

1 2 3 4

 

Circular Linked List after deletion at position 2 :

1 3 4

--------------------------------------------------------------------------

 

To traverse a circular linked list:-

Use a loop to iterate through the nodes, starting from the head, until you reach the head again.

 

pseudocode:

Algorithm traverseCircularLinkedList():

    1. If head is NULL (indicating an empty circular linked list):

        1.1 Print a message indicating that the circular linked list is empty.

    2. Else (circular linked list is not empty):

        2.1 Create a variable current and set it to the head of the circular linked list.

        2.2 Repeat the following steps until current reaches the head again:

            2.2.1 Process the data of the current node.

            2.2.2 Move to the next node (current = current.next).

 

 C++ Example:cpp

#include <iostream>

 

// Node structure

struct Node {

    int data;

    Node* next;

};

 

// Function to traverse a circular linked list

void traverseCircularLinkedList(Node* head) {

    if (head == nullptr) {

        std::cout << "Circular linked list is empty." << std::endl;

    } else {

        Node* current = head;

        do {

            // Process the data of the current node

            std::cout << current->data << " ";

            // Move to the next node

            current = current->next;

        } while (current != head);

 

        std::cout << std::endl;

    }

}

 

int main() {

    Node* head = nullptr;

 

    // Insert some nodes

    head = new Node{1, nullptr};

    head->next = head;

    head = new Node{2, head};

    head = new Node{3, head};

 

    // Display the circular linked list by traversing it

    std::cout << "Traversing Circular Linked List: ";

    traverseCircularLinkedList(head);

 

    return 0;

}

 

Output (C++):

Traversing Circular Linked List: 3 2 1

----------------------------

 

 Python Example: python

class Node:

    def __init__(self, data):

        self.data = data

        self.next = None

 

# Function to traverse a circular linked list

def traverse_circular_linked_list(head):

    if head is None:

        print("Circular linked list is empty.")

    else:

        current = head

        while True:

            # Process the data of the current node

            print(current.data, end=" ")

            # Move to the next node

            current = current.next

            # Check if we have traversed the entire circular linked list

            if current == head:

                break

 

        print()

 

# Main function

if __name__ == "__main__":

    head = None

 

    # Insert some nodes

    head = Node(1)

    head.next = head

    head = Node(2, head)

    head = Node(3, head)

 

    # Display the circular linked list by traversing it

    print("Traversing Circular Linked List:", end=" ")

    traverse_circular_linked_list(head)

 

Output (Python):

Traversing Circular Linked List: 3 2 1

 

============================================

Updating in the circular link list:-

To update a node in a circular linked list, you need to traverse the list and find the node with the target value. Once found, you can update its data.

 

pseudocode:

Algorithm updateCircularLinkedList(target, newData):

    1. If head is NULL (indicating an empty circular linked list):

        1.1 Print a message indicating that the circular linked list is empty.

    2. Create a variable current and set it to the head of the circular linked list.

    3. Repeat the following steps until current reaches the head again:

        3.1 If the data of the current node is equal to the target:

            3.1.1 Update the data of the current node to newData.

            3.1.2 Print a message indicating that the update is successful.

            3.1.3 Return true or an appropriate indication that the update is successful.

        3.2 Move to the next node (current = current.next).

    4. Print a message indicating that the target is not found.

    5. Return false or an appropriate indication that the update is unsuccessful.

 

C++ Example:cpp

#include <iostream>

 

// Node structure

struct Node {

    int data;

    Node* next;

};

 

// Function to update a node in a circular linked list

bool updateCircularLinkedList(Node* head, int target, int newData) {

    if (head == nullptr) {

        std::cout << "Circular linked list is empty. Update unsuccessful." << std::endl;

        return false;

    }

 

    Node* current = head;

    do {

        if (current->data == target) {

            // Update the data of the current node to newData

            current->data = newData;

            std::cout << "Update successful. New data at target: " << newData << std::endl;

            return true;

        }

        current = current->next;

    } while (current != head);

 

    std::cout << "Target " << target << " not found. Update unsuccessful." << std::endl;

    return false;

}

 

int main() {

    Node* head = nullptr;

 

    // Insert some nodes

    head = new Node{1, nullptr};

    head->next = head;

    head = new Node{2, head};

    head = new Node{3, head};

 

    // Update a node in the circular linked list

    updateCircularLinkedList(head, 2, 4);  // Update successful

    updateCircularLinkedList(head, 5, 6);  // Target not found, update unsuccessful

 

    return 0;

}

 

Output (C++):

Update successful. New data at target: 4

Target 5 not found. Update unsuccessful.

----------------------------

 

 Python Example: python

Update successful. New data at target: 4

Target 5 not found. Update unsuccessful.

 

class Node:

    def __init__(self, data):

        self.data = data

        self.next = None

 

# Function to insert a node at the end of a circular linked list

def insert_at_end_circular_linked_list(head, data):

    new_node = Node(data)

    if head is None:

        head = new_node

        new_node.next = head

    else:

        current = head

        while current.next != head:

            current = current.next

        current.next = new_node

        new_node.next = head

    return head

 

# Function to update a node at a specific location in a circular linked list

def update_at_specific_location_circular_linked_list(head, position, new_data):

    if head is None:

        print("Circular linked list is empty.")

        return None

 

    if position < 1:

        print("Invalid position.")

        return head

 

    current = head

 

    for _ in range(position - 1):

        current = current.next

 

    current.data = new_data

 

    return head

 

# Function to display the circular linked list

def display_circular_linked_list(head):

    if head is None:

        print("Circular linked list is empty.")

        return

 

    current = head

    while True:

        print(current.data, end=" ")

        current = current.next

        if current == head:

            break

 

    print()

 

# Main function

if __name__ == "__main__":

    head = None

 

    # Insert some nodes into the circular linked list

    head = insert_at_end_circular_linked_list(head, 1)

    head = insert_at_end_circular_linked_list(head, 2)

    head = insert_at_end_circular_linked_list(head, 3)

    head = insert_at_end_circular_linked_list(head, 4)

 

    # Display the circular linked list before update

    print("Circular Linked List before update:")

    display_circular_linked_list(head)

 

    # Update a node at a specific location

    position_to_update = 2

    new_data = 10

    head = update_at_specific_location_circular_linked_list(head, position_to_update, new_data)

 

    # Display the circular linked list after update

    print("\nCircular Linked List after updating at position", position_to_update, ":")

    display_circular_linked_list(head)

 

output:-

Circular Linked List before update:

1 2 3 4

 

Circular Linked List after updating at position 2 :

1 10 3 4

 

Both examples demonstrate updating a node in a circular linked list and print whether the update is successful or not.

--------------------------------------------------------------------------------

 

Complete operation example:-

examples to include insertion, deletion, traversing, searching, and updating operations.

 

C++ Example:

#include <iostream>

 

using namespace std;

 

class Node {

public:

    int data;

    Node* next;

 

    Node(int value) {

        data = value;

        next = nullptr;

    }

};

 

class CircularLinkedList {

private:

    Node* head;

 

public:

    CircularLinkedList() {

        head = nullptr;

    }

 

    void insert(int value) {

        Node* newNode = new Node(value);

        if (!head) {

            head = newNode;

            head->next = head;

        } else {

            Node* temp = head;

            while (temp->next != head) {

                temp = temp->next;

            }

            temp->next = newNode;

            newNode->next = head;

        }

    }

 

    void deleteNode(int value) {

        if (!head) {

            cout << "List is empty. Cannot delete.\n";

            return;

        }

 

        Node* temp = head;

        Node* prev = nullptr;

 

        while (temp->data != value && temp->next != head) {

            prev = temp;

            temp = temp->next;

        }

 

        if (temp->data != value) {

            cout << "Node with value " << value << " not found.\n";

            return;

        }

 

        if (temp == head && temp->next == head) {

            delete temp;

            head = nullptr;

        } else if (temp == head) {

            prev = head;

            while (prev->next != head) {

                prev = prev->next;

            }

            prev->next = head->next;

            delete head;

            head = prev->next;

        } else {

            prev->next = temp->next;

            delete temp;

        }

    }

 

    void traverse() {

        if (!head) {

            cout << "List is empty.\n";

            return;

        }

 

        Node* temp = head;

 

        do {

            cout << temp->data << " ";

            temp = temp->next;

        } while (temp != head);

 

        cout << endl;

    }

 

    bool search(int value) {

        if (!head) {

            cout << "List is empty.\n";

            return false;

        }

 

        Node* temp = head;

 

        do {

            if (temp->data == value) {

                cout << "Node with value " << value << " found.\n";

                return true;

            }

            temp = temp->next;

        } while (temp != head);

 

        cout << "Node with value " << value << " not found.\n";

        return false;

    }

 

    void update(int oldValue, int newValue) {

        if (!head) {

            cout << "List is empty.\n";

            return;

        }

 

        Node* temp = head;

 

        do {

            if (temp->data == oldValue) {

                temp->data = newValue;

                cout << "Node updated successfully.\n";

                return;

            }

            temp = temp->next;

        } while (temp != head);

 

        cout << "Node with value " << oldValue << " not found. Update failed.\n";

    }

};

 

int main() {

    CircularLinkedList myList;

 

    myList.insert(1);

    myList.insert(2);

    myList.insert(3);

 

    cout << "Circular Linked List: ";

    myList.traverse();

 

    myList.search(2);

 

    myList.update(2, 4);

 

    cout << "After updating node with value 2 to 4: ";

    myList.traverse();

 

    myList.deleteNode(4);

 

    cout << "After deleting node with value 4: ";

    myList.traverse();

 

    return 0;

}

---------------------------------------------------

 

Python Example:

class Node:

    def __init__(self, data):

        self.data = data

        self.next = None

 

class CircularLinkedList:

    def __init__(self):

        self.head = None

 

    def insert(self, value):

        new_node = Node(value)

        if not self.head:

            self.head = new_node

            self.head.next = self.head

        else:

            temp = self.head

            while temp.next != self.head:

                temp = temp.next

            temp.next = new_node

            new_node.next = self.head

 

    def delete_node(self, value):

        if not self.head:

            print("List is empty. Cannot delete.")

            return

 

        temp = self.head

        prev = None

 

        while temp.data != value and temp.next != self.head:

            prev = temp

            temp = temp.next

 

        if temp.data != value:

            print(f"Node with value {value} not found.")

            return

 

        if temp == self.head and temp.next == self.head:

            del temp

            self.head = None

        elif temp == self.head:

            prev = self.head

            while prev.next != self.head:

                prev = prev.next

            prev.next = self.head.next

            del self.head

            self.head = prev.next

        else:

            prev.next = temp.next

            del temp

 

    def traverse(self):

        if not self.head:

            print("List is empty.")

            return

 

        temp = self.head

 

        while True:

            print(temp.data, end=" ")

            temp = temp.next

            if temp == self.head:

                break

 

        print()

 

    def search(self, value):

        if not self.head:

            print("List is empty.")

            return False

 

        temp = self.head

 

        while True:

            if temp.data == value:

                print(f"Node with value {value} found.")

                return True

            temp = temp.next

            if temp == self.head:

                break

 

        print(f"Node with value {value} not found.")

        return False

 

    def update(self, old_value, new_value):

        if not self.head:

            print("List is empty.")

            return

 

        temp = self.head

 

        while True:

            if temp.data == old_value:

                temp.data = new_value

                print("Node updated successfully.")

                return

            temp = temp.next

            if temp == self.head:

                break

 

        print(f"Node with value {old_value} not found. Update failed.")

 

# Example usage

my_list = CircularLinkedList()

 

my_list.insert(1)

my_list.insert(2)

my_list.insert(3)

 

print("Circular Linked List:", end=" ")

my_list.traverse()

 

my_list.search(2)

 

my_list.update(2, 4)

 

print("After updating node with value 2 to 4:", end=" ")

my_list.traverse()

 

my_list.delete_node(4)

 

print("After deleting node with value 4:", end=" ")

my_list.traverse()

 

Output:-

Circular Linked List: 1 2 3

Node with value 2 found.

Node updated successfully.

After updating node with value 2 to 4: 1 4 3

After deleting node with value 4: 1 3

------------------------------------------------------------------------------

 

Advantage of circular link list

Circular linked lists offer several advantages in certain scenarios, and their characteristics make them suitable for specific applications.

Some advantages of circular linked lists:

1. Efficient Insertion and Deletion at the Beginning:

   - Insertion and deletion at the beginning of a circular linked list can be done in constant time. This makes circular linked lists efficient for operations that involve frequent insertions and deletions at the front.

 

2. Circular Nature:

   - The circular structure naturally supports operations that involve cycling through a set of elements. For example, in applications like round-robin scheduling, a circular linked list can be used to represent a queue of tasks.

 

3. Memory Utilization:

   - Circular linked lists can be more memory-efficient than arrays or linear linked lists in certain scenarios. They allow for dynamic memory allocation and deallocation as elements are added or removed.

 

4. Implementation of Circular Buffers:

   - Circular linked lists can be used to implement circular buffers, which are useful in scenarios where data needs to be continuously cycled and overwritten.

 

5. Support for Circular Operations:

   - Algorithms or applications that involve circular operations, such as cyclic rotations or circular lists, can be naturally represented using circular linked lists.

 

6. Implementation of Circular Navigation:

   - Circular linked lists are suitable for implementing circular navigation structures, like menus or slideshows, where the navigation loops back to the beginning after reaching the end.

 

7. Simplifies Certain Algorithms:

   - Some algorithms, especially those that involve cyclic patterns or periodic behavior, can be simplified and more elegantly expressed using circular linked lists.

 

8. Dynamic Size Adjustment:

   - Circular linked lists can easily accommodate dynamic changes in size. Elements can be added or removed without the need to resize the data structure, which is particularly beneficial in scenarios where the size is unpredictable.

 

9. Implementation of Circular Queues:

   - Circular linked lists can be used to implement circular queues, where elements are enqueued at one end and dequeued at the other end. This is common in scenarios like task scheduling.

 

10. Applications with Natural Circular Behaviour:

    - In certain applications, the nature of the data or the operations naturally exhibits circular behavior. Circular linked lists provide a more intuitive representation in such cases.

---------------------------

 

Disadvantage of circular link list

Some disadvantages of circular linked lists:

 

1. Complexity in Traversal:

   - Traversal of a circular linked list can be more complex than that of a linear linked list. It requires careful handling to avoid infinite loops, especially if there are errors in the logic of traversal.

 

2. Difficulty in Detecting the End:

   - Determining the end of a circular linked list can be challenging. Unlike linear linked lists where a `nullptr` (null reference) signifies the end, circular linked lists do not have a clear termination point. Special techniques or sentinel nodes may be required.

 

3. Increased Complexity in Operations:

   - Certain operations, such as finding the middle element or reversing the list, can be more complex in a circular linked list compared to a linear linked list.

 

4. Additional Memory Overhead:

   - The circular nature of the list requires an extra link or pointer field in each node to form the loop. This additional memory overhead can be a consideration when memory usage is a critical factor.

 

5. Complex Initialization and Termination:

   - Initializing and terminating a circular linked list requires special attention to ensure that the last node correctly points back to the first node during initialization and is properly disconnected during termination.

 

6. Increased Code Complexity:

   - Implementing operations on a circular linked list often involves more intricate code compared to linear linked lists. This increased complexity can lead to a higher likelihood of errors and may make the code harder to maintain.

 

7. Limited Support for Random Access:

   - Circular linked lists do not support direct random access to elements based on an index, as indexing is not straightforward in a circular structure. Accessing elements in a circular linked list may require traversing the list, leading to higher time complexity.

 

8. Difficulty in Reversing:

   - Reversing a circular linked list is a non-trivial task and typically requires special handling to maintain the circular structure while reversing the direction of links.

 

9. Algorithmic Challenges:

   - Some algorithms that work efficiently on linear structures may require modification to work correctly on circular linked lists. Adapting standard algorithms to circular structures may introduce additional complexity.

 

10. Limited Use Cases:

    - Circular linked lists are not suitable for all scenarios. In many cases, linear linked lists or arrays may be more straightforward to use and better meet the requirements of the application.

----------------------------

 Applications of circular link list

Circular linked lists find applications in various scenarios where their unique properties are advantageous. Some common applications of circular linked lists:

 1. Round-Robin Scheduling:

   - Circular linked lists are used in operating systems for implementing round-robin scheduling algorithms. In round-robin scheduling, tasks are assigned a fixed time slice, and the scheduler cycles through the tasks in a circular manner.

 2. Music Player Playlist:

   - Circular linked lists can be used to implement playlists in music players. The last song in the playlist points to the first, creating a loop that allows continuous playback.

 3. Image Slideshow:

   - Circular linked lists are suitable for implementing image slideshows or presentations where the display loops back to the beginning after reaching the last image.

 4. Game Development:

   - In game development, circular linked lists can be employed to represent cycles or loops in the game logic, such as the movement of characters or the rotation of objects.

 5. Managing Resources in a Circular Manner:

   - Circular linked lists are used in resource management scenarios where resources are allocated in a circular manner. For example, in a pool of resources, once the last resource is reached, the allocation cycles back to the first resource.

 6. Circular Queues:

   - Circular linked lists are employed in the implementation of circular queues. In data structures, circular queues efficiently handle scenarios where elements need to be enqueued and dequeued in a circular fashion.

 7. Cyclic Structures in Algorithms:

   - Algorithms that involve cyclic or periodic behavior can be naturally represented using circular linked lists. Examples include algorithms that perform cyclic rotations or maintain cyclic patterns.

 8. Simulation Systems:

   - In simulations, circular linked lists can model cyclic processes or events. For instance, in a simulation of a traffic signal, the states of the signal lights can be organized in a circular linked list.

 9. Clockwise and Anticlockwise Navigation:

   - Circular linked lists are used in applications that involve navigation in a circular manner. This can include clockwise or anticlockwise navigation through a set of elements.

 10. Implementing Circular Buffers:

    - Circular linked lists can be employed to implement circular buffers, which are useful in scenarios where data needs to be continuously cycled and overwritten, such as in streaming applications.

 11. Data Structures with Wrap-Around Behaviour:

    - Circular linked lists are suitable for scenarios where a data structure needs to exhibit wrap-around behavior, such as in cyclic buffer implementations or circular stacks.

 

12. Managing System Resources:

    - Circular linked lists can be used in resource management systems where a set of resources needs to be allocated cyclically, ensuring fair usage.

======================================================= 

 





Post a Comment

0 Comments