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

linked list deletion

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:

Case1: If the user inputs the linked list elements as 1,2,3,4,5 and wants to delete an element at the beginning of the linked list.

                    The output should be 2 3 4 5.

Case2: If the user inputs the elements of the linked list as 1, 2, 3, 4, 5 and wants to delete an element at the end of the linked list.

                    The output should be 1, 2, 3, 4.

Case3: If the user inputs the elements of the linked list as 1, 2, 3, 4, 5 and wants to delete an element after element at location 2.

                    The output should be 1, 3, 4, 5.

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.

Python linked list creation

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

Delete element of the beginning of single linked list

linked list deletion python program at beginning

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.

Delete element of the given position of singly linked list

linked list deletion python program at given position

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.

Delete the last element of singly linked list

linked list deletion python program at end

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.

Now let’s have a look at the algorithm of our program.

Algorithm to delete an element from single linked list

Step 1: Start

Step 2: create function delete_first(), delete_last(), and delete_at_location().

Step 3: ask the user about which operation he/she wants.

Step 4: if(delete_first):

Call function delete_first(self).

   elif( delete at ‘k’ position):

Take a position as inputs from the user.

Call function delete_at_location(self, position)

elif( delete at last):

Call function delete_last(self).

Step 5: print the linked list

Step 6: Stop

Python code to delete an element from the singly linked list

Output:

Explanation:

For the input linked list 1à2à3, the user deleted position 2 and print the final linked list, 1à2 as the output.

[Note: the indexing of elements starts from 0 ]

Output:

Explanation:

For the input linked list 9–>8–>0–>54–>500–>65–>101,

          The user performs the following operations:

i. Delete the first element of the linked list, the list becomes

8–>0–>54–>500–>65–>101

ii. Delete the last element of the linked list, the list becomes

8–>0–>54–>500–>65

iii. Delete the element at position 3 from the start, the list becomes

8–>0–>54–>65

[Note: the indexing of elements starts from 0 ]