Searching in Circular Linked list
Given a Circular Linked List CList, and an element K, the task is to check if this element K is present in the Circular Linked list or not.
Example:
Input: CList = 6->5->4->3->2, K = 3
Output: Found
Input: CList = 6->5->4->3->2, K = 1
Output: Not Found
Approach: The approach to find an element in Circular Linked List can be visualized as follows:
- Keep a pointer to the head of the Circular Linked List. This will help us to determine if the Linked List has been traversed already.
- Now traverse the Linked List one by one and check if the element is present or not.
- If the element is present, return true.
- Now if the element is not present and the traversal pointer reaches the head again, it means the element is not present in the CLL. Therefore return false.
Below is the implementation of the above approach:
C++
#include <iostream> using namespace std; class Search { private : class Node { public : int data; Node* next; Node( int data) { this ->data = data; next = nullptr; } }; public : Node* head = nullptr; Node* tempo = nullptr; // Function to add new nodes at the end of the list void addNode( int data) { Node* new1 = new Node(data); // If linked list is empty if (head == nullptr) { head = new1; } else { tempo->next = new1; } tempo = new1; // last node points to the first node tempo->next = head; } void find( int key) { // temp will traverse the circular linked list for // searching the element Node* temp = head; // flag used to check if the element is found or not int f = 0; if (head == nullptr) { cout << "List is empty" << endl; } else { do { if (temp->data == key) { cout << key << " Found" << endl; f = 1; break ; } temp = temp->next; } while (temp != head); if (f == 0) { cout << key << " Not Found" << endl; } } } }; // Driver code int main() { Search s; // Adds data to the list s.addNode(5); s.addNode(4); s.addNode(3); s.addNode(2); // Search for node 2 in the list int key = 2; s.find(key); // Search for node 6 in the list key = 6; s.find(key); return 0; } |
Java
// Java program to search for an element in a circular // linked list public class Search { class Node { int data; Node next; public Node( int data) { this .data = data; } } // declaring head pointer as null public Node head = null ; public Node tempo = null ; // function to add new nodes at the end of the list public void addNode( int data) { Node new1 = new Node(data); // If linked list is empty if (head == null ) { head = new1; } else { tempo.next = new1; } tempo = new1; // last node points to first node tempo.next = head; } public void find( int key) { // temp will traverse the circular linked list for // searching element Node temp = head; // counter used to check if the element is found or // not int f = 0 ; if (head == null ) { System.out.println( "List is empty" ); } else { do { if (temp.data == key) { System.out.println(key + " Found" ); f = 1 ; break ; } temp = temp.next; } while (temp != head); if (f == 0 ) { System.out.println(key + " Not Found" ); } } } // Driver code public static void main(String[] args) { Search s = new Search(); // Adds data to the list s.addNode( 5 ); s.addNode( 4 ); s.addNode( 3 ); s.addNode( 2 ); // Search for node 2 in the list int key = 2 ; s.find(key); // Search for node 6 in the list key = 6 ; s.find(key); } } |
Python3
# Python program to search for an element in a circular # linked list class Search: class Node: def __init__( self , data): self .data = data self . next = None def __init__( self ): self .head = None self .tempo = None # Function to add new nodes at the end of the list def addNode( self , data): new1 = Search.Node(data) # If linked list is empty if self .head is None : self .head = new1 else : self .tempo. next = new1 self .tempo = new1 # last node points to the first node self .tempo. next = self .head def find( self , key): # temp will traverse the circular linked list for searching the element temp = self .head # flag used to check if the element is found or not f = 0 if self .head is None : print ( "List is empty" ) else : while True : if temp.data = = key: print (key, " Found" ) f = 1 break temp = temp. next if temp = = self .head: break if f = = 0 : print (key, " Not Found" ) # Driver code if __name__ = = "__main__" : s = Search() # Adds data to the list s.addNode( 5 ) s.addNode( 4 ) s.addNode( 3 ) s.addNode( 2 ) # Search for node 2 in the list key = 2 s.find(key) # Search for node 6 in the list key = 6 s.find(key) # This code is contributed by Susobhan Akhuli |
C#
using System; namespace CircularLinkedListSearch { class Search { public class Node { public int data; public Node next; public Node( int data) { this .data = data; } } // declaring head pointer as null public Node head = null ; public Node tempo = null ; // function to add new nodes at the end of the list public void AddNode( int data) { Node new1 = new Node(data); // If linked list is empty if (head == null ) { head = new1; } else { tempo.next = new1; } tempo = new1; // last node points to first node tempo.next = head; } public void Find( int key) { // temp will traverse the circular linked list for // searching element Node temp = head; // counter used to check if the element is found or // not int f = 0; if (head == null ) { Console.WriteLine( "List is empty" ); } else { do { if (temp.data == key) { Console.WriteLine(key + " Found" ); f = 1; break ; } temp = temp.next; } while (temp != head); if (f == 0) { Console.WriteLine(key + " Not Found" ); } } } // Driver code static void Main( string [] args) { Search s = new Search(); // Adds data to the list s.AddNode(5); s.AddNode(4); s.AddNode(3); s.AddNode(2); // Search for node 2 in the list int key = 2; s.Find(key); // Search for node 6 in the list key = 6; s.Find(key); } } } |
Javascript
// JavaScript program to search for an element in a circular // linked list class Search { constructor() { this .head = null ; this .tempo = null ; } // Function to add new nodes at the end of the list addNode(data) { const newNode = { data, next: null }; // If linked list is empty if ( this .head === null ) { this .head = newNode; } else { this .tempo.next = newNode; } this .tempo = newNode; // last node points to the first node this .tempo.next = this .head; } find(key) { // temp will traverse the circular linked list for // searching the element let temp = this .head; // flag used to check if the element is found or not let found = false ; if ( this .head === null ) { console.log( "List is empty" ); } else { do { if (temp.data === key) { console.log(key + " Found" ); found = true ; break ; } temp = temp.next; } while (temp !== this .head); if (!found) { console.log(key + " Not Found" ); } } } } // Driver code const s = new Search(); // Adds data to the list s.addNode(5); s.addNode(4); s.addNode(3); s.addNode(2); // Search for node 2 in the list let key = 2; s.find(key); // Search for node 6 in the list key = 6; s.find(key); // This code is contributed by Susobhan Akhuli |
Output
2 Found 6 Not Found
Contact Us