Search on Doubly Circular Linked List

Searching in a Doubly Circular Linked List means finding whether a particular value (data) exists in the list or not. In this type of list, each node is connected to both its previous and next nodes, and the last node connects back to the first node, forming a circle. We start from the head and move through the list one node at a time until we either find the element or return to the starting point.

Why Searching in Doubly Circular Linked List ?

Searching in a doubly circular linked list is important because it helps us find a particular value stored in the list. In this type of list, each node is connected to both the next and previous nodes, and the last node connects back to the first node, forming a circle. This means we can move forward or backward through the list easily.

Unlike arrays, the list can grow or shrink without worrying about memory space, and we don’t need all elements to be stored in consecutive memory locations. The circular structure is especially useful when we need to keep checking or looping through the list repeatedly, such as in music playlists, task scheduling, or real-time systems, because we can start from any node and traverse the entire list without stopping. Searching allows us to quickly locate a node and use its data for any operation we want, making the list flexible and efficient.

Algorithm to Perform Search on Doubly Circular Linked List

1. Start at the Head:
   • Begin the search from the head node of the list.
2. Check if the List is Empty:
   • If head is NULL, the list is empty. Indicate that the element cannot be found.
3. Traverse the List:
   • Loop through the list starting from the head.
   • For each node, compare the node’s data with the search element.
4. Check for a Match:
   • If a node with the matching data is found, return an indication of success, such as the position of the node or a success message.
5. Handle Circular Nature:
   • If the next node to be checked is the head again, it means the entire list has been traversed. Stop the search.
6. Element Not Found:
   • If the loop completes without finding the element, indicate that the element is not present in the list.

Example

• Given List: A Doubly Circular Linked List containing the elements: 10, 20, 30, 40.
• Search Task: Search for the element 20 and 50 in the list.

Steps

Initial State

• List: head -> [10] <-> [20] <-> [30] <-> [40] <-> back to [10]
• Head: Points to [10]

Step 1: Start at the Head

• Action: Begin the search from the head node of the list (node [10]).

Step 2: Check if the List is Empty

• Check: head is not NULL, so the list is not empty.

Step 3: Traverse the List (Searching for 20)

• Loop Through the List:
  • First Node [10]: Compare [10] with 20. Not a match, move to the next node.
  • Second Node [20]: Compare [20] with 20. It’s a match.
• Check for a Match: Node [20] contains the search element 20.
• Indicate Success: Return success – “Element 20 found at position 2.”

Step 4: Handle Circular Nature (Searching for 50)

• Loop Through the List:
  • Traverse Entire List: Compare each node’s data with 50.
  • Back to Head: Reach node [10] again, completing a full loop.
• Element Not Found: 50 is not found in any node.
• Indicate Failure: Return – “Element 50 not found in the list.”

result

• Outcome: The search for 20 was successful, found at position 2. However, the search for 50 indicated that it’s not present in the list.

C Program for Searching an Element in a Doubly Circular Linked List

#include <stdio.h>
#include <stdlib.h>

struct Node {
    int data;
    struct Node *next;
    struct Node *prev;
}; 

typedef struct Node Node;

// Create a new node
Node* createNode(int data) {
    Node* newNode = (Node*)malloc(sizeof(Node));
    newNode->data = data;
    newNode->next = newNode;
    newNode->prev = newNode;
    return newNode;
}

// Insert at the End of the Doubly Circular Linked List
void insertAtEnd(Node** head, int data) {
    Node* newNode = createNode(data);
    if (*head == NULL) {
        *head = newNode;
    } else {
        Node* last = (*head)->prev;
        newNode->next = *head;
        newNode->prev = last;
        last->next = (*head)->prev = newNode;
    }
}

// Search for an element in Doubly Circular Linked List
int searchElementInDCLL(Node* head, int element) {
    if (!head) {
        printf("Doubly Circular Linked List is empty.\n");
        return -1;
    }
    Node* temp = head;
    int position = 1;
    do {
        if (temp->data == element) {
            printf("Given element %d found at position %d.\n", element, position);
            return position;
        }
        temp = temp->next;
        position++;
    } while (temp != head);
    printf("Given element %d not found in the list.\n", element);
    return -1;
}

