Search an Element in Doubly Circular Linked List
Pre-requisite: Convert an Array to a Circular Doubly Linked List, Doubly Circular Linked List
Given a doubly circular linked list. The task is to find the position of an element in the list.
Image Representation:
Algorithm:
- Declare a temp pointer, and initialize it to the head of the list.
- Iterate the loop until temp reaches the start address (last node in the list, as it is in a circular fashion), and check for the n element, whether present or not.
- If it is present, raise a flag, increment count, and break the loop.
- At the last, as the last node is not visited yet check for the n element if present does step 3.
The below program illustrates the above approach:
C++
// C++ program to illustrate inserting a Node in // a Circular Doubly Linked list in begging, end // and middle #include <bits/stdc++.h> using namespace std; // Structure of a Node struct Node { int data; struct Node *next; struct Node *prev; }; // Function to insert a node at the end void insertNode(struct Node** start, int value) { // If the list is empty, create a single node // circular and doubly list if (*start == NULL) { struct Node* new_node = new Node; new_node->data = value; new_node->next = new_node->prev = new_node; *start = new_node; return; } // If list is not empty /* Find last node */ Node *last = (*start)->prev; // Create Node dynamically struct Node* new_node = new Node; new_node->data = value; // Start is going to be next of new_node new_node->next = *start; // Make new node previous of start (*start)->prev = new_node; // Make last previous of new node new_node->prev = last; // Make new node next of old last last->next = new_node; } // Function to display the// circular doubly linked listvoid displayList(struct Node* start) { struct Node *temp = start; while (temp->next != start) { printf("%d ", temp->data); temp = temp->next; } printf("%d ", temp->data); } // Function to search the particular element// from the listint searchList(struct Node* start, int search){ // Declare the temp variable struct Node *temp = start; // Declare other control // variable for the searching int count=0,flag=0,value; // If start is NULL return -1 if(temp == NULL) return -1; else { // Move the temp pointer until, // temp->next doesn't move // start address (Circular Fashion) while(temp->next != start) { // Increment count for location count++; // If it is found raise the // flag and break the loop if(temp->data == search) { flag = 1; count--; break; } // Increment temp pointer temp = temp->next; } // Check whether last element in the // list content the value if contain, // raise a flag and increment count if(temp->data == search) { count++; flag = 1; } // If flag is true, then element // found, else not if(flag == 1) cout<<"\n"<<search <<" found at location "<< count<<endl; else cout<<"\n"<<search <<" not found"<<endl; }}// Driver codeint main() { /* Start with the empty list */ struct Node* start = NULL; // Insert 4. So linked list becomes 4->NULL insertNode(&start, 4); // Insert 5. So linked list becomes 4->5 insertNode(&start, 5); // Insert 7. So linked list // becomes 4->5->7 insertNode(&start, 7); // Insert 8. So linked list // becomes 4->5->7->8 insertNode(&start, 8); // Insert 6. So linked list // becomes 4->5->7->8->6 insertNode(&start, 6); printf("Created circular doubly linked list is: "); displayList(start); searchList(start, 5); return 0; } |
Java
// Java program to illustrate inserting // a Node in a Circular Doubly Linked list // in begging, end and middle class GFG{ // Structure of a Node static class Node { int data; Node next; Node prev; }; // Function to insert a node at the end static Node insertNode(Node start, int value) { // If the list is empty, create a single node // circular and doubly list if (start == null) { Node new_node = new Node(); new_node.data = value; new_node.next = new_node.prev = new_node; start = new_node; return new_node; } // If list is not empty // Find last node / Node last = (start).prev; // Create Node dynamically Node new_node = new Node(); new_node.data = value; // Start is going to be next of new_node new_node.next = start; // Make new node previous of start (start).prev = new_node; // Make last previous of new node new_node.prev = last; // Make new node next of old last last.next = new_node; return start;} // Function to display the // circular doubly linked list static void displayList(Node start) { Node temp = start; while (temp.next != start) { System.out.printf("%d ", temp.data); temp = temp.next; } System.out.printf("%d ", temp.data); } // Function to search the particular element // from the list static int searchList(Node start, int search) { // Declare the temp variable Node temp = start; // Declare other control // variable for the searching int count = 0, flag = 0, value; // If start is null return -1 if(temp == null) return -1; else { // Move the temp pointer until, // temp.next doesn't move // start address (Circular Fashion) while(temp.next != start) { // Increment count for location count++; // If it is found raise the // flag and break the loop if(temp.data == search) { flag = 1; count--; break; } // Increment temp pointer temp = temp.next; } // Check whether last element in the // list content the value if contain, // raise a flag and increment count if(temp.data == search) { count++; flag = 1; } // If flag is true, then element // found, else not if(flag == 1) System.out.println("\n"+search +" found at location "+ count); else System.out.println("\n"+search +" not found"); } return -1;} // Driver code public static void main(String args[]){ // Start with the empty list / Node start = null; // Insert 4. So linked list becomes 4.null start= insertNode(start, 4); // Insert 5. So linked list becomes 4.5 start= insertNode(start, 5); // Insert 7. So linked list // becomes 4.5.7 start= insertNode(start, 7); // Insert 8. So linked list // becomes 4.5.7.8 start= insertNode(start, 8); // Insert 6. So linked list // becomes 4.5.7.8.6 start= insertNode(start, 6); System.out.printf("Created circular doubly linked list is: "); displayList(start); searchList(start, 5); } }// This code is contributed by Arnab Kundu |
Python3
# Python3 program to illustrate inserting a Node in # a Circular Doubly Linked list in begging, end # and middle import math# Structure of a Node class Node: def __init__(self, data): self.data = data self.next = None# Function to insert a node at the end def insertNode(start, value): # If the list is empty, create a single node # circular and doubly list if (start == None) : new_node = Node(value) new_node.data = value new_node.next = new_node new_node.prev = new_node start = new_node return new_node # If list is not empty # Find last node */ last = start.prev # Create Node dynamically new_node = Node(value) new_node.data = value # Start is going to be next of new_node new_node.next = start # Make new node previous of start (start).prev = new_node # Make last previous of new node new_node.prev = last # Make new node next of old last last.next = new_node return start# Function to display the# circular doubly linked listdef displayList(start): temp = start while (temp.next != start): print(temp.data, end = " ") temp = temp.next print(temp.data) # Function to search the particular element# from the listdef searchList(start, search): # Declare the temp variable temp = start # Declare other control # variable for the searching count = 0 flag = 0 value = 0 # If start is None return -1 if(temp == None): return -1 else: # Move the temp pointer until, # temp.next doesn't move # start address (Circular Fashion) while(temp.next != start): # Increment count for location count = count + 1 # If it is found raise the # flag and break the loop if(temp.data == search): flag = 1 count = count - 1 break # Increment temp pointer temp = temp.next # Check whether last element in the # list content the value if contain, # raise a flag and increment count if(temp.data == search): count = count + 1 flag = 1 # If flag is true, then element # found, else not if(flag == 1): print(search,"found at location ", count) else: print(search, " not found") return -1# Driver codeif __name__=='__main__': # Start with the empty list */ start = None # Insert 4. So linked list becomes 4.None start = insertNode(start, 4) # Insert 5. So linked list becomes 4.5 start = insertNode(start, 5) # Insert 7. So linked list # becomes 4.5.7 start = insertNode(start, 7) # Insert 8. So linked list # becomes 4.5.7.8 start = insertNode(start, 8) # Insert 6. So linked list # becomes 4.5.7.8.6 start = insertNode(start, 6) print("Created circular doubly linked list is: ", end = "") displayList(start) searchList(start, 5)# This article contributed by Srathore |
C#
// C# Program to Reverse a List using Data Swapping using System;class GFG{ // Structure of a Node public class Node { public int data; public Node next; public Node prev; }; // Function to insert a node at the end static Node insertNode(Node start, int value) { // If the list is empty, create a single node // circular and doubly list Node new_node = new Node(); if (start == null) { new_node.data = value; new_node.next = new_node.prev = new_node; start = new_node; return new_node; } // If list is not empty // Find last node / Node last = (start).prev; // Create Node dynamically new_node = new Node(); new_node.data = value; // Start is going to be next of new_node new_node.next = start; // Make new node previous of start (start).prev = new_node; // Make last previous of new node new_node.prev = last; // Make new node next of old last last.next = new_node; return start; } // Function to display the // circular doubly linked list static void displayList(Node start) { Node temp = start; while (temp.next != start) { Console.Write("{0} ", temp.data); temp = temp.next; } Console.Write("{0} ", temp.data); } // Function to search the particular element // from the list static int searchList(Node start, int search) { // Declare the temp variable Node temp = start; // Declare other control // variable for the searching int count = 0, flag = 0, value; // If start is null return -1 if(temp == null) return -1; else { // Move the temp pointer until, // temp.next doesn't move // start address (Circular Fashion) while(temp.next != start) { // Increment count for location count++; // If it is found raise the // flag and break the loop if(temp.data == search) { flag = 1; count--; break; } // Increment temp pointer temp = temp.next; } // Check whether last element in the // list content the value if contain, // raise a flag and increment count if(temp.data == search) { count++; flag = 1; } // If flag is true, then element // found, else not if(flag == 1) Console.WriteLine("\n"+search +" found at location "+ count); else Console.WriteLine("\n"+search +" not found"); } return -1; } // Driver code public static void Main(String []args) { // Start with the empty list / Node start = null; // Insert 4. So linked list becomes 4.null start= insertNode(start, 4); // Insert 5. So linked list becomes 4.5 start= insertNode(start, 5); // Insert 7. So linked list // becomes 4.5.7 start= insertNode(start, 7); // Insert 8. So linked list // becomes 4.5.7.8 start= insertNode(start, 8); // Insert 6. So linked list // becomes 4.5.7.8.6 start= insertNode(start, 6); Console.Write("Created circular doubly linked list is: "); displayList(start); searchList(start, 5); } }// This code has been contributed by 29AjayKumar |
Javascript
<script>// JavaScript program to illustrate inserting // a Node in a Circular Doubly Linked list // in begging, end and middle class Node { constructor() { this.data=0; this.next=this.prev=null; }}// Function to insert a node at the endfunction insertNode(start,value){ // If the list is empty, create a single node // circular and doubly list if (start == null) { let new_node = new Node(); new_node.data = value; new_node.next = new_node.prev = new_node; start = new_node; return new_node; } // If list is not empty // Find last node / let last = (start).prev; // Create Node dynamically let new_node = new Node(); new_node.data = value; // Start is going to be next of new_node new_node.next = start; // Make new node previous of start (start).prev = new_node; // Make last previous of new node new_node.prev = last; // Make new node next of old last last.next = new_node; return start;}// Function to display the // circular doubly linked list function displayList(start){ let temp = start; while (temp.next != start) { document.write(temp.data+" "); temp = temp.next; } document.write(temp.data+" ");}// Function to search the particular element // from the list function searchList(start,search){ // Declare the temp variable let temp = start; // Declare other control // variable for the searching let count = 0, flag = 0, value; // If start is null return -1 if(temp == null) return -1; else { // Move the temp pointer until, // temp.next doesn't move // start address (Circular Fashion) while(temp.next != start) { // Increment count for location count++; // If it is found raise the // flag and break the loop if(temp.data == search) { flag = 1; count--; break; } // Increment temp pointer temp = temp.next; } // Check whether last element in the // list content the value if contain, // raise a flag and increment count if(temp.data == search) { count++; flag = 1; } // If flag is true, then element // found, else not if(flag == 1) document.write("<br>"+search +" found at location "+ count); else document.write("<br>"+search +" not found"); } return -1;}// Driver code // Start with the empty list /let start = null; // Insert 4. So linked list becomes 4.null start= insertNode(start, 4); // Insert 5. So linked list becomes 4.5 start= insertNode(start, 5); // Insert 7. So linked list // becomes 4.5.7 start= insertNode(start, 7); // Insert 8. So linked list // becomes 4.5.7.8 start= insertNode(start, 8); // Insert 6. So linked list // becomes 4.5.7.8.6 start= insertNode(start, 6); document.write("Created circular doubly linked list is: "); displayList(start); searchList(start, 5); // This code is contributed by avanitrachhadiya2155</script> |
Output:
Created circular doubly linked list is: 4 5 7 8 6 5 found at location 2
Time Complexity: O(n), as we are using a loop to traverse n times. Where n is the number of nodes in the linked list.
Auxiliary Space: O(1), as we are not using any extra space.
Feeling lost in the world of random DSA topics, wasting time without progress? It’s time for a change! Join our DSA course, where we’ll guide you on an exciting journey to master DSA efficiently and on schedule.
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 zambiatek!
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 zambiatek!
