Linked list can have various variations of the insert, delete, get and sort operations. The first 3 operations can be done at any point in the list. In this article that is a follow up to my previous article about linked lists I explain two more methods/operations that can be associated with linked lists. These are:

Delete
Sort

1. Delete

In the delete operation I'm going to focus on deleting a node given its data and deleting a node given its index.

Delete node given its data

We first check the head node and if the data matches we set the head to the next node and set the current head to None.

If the head does not contain the data we traverse the entire list while comparing the data to each node point with the data we have keeping track of the previous and current node. If its a match, we break out of the loop and link the previous node to the node after the current node. Then we set the current node to None.

# delete at node
    def delete_node(self,key):
        temp = self.head
        # if the head contains the key
        if temp is not None:
            if temp.data == key:
                self.head = temp.next #set head to the next node
                temp = None # free up space occupied by the node
                return
        # search for key in the list while keeping track of the previous node
        while(temp):
            if temp.data == key:
                break
            prev = temp
            temp = temp.next

        #  if list if empty or key not in list
        if(temp is None):
            # return
            raise Exception('Key not in list')

        # unlink the node to be deleted from the list
        prev.next = temp.next
        temp = None

Delete node given its index

If the position/index is zero we set the head to the next node and set the current head to None.

If the index is greater than zero, we traverse the entire list while keeping track of the current index in the list and comparing it with the given list position. We also have to keep track of the current and previous nodes. If its a match, we break out of the loop and link the previous node to the node after the current node. Then we set the current node to None.

# delete at given position
    def del_at_position(self,position):
        # check if the list is empty
        if self.head == None:
            return
        # check if the position is 0 then just delete the head 
        if position == 0:
            self.head = self.head.next
            return self.head
        # traverse the list looking for the position
        #  keep track of the list index, current node, previous node 
        index =0
        current = self.head
        prev = self.head 
        temp = self.head

        while current is not None:
            if index ==position:
                temp= current.next
                break
            prev = current
            current = current.next
            index +=1
        prev.next = temp
        return prev

Sort the elements of a linked list

Sorting can be implemented in many different ways using any of the available sorting algorithms. Here, I'm going to use a simple variation the of the bubble sort algorithms. We will traverse the entire list while comparing adjacent items in the list. If the previous node is greater than the next node then we swap their positions. We do this till the entire list is sorted.

    # sort list
    def sort_list(self):
        current = self.head
        index= Node(None)
        if current is None:
            return
        while current is not None:
            index = current.next
            while index is not None:
                if current.data>index.data:
                    current.data, index.data = index.data, current.data
                index = index.next
            current = current.next

DSA is a continuous subject and the more you practice everyday the better you become! The entire code for the linked list can be found here

Linked list deletion and sorting

1. Delete