Linked list Deletion in Python: At beginning, End, Given location

In this tutorial, we are going to learn the python program to create a singly linked list and delete a node at the beginning, at the end, and at the given location of the singly linked list.

Problem Statement

Our program will delete an element at the beginning, at the end, and at the given location of the linked list.

For example:

What is singly linked list?

A linked list is the collection of elements that are connected via the memory address of successor elements. Or it is an unordered collection of data that is connected via links. Each data element has another block containing the address of the next elements 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 which factors to the following detail inside the listing. Each element within the singly connected list is referred to as a node. Each node has two components: data and next pointer, which factors the following node within the listing. The first node of the list is the head, and the closing node of the list is called a tail. The last node of the list contains a pointer to the null. Each node in the list can be 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 this 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

Delete element of the beginning of single linked list

In this case, the new list is deleted at the beginning of the linked list.

Deleting an element at the beginning of the linked list involves some logic:-

i. Delete the pointer of the first node which is pointing to the next node.

ii. Change the head pointer to the next node.

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

def delete_first(self):
    if self.head is not None:
        # store the current head in a temp variable
        temp = self.head
        # move head to the next node
        self.head = self.head.next
        # delete temp (optional in Python due to garbage collection)
        del temp
        print("First node deleted successfully.")
    else:
        print("List is already empty. Nothing to delete.")

Delete element of the given position of singly linked list

In this method, a node is deleted at the position specified by the user.

Logic to delete an element at given location:-

i. Traverse the node to one previous to the delete location specified by the user and check if it is null or not.

ii. If it is not null, change the next pointer of the previous node and the next of node which needs to be deleted as Null.

iii. If the input location is null, then the position does not exist.

Let’s look on the program to delete an element at the given location of linked list.

def delete_at_position(self, element):
	# create a temp node to store head
	temp=self.head
	if(temp != None):
		if(temp.data == element):
			self.head=self.next
			temp = None
			return
	# tracking the node that need to be deleted
	while(temp != None):
		if(temp.data == element):
			break
		prev = temp
		temp = temp.next
	if(temp == Null):
		return
	prev.next = temp.next
	temp = None

Delete the last element of singly linked list

In this case, the node is deleted at the end of the linked list.

Deleting an element at the end of the linked list involves some logic:-

i. Traverse to the previous element to last element of the list.

ii. Make the next pointer of the previous node Null.

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

def delete_last(self):
    if self.head is None:
        print("List is already empty. Nothing to delete.")
        return

    # If there is only one node in the list
    if self.head.next is None:
        self.head = None
        print("Last node deleted successfully.")
        return

    # Traverse to the second last node
    temp = self.head
    while temp.next.next is not None:
        temp = temp.next

    # Delete the last node
    print(f"Deleted node with value: {temp.next.data}")
    temp.next = None

Python code to delete an element from the singly linked list

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

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

    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

    def delete_first(self):
        if self.head is not None:
            print(f"Deleted first element: {self.head.data}")
            self.head = self.head.next
        else:
            print("List is already empty.")

    def delete_last(self):
        if self.head is None:
            print("List is already empty.")
            return
        if self.head.next is None:
            print(f"Deleted last element: {self.head.data}")
            self.head = None
            return
        temp = self.head
        while temp.next.next is not None:
            temp = temp.next
        print(f"Deleted last element: {temp.next.data}")
        temp.next = None

    def delete_at_position(self, position):
        if self.head is None:
            print("List is empty.")
            return
        if position == 0:
            print(f"Deleted element at position 0: {self.head.data}")
            self.head = self.head.next
            return
        temp = self.head
        index = 0
        prev = None
        while temp is not None and index < position:
            prev = temp
            temp = temp.next
            index += 1
        if temp is None:
            print("Position out of range.")
        else:
            print(f"Deleted element at position {position}: {temp.data}")
            prev.next = temp.next

    def PrintList(self):
        temp = self.head
        if temp is not None:
            print("The list contains:", end=" ")
            while temp is not None:
                print(temp.data, end=" ")
                temp = temp.next
            print()
        else:
            print("The list is empty.")

# ---- Main Program ----
MyList = LinkedList()

print("\nMenu:")
print("1 - Add element")
print("2 - Delete first element")
print("3 - Delete last element")
print("4 - Delete element at position")
print("5 - Display list")
print("0 - Exit")

while True:
    try:
        choice = int(input("\nEnter your choice: "))
        if choice == 1:
            data = int(input("Enter the element to add: "))
            MyList.push_back(data)
        elif choice == 2:
            MyList.delete_first()
        elif choice == 3:
            MyList.delete_last()
        elif choice == 4:
            position = int(input("Enter the position to delete (0-based index): "))
            MyList.delete_at_position(position)
        elif choice == 5:
            MyList.PrintList()
        elif choice == 0:
            print("Exiting program.")
            break
        else:
            print("Invalid choice. Please try again.")
    except ValueError:
        print("Please enter a valid integer.")

Output

Menu:
1 - Add element
2 - Delete first element
3 - Delete last element
4 - Delete element at position
5 - Display list
0 - Exit

Enter your choice: 1
Enter the element to add: 2

Enter your choice: 1
Enter the element to add: 4

Enter your choice: 1
Enter the element to add: 6

Enter your choice: 1
Enter the element to add: 3

Enter your choice: 4
Enter the position to delete (0-based index): 1
Deleted element at position 1: 4

Enter your choice: 5
The list contains: 2 6 3 

Enter your choice: 0
Exiting program.