Search on Doubly Circular Linked List

by

In this tutorial we will learn writing Algorithm and program to perform the search operation on Doubly Circular Linked List.

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;
  • Defines a structure Node representing an element in the doubly circular linked list.
  • Each Node contains:
    • int data: Holds the actual data (integer value) of the node.
    • struct Node* next: A pointer to the next node in the list.
    • struct Node* prev: A pointer to the previous node in the list.
  • The typedef keyword in C is used to create an alias for a data type. The statement typedef struct Node Node; creates an alias Node for struct Node.

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.

Hope above program and algorithm helped you to understand how to perform search on Doubly Circular Linked List