Search in Doubly Linked List : Algorithm and Program

by

In this tutorial we will learn how to perform search operation in doubly linked list. We will also learn writing Program and algorithm to perform searching in doubly linked list.

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.

This program is a clear demonstration of creating, managing, and searching a doubly linked list in C. The code is written in an easy-to-understand manner, ideal for beginners learning about data structures.