Python program to Search an Element in a Circular Linked List

Last Updated : 18 May, 2022

A linked list is a kind of linear data structure where each node has a data part and an address part which points to the next node. A circular linked list is a type of linked list where the last node points to the first one, making a circle of nodes.

Example:

Input: CList = 6->5->4->3->2, find = 3
Output: Element is present
 
Input: CList = 6->5->4->3->2, find = 1
Output: Element is not present

Search an Element in a Circular Linked List

For example, if the key to be searched is 30 and the linked list is 5->4->3->2, then the function should return false. If the key to be searched is 4, then the function should return true.

Approach:

Initialize a node pointer, temp = head.
Initialize a counter f=0 (to check if the element is present in a linked list or not).
If the head is null then the print list is empty.
Else start traversing the Linked List and if element found in Linked List increment in f.
If the counter is zero, then the print element is not found.
Else print element is present.

Below is the implementation of the above approach:

Python3

# Python program to Search an Element 
# in a Circular Linked List 
        
# Class to define node of the linked list     
class Node:  
    def __init__(self,data):     
        self.data = data; 
        self.next = None; 
          
class CircularLinkedList: 
      
    # Declaring Circular Linked List 
    def __init__(self):     
        self.head = Node(None);     
        self.tail = Node(None);     
        self.head.next = self.tail;     
        self.tail.next = self.head;     
          
      
    # Adds new nodes to the Circular Linked List 
    def add(self,data):     
          
        # Declares a new node to be added 
        newNode = Node(data);  
          
        # Checks if the Circular 
        # Linked List is empty 
        if self.head.data is None: 
              
            # If list is empty then new node 
            # will be the first node 
            # to be added in the Circular Linked List 
            self.head = newNode; 
            self.tail = newNode; 
            newNode.next = self.head; 
          
        else: 
            # If a node is already present then 
            # tail of the last node will point to 
            # new node 
            self.tail.next = newNode; 
              
            # New node will become new tail 
            self.tail = newNode; 
              
            # New Tail will point to the head 
            self.tail.next = self.head;     
                  
    # Function to search the element in the  
    # Circular Linked List 
    def findNode(self,element): 
          
        # Pointing the head to start the search 
        current = self.head; 
        i = 1; 
          
        # Declaring f = 0 
        f = 0;     
        # Check if the list is empty or not     
        if(self.head == None): 
            print("Empty list");  
        else: 
            while(True):      
                # Comparing the elements 
                # of each node to the 
                # element to be searched 
                if(current.data ==  element):  
  
                    # If the element is present 
                    # then incrementing f 
                    f += 1;     
                    break; 
                  
                # Jumping to next node 
                current = current.next;     
                i = i + 1;     
                  
                # If we reach the head 
                # again then element is not  
                # present in the list so  
                # we will break the loop 
                if(current == self.head):     
                    break;     
              
            # Checking the value of f 
            if(f > 0):     
                print("element is present");     
            else:     
                print("element is not present");     
                  
# Driver Code 
if __name__ == '__main__': 
      
    # Creating a Circular Linked List 
    ''' 
    Circular Linked List we will be working on: 
    1 -> 2 -> 3 -> 4 -> 5 -> 6 
    '''
    circularLinkedList = CircularLinkedList(); 
      
    #Adding nodes to the list     
    circularLinkedList.add(1); 
    circularLinkedList.add(2); 
    circularLinkedList.add(3); 
    circularLinkedList.add(4); 
    circularLinkedList.add(5); 
    circularLinkedList.add(6); 
      
    # Searching for node 2 in the list     
    circularLinkedList.findNode(2); 
      
    #Searching for node in the list     
    circularLinkedList.findNode(7);

Output:

element is present
element is not present

Time Complexity: O(N), where N is the length of the Circular linked list.

aditya_taparia

Improve

Python - Substituting patterns in text using regex

Implementation of XOR Linked List in Python

Python Matrix Exercises

Python Functions Exercises

Python Lambda Exercises

Python Pattern printing Exercises

Python DateTime Exercises

Python OOPS Exercises

Python Regex Exercises

Python LinkedList Exercises

Python Searching Exercises

Python Sorting Exercises

Python DSA Exercises

Python File Handling Exercises

Python CSV Exercises

Python JSON Exercises

Python OS Module Exercises

Python Tkinter Exercises

Python Web Scraping Exercises

Python Selenium Exercises

Python program to Search an Element in a Circular Linked List

Search an Element in a Circular Linked List

Approach:

Python3

Please Login to comment...

Similar Reads

What kind of Experience do you want to share?