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++ 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 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# 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
|
|
<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>
|
|
# 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 poto 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
|
Time Complexity: O(N)
Auxiliary Space: O(1)
Singly Linked List vs Doubly Linked List
Before looking at the differences between the singly linked list and doubly linked list, we first understand what is singly linked list and doubly linked list separately.
Introduction
In today’s world, the communication network is expanding at a very fast rate. Businesses are going digital to improve management efficiency. The amount of data generated on the internet is increasing, and as a result, datasets are becoming more complex. It is important to organize, manage, access, and analyze the data carefully and efficiently, a data structure is the most helpful method, and the article focuses on it
In computer science, data structures serve as the foundation for abstract data types (ADT), where ADT is the logical form of data types. The physical design of data types is implemented using data structures. various types of data structures are used for different types of applications; some are specialized in specific tasks.
Data structures are referred to as a collection of data values and relationships between them, functions, and operations applicable to the data. so that, users can easily access and modify the data efficiently.
Data structures help us to manage large amounts of data, such as huge databases. Efficient data structures are the fundamental basis for efficient algorithms. Besides efficient storage, data structures are also responsible for the efficient retrieval of data from stored locations. It includes an array, Graph, Searching, Programs, Linked List, Pointer, Stack, Queue, Structure, Sorting, and so forth.
The concepts of searching in a data structure, as well as its methods, are covered in this article.