Deletion in Linked list | Data Structure

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 of the node.

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

Deletion in Linked List

1. Deletion of the first node
2. Deletion of the only node
3. Deletion in between the node
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

like if we have a list that has only one node.

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

so now our list becomes empty.

self.start = None

self.start = None

Deletion in 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 the image given below.

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 we see in the image given below.

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