Python program to search an element in a Circular Linked List

Created with Sketch.
Python Programs

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

Output:

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

Leave a Reply

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

©  2024 python tutorials.  python-tutorials.in