Deletion in Linked List Data Structure | DSA Tutorials

Deletion in Linked list – As we know, for performing operations on the linked list we need to find the reference to the node of the list. So, to delete a node from any position in the linked list, we need to first find the reference to the node.

And if you don’t know how to find the reference of a node in the linked list, then first complete reading this post – Operations on a linked list

Deletion in Linked List Data Structure

1. Deletion of the first node
2. Deletion of the only node
3. Deletion between the nodes
4. Deletion at the end of the list

Deletion of the first node from the linked list

As you see, we have a linked list that contains 5 items in it.

To delete the first node of the list, we need to point the start variable of the linked list to the second node of the list.

So now the first node of the linked list is deleted.

def delete_first_node(self):
    if self.start is None:
        return    self.start = self.start.link

def delete_first_node(self):
    if self.start is None:
        return    self.start = self.start.link

Deletion of the only node from the linked list

If we have a list that has only one node, as shown in Figure 4.

Then, to delete the only node of the list, we store the null or None value in the start variable.

So now our list becomes empty.

self.start = None

self.start = None

Deletion between the nodes of a linked list

To delete a node between the nodes of the linked list, first, we need to find the reference of the predecessor of the node that we want to delete. Like in the example given below, we want to delete the second and fourth nodes. So we want to delete the node that contains the value 30.

So we need to find the reference to the node that comes before the node that contains the value 30.

Then we refer the p node to the node that comes second after the node p, as you see in Figure 8.

Now the node is deleted from the list.

Deletion at the end of the linked list

To delete the last node, we need a reference to the second last node of the linked list, as shown in Figure 10.

After that, we set the linked part of p to null or None.

So now the last node of the linked list is deleted.

def delete_last_node(self):

    if self.start is None:
        return
    if self.start.link is None:
        self.start = None        return
    p = self.start
    while p.link.link is not None:
        p = p.link
    p.link = None

def delete_last_node(self):

    if self.start is None:
        return
    if self.start.link is None:
        self.start = None        return
    p = self.start
    while p.link.link is not None:
        p = p.link
    p.link = None