Python Program to Search for an Element in the Linked List without using Recursion

Python / By

Linked List Data Structure:

A linked list is a type of data structure that consists of a chain of nodes, each of which contains a value and a pointer to the next node in the chain.

The list’s head pointer points to the first node, and the list’s last element points to null. The head pointer points to null when the list is empty.

Linked lists can grow in size dynamically, and inserting and deleting elements from them is simple because, unlike arrays, we only need to change the pointers to the previous and next elements to insert or delete an element.

Linked lists are commonly used in the construction of file systems, adjacency lists, and hash tables.

Given an Element and LinkedList, the Task is to check whether the given element is present in the LinkedList or not in Python.

Examples:

Example1:

Input:

Given LinkedList : 5 1 7 8 9 11 13
Given Element : 9

Output:

True

Example2:

Input:

Given LinkedList : 1 9 3 5
Given Element : 2

Output:

False

Program to Search for an Element in the Linked List without using Recursion in Python

Approach:

  • Create a class that creates a node of the LinkedList.
  • Create a constructor that accepts val as an argument and initializes the class variable val with the given argument val.
  • Initializing the next Pointer(Last Node Pointer to None i.e Null).
  • Create a Class Which Creates the LinkedList by connecting all the nodes.
  • Inside the class, the constructor Initialize the head pointer to None(Null) and the last Node pointer to Null.
  • Create a function addElements() inside the class which accepts the data value as an argument and add this node to the LinkedList.
  • Check if the lastNode Pointer is None using the if conditional statement.
  • If the above if condition is true(If there are no elements in the linked list) then Create a Node using the Node class by passing the data as an argument.
  • Initialize the head with the above node.
  • Else Create the new node and initialize the last node pointer Value to the new node.
  • Set the last node Pointer Value to the Next Pointer.
  • Create a function SearchElement() inside the class which accepts the element as argument and searches whether the given element is present in the LinkedList or not
  • Take a Pointer that points to the nodes of the LinkedList and initialize its value to the Head Pointer.
  • Loop till the temPtr is None(null) using the while loop.
  • Check if the value of the node is equal to the given element using the if conditional statement
  • If it is true then return True
  • Else Increment the temPtr to the Next Node.
  • Return False(Element is not Found)
  • Take an object for the LinkedList Class and store it in a variable.
  • Add elements to the LinkedList by using the below steps.
  • Loop till the above number of elements using the For loop.
  • Give the data value as user input and store it in a variable.
  • Pass the above value as an argument to the addElements() function to add this value as a node to the LinkedList.
  • Give the element to search as user input and store it in a variable
  • Printing whether the element is present or not in the LinkedList by calling the SearchElement() of the above object.
  • The Exit of the Program.

Below is the implementation:

# Create a class that creates a node of the LinkedList.
class Node:
    # Create a constructor that accepts val as an argument and initializes the class variable val with the given argument val.
    def __init__(self, val):
        self.val = val
        # Initializing the next Pointer(Last Node Pointer to None i.e Null).
        self.nextPtr = None
  # Create a Class Which Creates the LinkedList by connecting all the nodes.


class LinkedList:
  # Inside the class, the constructor Initialize the head pointer to None(Null) and the last Node pointer to Null.
    def __init__(self):
        self.headPtr = None
        self.lastNode = None
    # Create a function addElements() inside the class which accepts the data value as an argument and add this node to the LinkedList.

    def addElements(self, val):
        # Check if the lastNode Pointer is None using the if conditional statement.
        if self.lastNode is None:
          # If the above if condition is true(If there are no elements in the linked list)
          # then Create a Node using the Node class by passing the data as an argument.
          # Initialize the head with the above node.
            self.headPtr = Node(val)
            self.lastNode = self.headPtr
        else:
          # Else Create the new node and initialize the last node pointer Value to the new node.
            self.lastNode.nextPtr = Node(val)
            # Set the last node Pointer Value to the Next Pointer.
            self.lastNode = self.lastNode.nextPtr
    # Create a function SearchElement() inside the class which accepts the element as argument
    # and searches whether the given element is present in the LinkedList or not

    def SearchElement(self, elem):
      # Take a Pointer that points to the nodes of the LinkedList and initialize its value to the Head Pointer.
        temPtr = self.headPtr
        # Loop till the temPtr is None(null) using the while loop.
        while temPtr is not None:
            # Check if the value of the node is equal to the given element using the if conditional statement
            if(temPtr.val == elem):
                # If it is true then return True
                return True
            # Else Increment the temPtr to the Next Node.
            temPtr = temPtr.nextPtr
        #Return False(Element is not Found)
        return False
# Take an object for the LinkedList Class and store it in a variable.
lkdList = LinkedList()
# Add elements to the LinkedList by using the below steps.
n = int(input('Enter the number of elements you wish to add in the linked list = '))
# Loop till the above number of elements using the For loop.
for i in range(n):
    # Give the data value as user input and store it in a variable.
    val = int(input('Enter data item: '))
    # Pass the above value as an argument to the addElements() function to add this value as a node to the LinkedList.
    lkdList.addElements(val)
#Give the element to search as user input and store it in a variable
elem=int(input('Enter the element to search in the LinkedList : '))    
# Printing whether the element is present or not in the LinkedList by calling the SearchElement() of the above object.
print(lkdList.SearchElement(elem))

Output:

Enter the number of elements you wish to add in the linked list = 7
Enter data item: 2
Enter data item: 11
Enter data item: 5
Enter data item: 9
Enter data item: 7
Enter data item: 17
Enter data item: 14
Enter the element to search in the LinkedList : 7
True