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.
[elementor-template id=”5256″]
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
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
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.
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.
[elementor-template id=”5253″]
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.
- Create a temp variable to store head
- 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:
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:
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”.
[elementor-template id=”5257″]