Python Program to Search an element in Singly linked list

python program to search element in linked list

In this tutorial, we will learn writing python program to perform search operation to find an element in the singly linked list.

Problem Statement

Our program takes the element of the linked list from the user as the input. And then, it takes another input from the user to search the element in the linked list. If the element is found at any position of the linked list, then it returns ‘element found’ otherwise it returns the ‘elements is not found’.

For example:

Case1: If the user input element 6 and search in the linked list as 1, 2, 3, 4.

                    The output should be “element is not present”.

Case2: If the user input 9 and search in the linked list as 7, 9, 1, 0.

                    The output should be “element found.

What is a Singly Linked List?

A linked list is the collection of elements that connects via the memory address of successor elements.

Or it is an unordered collection of data that connects the next node using a pointer. Each data element of the singly linked list has another block which contains the address of the next element of the linked list.

Creation of Singly Linked List

search program in python singly linked list

The singly linked list is a linear records shape wherein every element of the listing incorporates a pointer that points to the address of the next node. Each element within the singly linked list refers to a node. Each node has two components: data and next to the pointer, which factors the next node within the list. The first node of the list is the head, and the last node of the list is the tail. The last node of the linked list contains a pointer to the null. Each node in the linked list is linearly accessed with the help of traversing through the list from head to tail.

The linked list is created using the node class. We create a node object and another class to use the created node object.

Traversal of a Singly linked list

python singly linked list search operation

Traversing is the most common operation of the linked list, it means visiting every node of the linked list once and performing any operation usually, we insert, delete and also display the elements of the linked list. 

For traversing basic idea is to visit every node from head to the null value.

Inserting a Node at the end of the linked list

In this case, the new list is added at the end of the linked list.

Inserting a new element at the end of the linked list involves some logic:-

i. Create a new node of the linked list.

ii. Traverse to the last element of the list.

iii. Link the next pointer of the last node to the newly created list and the next pointer of the newly created list to Null.

search operation in python singly linked list

Let’s look at the program to insert an element at the last of the linked list.

Searching an element in Singly linked list

Searching an elements in linked list requires 2 variables.

i. One to track the search

ii. And other to track the index of the current node of the linked list

If head node is not null then, traverse through the elements of linked list and once desired element found, the traversal need to be stop and return the element position.

Algorithm to search an element in Singly Linked List

Step 1: Start

Step 2: Create a linked list

Step 3: Create pushLlast() function to push the elements of the liked list entered by user.

i. Create a new node of the linked list.

ii. Traverse to the last element of the list.

iii. Link the next pointer of the last node to the newly created list and the next pointer of the newly created list to Null.

Step 4: Create search() function to search the element entered by user, in the linked list.

  1. Create a temp variable to store head
  2.     if(temp != None):

      while (temp != None):

                              i += 1

                    if(temp.data == searchValue):

                              found += 1

                     break

                     temp = temp.next

          if(found == 1):

                                        print “element found”

         else:

                                        print “element not found”

Step 5: pass the value of element to search in search() function.

Step 6: Stop

Now let’s code the above algorithm in python code.

Python Program to search an element in Singly Linked List

Output 1:

python program to search in singly linked list

Explanation:

The creation of the linked list in this example is shown with steps below where all the elements get added at the end of the linked list: :

  • Head–>11 
  • Head–>11–>100
  • Head–>11–>100–>51
  • Head–>11–>100–>51–>98
  • Head–>11–>100–>51–>98–>500 

So, the generated linked list is 11–>100–>51–>98–>500. The user asks our program to search for the value 98 in the linked list. The element 98 is present in the list at location 4, the output generated is ‘the element found at position 4’.

Output 2:

searching element in singly linked list python

Explanation:

The linked list creation is shown below with the steps where all the elements get added at the end of the linked list:

  • Head–>1 
  • Head–>1–>2
  • Head–>1–>2–>3
  • Head–>1–>2–>3–>4
  • Head–>1–>2–>3–>4–>5
  • Head–>1–>2–>3–>4–>5–>6

So, the generated linked list is 1–>2–>3–>4–>5–>6. The user asks our program to search for the value 11 in the linked list. It can be observed that element 11 is not present in the list at any position, so the output is generated as “the element is not found”.