Search an element in a Doubly Linked List
Given a Doubly linked list(DLL) containing N nodes and an integer X, the task is to find the position of the integer X in the doubly linked list. If no such position found then print -1.
Examples:
Input: 15 <=> 16 <=> 8 <=> 7 <=> 13, X = 8
Output: 3
Explanation: X (= 8) is present at the 3rd node of the doubly linked list.
Therefore, the required output is 3Input: 5 <=> 3 <=> 4 <=> 2 <=> 9, X = 0
Output: -1
Explanation: X (= 0) is not present in the doubly linked list.
Therefore, the required output is -1
Approach: Follow the steps below to solve the problem:
- Initialize a variable, say pos, to store the position of the node containing data value X in the doubly linked list.
- Initialize a pointer, say temp, to store the head node of the doubly linked list.
- Iterate over the linked list and for every node, check if data value of that node is equal to X or not. If found to be true, then print pos.
- Otherwise, print -1.
Below is the implementation of the above approach
C++
// C++ program to implement // the above approach #include <bits/stdc++.h> using namespace std; // Structure of a node of // the doubly linked list struct Node { // Stores data value // of a node int data; // Stores pointer // to next node Node* next; // Stores pointer // to previous node Node* prev; }; // Function to insert a node at the // beginning of the Doubly Linked List void push(Node** head_ref, int new_data) { // Allocate memory for new node Node* new_node = (Node*) malloc ( sizeof ( struct Node)); // Insert the data new_node->data = new_data; // Since node is added at the // beginning, prev is always NULL new_node->prev = NULL; // Link the old list to the new node new_node->next = (*head_ref); // If pointer to head is not NULL if ((*head_ref) != NULL) { // Change the prev of head // node to new node (*head_ref)->prev = new_node; } // Move the head to point to the new node (*head_ref) = new_node; } // Function to find the position of // an integer in doubly linked list int search(Node** head_ref, int x) { // Stores head Node Node* temp = *head_ref; // Stores position of the integer // in the doubly linked list int pos = 0; // Traverse the doubly linked list while (temp->data != x && temp->next != NULL) { // Update pos pos++; // Update temp temp = temp->next; } // If the integer not present // in the doubly linked list if (temp->data != x) return -1; // If the integer present in // the doubly linked list return (pos + 1); } // Driver Code int main() { Node* head = NULL; int X = 8; // Create the doubly linked list // 18 <-> 15 <-> 8 <-> 9 <-> 14 push(&head, 14); push(&head, 9); push(&head, 8); push(&head, 15); push(&head, 18); cout << search(&head, X); return 0; } |
Java
// Java program to implement // the above approach import java.util.*; class GFG { // Structure of a node of // the doubly linked list static class Node { // Stores data value // of a node int data; // Stores pointer // to next node Node next; // Stores pointer // to previous node Node prev; }; // Function to insert a node at the // beginning of the Doubly Linked List static Node push(Node head_ref, int new_data) { // Allocate memory for new node Node new_node = new Node(); // Insert the data new_node.data = new_data; // Since node is added at the // beginning, prev is always null new_node.prev = null ; // Link the old list to the new node new_node.next = head_ref; // If pointer to head is not null if (head_ref != null ) { // Change the prev of head // node to new node head_ref.prev = new_node; } // Move the head to point to the new node head_ref = new_node; return head_ref; } // Function to find the position of // an integer in doubly linked list static int search(Node head_ref, int x) { // Stores head Node Node temp = head_ref; // Stores position of the integer // in the doubly linked list int pos = 0 ; // Traverse the doubly linked list while (temp.data != x && temp.next != null ) { // Update pos pos++; // Update temp temp = temp.next; } // If the integer not present // in the doubly linked list if (temp.data != x) return - 1 ; // If the integer present in // the doubly linked list return (pos + 1 ); } // Driver Code public static void main(String[] args) { Node head = null ; int X = 8 ; // Create the doubly linked list // 18 <-> 15 <-> 8 <-> 9 <-> 14 head = push(head, 14 ); head = push(head, 9 ); head = push(head, 8 ); head = push(head, 15 ); head = push(head, 18 ); System.out.print(search(head, X)); } } // This code is contributed by Rajput-Ji |
C#
// C# program to implement // the above approach using System; class GFG{ // Structure of a node of // the doubly linked list public class Node { // Stores data value // of a node public int data; // Stores pointer // to next node public Node next; // Stores pointer // to previous node public Node prev; }; // Function to insert a node at the // beginning of the Doubly Linked List static Node push(Node head_ref, int new_data) { // Allocate memory for new node Node new_node = new Node(); // Insert the data new_node.data = new_data; // Since node is added at the // beginning, prev is always null new_node.prev = null ; // Link the old list to the new node new_node.next = head_ref; // If pointer to head is not null if (head_ref != null ) { // Change the prev of head // node to new node head_ref.prev = new_node; } // Move the head to point to the new node head_ref = new_node; return head_ref; } // Function to find the position of // an integer in doubly linked list static int search(Node head_ref, int x) { // Stores head Node Node temp = head_ref; // Stores position of the integer // in the doubly linked list int pos = 0; // Traverse the doubly linked list while (temp.data != x && temp.next != null ) { // Update pos pos++; // Update temp temp = temp.next; } // If the integer not present // in the doubly linked list if (temp.data != x) return -1; // If the integer present in // the doubly linked list return (pos + 1); } // Driver Code public static void Main(String[] args) { Node head = null ; int X = 8; // Create the doubly linked list // 18 <-> 15 <-> 8 <-> 9 <-> 14 head = push(head, 14); head = push(head, 9); head = push(head, 8); head = push(head, 15); head = push(head, 18); Console.Write(search(head, X)); } } // This code is contributed by gauravrajput1 |
Javascript
<script> // Javascript program to implement // the above approach // Structure of a node of // the doubly linked list class Node { constructor() { // Stores data value // of a node this .data = 0; // Stores pointer // to next node this .next = null ; // Stores pointer // to previous node this .prev = null ; } }; // Function to insert a node at the // beginning of the Doubly Linked List function push(head_ref, new_data) { // Allocate memory for new node var new_node = new Node(); // Insert the data new_node.data = new_data; // Since node is added at the // beginning, prev is always null new_node.prev = null ; // Link the old list to the new node new_node.next = (head_ref); // If pointer to head is not null if ((head_ref) != null ) { // Change the prev of head // node to new node (head_ref).prev = new_node; } // Move the head to point to the new node (head_ref) = new_node; return head_ref; } // Function to find the position of // an integer in doubly linked list function search( head_ref, x) { // Stores head Node var temp = head_ref; // Stores position of the integer // in the doubly linked list var pos = 0; // Traverse the doubly linked list while (temp.data != x && temp.next != null ) { // Update pos pos++; // Update temp temp = temp.next; } // If the integer not present // in the doubly linked list if (temp.data != x) return -1; // If the integer present in // the doubly linked list return (pos + 1); } // Driver Code var head = null ; var X = 8; // Create the doubly linked list // 18 <. 15 <. 8 <. 9 <. 14 head = push(head, 14); head = push(head, 9); head = push(head, 8); head = push(head, 15); head = push(head, 18); document.write( search(head, X)); // This code is contributed by rrrtnx. </script> |
Python3
# Python program to implement # the above approach # Structure of a Node of # the doubly linked list class Node: def __init__( self ): self .data = 0 ; self . next = None ; self .prev = None ; # Function to insert a Node at the # beginning of the Doubly Linked List def push(head_ref, new_data): # Allocate memory for new Node new_Node = Node(); # Insert the data new_Node.data = new_data; # Since Node is added at the # beginning, prev is always None new_Node.prev = None ; # Link the old list to the new Node new_Node. next = head_ref; # If pointer to head is not None if (head_ref ! = None ): # Change the prev of head # Node to new Node head_ref.prev = new_Node; # Move the head to point to the new Node head_ref = new_Node; return head_ref; # Function to find the position of # an integer in doubly linked list def search(head_ref, x): # Stores head Node temp = head_ref; # Stores position of the integer # in the doubly linked list pos = 0 ; # Traverse the doubly linked list while (temp.data ! = x and temp. next ! = None ): # Update pos pos + = 1 ; # Update temp temp = temp. next ; # If the integer not present # in the doubly linked list if (temp.data ! = x): return - 1 ; # If the integer present in # the doubly linked list return (pos + 1 ); # Driver Code if __name__ = = '__main__' : head = None ; X = 8 ; # Create the doubly linked list # 18 <-> 15 <-> 8 <-> 9 <-> 14 head = push(head, 14 ); head = push(head, 9 ); head = push(head, 8 ); head = push(head, 15 ); head = push(head, 18 ); print (search(head, X)); # This code is contributed by Rajput-Ji |
Output:
3
Time Complexity: O(N)
Auxiliary Space: O(1)