# Search on Doubly Circular Linked List

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

• 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.
• 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);
} else {
newNode->prev = last;
}
}

// Search for an element in Doubly Circular Linked List
int searchElementInDCLL(Node* head, int element) {
printf("Doubly Circular Linked List is empty.\n");
return -1;
}
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++;
return -1;
}

int main() {
// Search for an element
return 0;
}
``````

Output

```Given element 20 found at position 2.
Given element 40 found at position 4.

## 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);
} else {
newNode->prev = last;
}
}``````
• 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) {
printf("Doubly Circular Linked List is empty.\n");
return -1;
}
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++;
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() {
• Initializes an empty list (`head = NULL`).