Python program to search an element in a Circular Linked List

Created with Sketch.

Python program to search an element in a Circular Linked List

In this program, we create a circular linked list and search a node in the list.

  1. 9->5->2->7->3

Consider, above example. Suppose we need to search for node 5. To solve this problem, we will iterate through the list and compare each node with 5. If a match is found, we will set the flag to true and prints out the position of the node 5. In this example, node 5 is present at position 2.

ALGORITHM:

  1. Define a Node class which represents a node in the list. It has two properties data and next which will point to the next node.
  2. Define another class for creating a circular linked list, and it has two nodes: head and tail.
  3. search() will search for a node in the list:
  • Variable i will keep track of the position of the searched node.
  • The variable flag will store boolean value false.
  • Current will point to head node.
  • Iterate through the loop by incrementing current to current.next and i to i + 1.
  • Compare each node’s data with the searched node if a match is found, set the flag to true.
  • If the flag is true, prints the position of the searched node.
  • Else, print the message “Element is not present in the list”.

PROGRAM:

  1. #Represents the node of list.  
  2. class Node:
  3.     def __init__(self,data):
  4.         self.data = data;
  5.         self.next = None;
  6. class CreateList:
  7.     #Declaring head and tail pointer as null.  
  8.     def __init__(self):
  9.         self.head = Node(None);
  10.         self.tail = Node(None);
  11.         self.head.next = self.tail;
  12.         self.tail.next = self.head;
  13.     #This function will add the new node at the end of the list.  
  14.     def add(self,data):
  15.         newNode = Node(data);
  16.         #Checks if the list is empty.  
  17.         if self.head.data is None:
  18.             #If list is empty, both head and tail would point to new node.  
  19.             self.head = newNode;
  20.             self.tail = newNode;
  21.             newNode.next = self.head;
  22.         else:
  23.             #tail will point to new node.  
  24.             self.tail.next = newNode;
  25.             #New node will become new tail.  
  26.             self.tail = newNode;
  27.             #Since, it is circular linked list tail will point to head.  
  28.             self.tail.next = self.head;
  29.     #Searches for a node in the list  
  30.     def search(self,element):
  31.         current = self.head;
  32.         i = 1;
  33.         flag = False;
  34.         #Checks whether list is empty  
  35.         if(self.head == None):
  36.             print(“List is empty”);
  37.         else:
  38.             while(True):
  39.                 #Compares element to be found with each node present in the list  
  40.                 if(current.data ==  element):
  41.                     flag = True;
  42.                     break;
  43.                 current = current.next;
  44.                 i = i + 1;
  45.                 if(current == self.head):
  46.                     break;
  47.             if(flag):
  48.                 print(“Element is present in the list at the position :  “ + str(i));
  49.             else:
  50.                 print(“Element is not present in the list”);
  51. class CircularLinkedList:
  52.     cl = CreateList();
  53.     #Adds data to the list  
  54.     cl.add(1);
  55.     cl.add(2);
  56.     cl.add(3);
  57.     cl.add(4);
  58.     #Search for node 2 in the list  
  59.     cl.search(2);
  60.     #Search for node in the list  
  61.     cl.search(7);

Output:

Element is present in the list at the position: 2
Element is not present in the list

Leave a Reply

Your email address will not be published. Required fields are marked *