Python Program to Search an element in Singly 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.

class Node:
	def __init__(self, data=None):
		self.data = data
		self.next = None

class LinkedList:
	 def __init__(self):
		self.head = None
		self.head = None

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.

def traverse(self):
	next_node=self.head
	while(next_node != 0):
		next_node = next_node.next

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.

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=newNode

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.

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’.

What did you think?

Similar Reads

Hi, Welcome back!
Forgot Password?
Don't have an account?  Register Now