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
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.
class Node:
def __init__(self, data=None):
self.data = data
self.next = None
class LinkedList:
def __init__(self):
self.head = None
self.head = NoneTraversal 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.
def traverse(self):
next_node=self.head
while(next_node != 0):
next_node = next_node.nextInserting 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.
def pushLast(self, newElement):
#create new node and assign new data
newNode=Node(newElement)
#check if linked list is empty
if(self.head == None):
self.head = newNode
return
else:
#traverse to last
temp = self.head
while(temp.next != None):
temp = temp.next
#change the nest node to the last node
temp.next=newNodeSearching 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.
Python Program to search an element in Singly Linked List
class Node:
def __init__(self, data):
self.data = data
self.next = None
# Singly Linked List class
class SinglyLinkedList:
def __init__(self):
self.head = None
# Add element at the end of the list
def push_back(self, newElement):
newNode = Node(newElement)
if self.head is None:
self.head = newNode
else:
temp = self.head
while temp.next is not None:
temp = temp.next
temp.next = newNode
# Search for an element
def search(self, ele):
temp = self.head
pos = 1
while temp:
if temp.data == ele:
print(f"{ele} is found at position = {pos}")
return
temp = temp.next
pos += 1
print(f"{ele} is not found in the linked list.")
# Display all elements
def show(self):
temp = self.head
if temp is None:
print("The list is empty.")
else:
print("The list elements are:", end=" ")
while temp:
print(temp.data, end=" ")
temp = temp.next
print()
# Main logic with improved menu
s = SinglyLinkedList()
while True:
print("\nMenu:")
print("1. Add element to the linked list")
print("2. Display the linked list")
print("3. Search for an element in the linked list")
print("0. Exit")
try:
choice = int(input("Enter your choice: "))
except ValueError:
print("Please enter a valid number.")
continue
if choice == 1:
try:
val = int(input("Enter element to add: "))
s.push_back(val)
except ValueError:
print("Invalid input. Please enter a number.")
elif choice == 2:
s.show()
elif choice == 3:
try:
key = int(input("Enter element to search: "))
s.search(key)
except ValueError:
print("Invalid input. Please enter a number.")
elif choice == 0:
print("Exiting...")
break
else:
print("Invalid choice. Please select from the menu.")
Output
Menu:
1. Add element to the linked list
2. Display the linked list
3. Search for an element in the linked list
0. Exit
Enter your choice: 1
Enter element to add: 6
Menu:
1. Add element to the linked list
2. Display the linked list
3. Search for an element in the linked list
0. Exit
Enter your choice: 1
Enter element to add: 7
Menu:
1. Add element to the linked list
2. Display the linked list
3. Search for an element in the linked list
0. Exit
Enter your choice: 1
Enter element to add: 3
Menu:
1. Add element to the linked list
2. Display the linked list
3. Search for an element in the linked list
0. Exit
Enter your choice: 2
The list elements are: 6 7 3
Menu:
1. Add element to the linked list
2. Display the linked list
3. Search for an element in the linked list
0. Exit
Enter your choice: 3
Enter element to search: 7
7 is found at position = 2
Menu:
1. Add element to the linked list
2. Display the linked list
3. Search for an element in the linked list
0. Exit
Enter your choice: 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’.