int main() {
    Node* head = NULL;
    insertAtEnd(&head, 10);
    insertAtEnd(&head, 20);
    insertAtEnd(&head, 30);
    insertAtEnd(&head, 40);
    insertAtEnd(&head, 50);
    insertAtEnd(&head, 60);
    // Search for an element
    searchElementInDCLL(head, 20);
    searchElementInDCLL(head, 40);
    searchElementInDCLL(head, 70);
    return 0;
}

Output

Given element 20 found at position 2.
Given element 40 found at position 4.
Given element 70 not found in the list.

Explanation of above program

Node Structure Definition

struct Node {
    int data;
    struct Node *next;
    struct Node *prev;
}; 

typedef struct Node Node;

• Purpose: Creates a new node with the given data.
• Process:
  • Sets both the next and prev pointers to point to the node itself, ensuring the circular structure is maintained when the node is alone in the list.
  • Allocates memory dynamically for a new node.
  • Initializes the node’s data field with the given value

Function: createNode

// Create a new node
Node* createNode(int data) {
    Node* newNode = (Node*)malloc(sizeof(Node));
    newNode->data = data;
    newNode->next = newNode;
    newNode->prev = newNode;
    return newNode;
}

• Purpose: Creates a new node with the given data.
• Process:
  • Allocates memory for a new node.
  • Initializes the node’s data field with the provided value.
  • Sets the next and prev pointers to point to the node itself (important for maintaining the circular structure, especially when the node is the only one in the list).

Function: insertAtEnd

// Insert at the End of the Doubly Circular Linked List
void insertAtEnd(Node** head, int data) {
    Node* newNode = createNode(data);
    if (*head == NULL) {
        *head = newNode;
    } else {
        Node* last = (*head)->prev;
        newNode->next = *head;
        newNode->prev = last;
        last->next = (*head)->prev = newNode;
    }
}

• Purpose: Inserts a new node at the end of the doubly circular linked list.
• Process:
  • If the list (head) is empty, the new node becomes the head.
  • If the list is not empty:
    • Finds the last node (current tail, which is head->prev).
    • Inserts the new node between the last node and the head, updating the next and prev pointers accordingly.
    • Ensures that the list remains circular and doubly linked.

Function: searchElementInDCLL

// Search for an element in Doubly Circular Linked List
int searchElementInDCLL(Node* head, int element) {
    if (!head) {
        printf("Doubly Circular Linked List is empty.\n");
        return -1;
    }
    Node* temp = head;
    int position = 1;
    do {
        if (temp->data == element) {
            printf("Given element %d found at position %d.\n", element, position);
            return position;
        }
        temp = temp->next;
        position++;
    } while (temp != head);
    printf("Given element %d not found in the list.\n", element);
    return -1;
}

• Purpose: Searches for an element in the list.
• Process:
  • Starts from the head and iterates through the list.
  • Compares each node’s data with the given element.
  • If a match is found, prints the position of the element and returns its position.
  • If the entire list is traversed (indicated by reaching the head again) and the element is not found, prints a message indicating the element is not in the list.

Main Function

int main() {
    Node* head = NULL;
    insertAtEnd(&head, 10);
    insertAtEnd(&head, 20);
    insertAtEnd(&head, 30);
    insertAtEnd(&head, 40);
    insertAtEnd(&head, 50);
    insertAtEnd(&head, 60);
    // Search for an element
    searchElementInDCLL(head, 20);
    searchElementInDCLL(head, 40);
    searchElementInDCLL(head, 70);
    return 0;
}

• Purpose: Demonstrates how to use the defined functions.
• Process:
  • Initializes an empty list (head = NULL).
  • Inserts several elements at the end of the list.
  • Searches for specific elements (20, 40, and a non-existent element 70) to demonstrate the search functionality.

Time & Space Complexity

Time Complexity

Space Complexity