Search in Doubly Linked List : Algorithm and Program

Searching in a doubly linked list means finding whether a particular value exists in the list and, if it does, identifying its position. A doubly linked list is a structure where each node contains data and two pointers: one pointing to the next node and another pointing to the previous node. This allows traversal in both forward and backward directions.

The search operation typically starts from the head of the list, moves through each node sequentially using the next pointer, and compares the node’s data with the target value. If the value is found, its position in the list is returned; otherwise, the search continues until the end of the list is reached, and a message indicates that the element is not present.

This operation is important because it enables efficient access and verification of data in the list, especially when combined with other operations like insertion or deletion.

Searching Algorithm in Doubly Linked List

1. Start at the Head:
   • Begin from the head of the list.
2. Traverse the List:
   • Move through the list one node at a time.
   • For each node, check if the data matches the element you’re searching for.
3. Check for a Match:
   • If a node with matching data is found, return a the true as element found successfully (like the position of the node or a success message).
   • If no match is found and reached the end of the list , return a failure indicator like element not found (like a message stating the element is not in the list).
4. End of Search:
   • The search ends when either a match is found or the end of the list is reached.

C Program to Perform Search in Doubly 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 = NULL;
    newNode->prev = NULL;
    return newNode;
}

// Insert at the end of Double linked list
void insertAtEnd(Node** head, int data) {
    Node *newNode = createNode(data);
    if (*head == NULL) {
        *head = newNode;
        return;
    }
    Node *temp = *head;
    while (temp->next != NULL) {
        temp = temp->next;
    }
    temp->next = newNode;
    newNode->prev = temp;
}

// Function to search for an element
int searchElementInDoublyLinkedList(Node *head, int key) {
    Node *temp = head;
    int position = 1;
    while (temp != NULL) {
        if (temp->data == key) {
            printf("%d found in Doubly linked list at position %d.\n", key, position);
            return position;
        }
        temp = temp->next;
        position++;
    }
    printf("%d not found in Doubly linked list at position.\n", key);
    return -1;
}

// Main function
int main() {
    Node *head = NULL;
    insertAtEnd(&head, 10);
    insertAtEnd(&head, 20);
    insertAtEnd(&head, 30);
    insertAtEnd(&head, 40);
    insertAtEnd(&head, 50);
    searchElementInDoublyLinkedList(head, 50);
    searchElementInDoublyLinkedList(head, 60);
    return 0;
}

Output

50 found in Doubly linked list at position 5.
60 not found in Doubly linked list at position.

Search in a Doubly Linked List Program Explanations

Include Headers and Define Node Structure

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

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

typedef struct Node Node;

• Headers: The program includes stdio.h for input/output operations and stdlib.h for memory allocation.
• Node Structure: Defines the structure for a node in the doubly linked list. Each node contains:
  • int data: The data stored in the node.
  • struct Node *next: A pointer to the next node.
  • struct Node *prev: A pointer to the previous node.
• The typedef is used to define Node as an alias for struct Node at the beginning. After that you can simply use Node to refer to this structure.

createNode Function

Node *createNode(int data) {
    Node *newNode = (Node*)malloc(sizeof(Node));
    newNode->data = data;
    newNode->next = NULL;
    newNode->prev = NULL;
    return newNode;
}

• Purpose: Creates a new node with the specified data.
• Process: Allocates memory for a new node, initializes its data, and sets its next and prev pointers to NULL.

insertAtEnd Function

void insertAtEnd(Node** head, int data) {
    Node *newNode = createNode(data);
    if (*head == NULL) {
        *head = newNode;
        return;
    }
    Node *temp = *head;
    while (temp->next != NULL) {
        temp = temp->next;
    }
    temp->next = newNode;
    newNode->prev = temp;
}

• Purpose: Inserts a new node at the end of the doubly linked list.
• Process:
  • Creates a new node using createNode.
  • If the list is empty (head is NULL), sets the new node as the head.
  • If the list is not empty, traverses to the last node and adjusts pointers to insert the new node at the end.

searchElementInDoublyLinkedList Function

int searchElementInDoublyLinkedList(Node *head, int key) {
    Node *temp = head;
    int position = 1;
    while (temp != NULL) {
        if (temp->data == key) {
            printf("%d found in Doubly linked list at position %d.\n", key, position);
            return position;
        }
        temp = temp->next;
        position++;
    }
    printf("%d not found in Doubly linked list at position.\n", key);
    return -1;
}

• Purpose: Searches for an element in the doubly linked list.
• Process:
  • Starts from the head and traverses the list.
  • For each node, checks if its data matches the key.
  • If a match is found, prints the position and returns it.
  • If no match is found by the end of the list, prints a message stating the element is not in the list and returns -1.

main Function

int main() {
    Node *head = NULL;
    insertAtEnd(&head, 10);
    insertAtEnd(&head, 20);
    insertAtEnd(&head, 30);
    insertAtEnd(&head, 40);
    insertAtEnd(&head, 50);
    searchElementInDoublyLinkedList(head, 50);
    searchElementInDoublyLinkedList(head, 60);
    return 0;
}

• Purpose: Demonstrates the functionality of the list.
• Process:
  • Initializes an empty list (head is NULL).
  • Inserts several nodes at the end of the list.
  • Performs searches for two elements, one that exists in the list and one that does not.

Time & Space Complexity

Time Complexity

Space Complexity