Sorting a Linked List Data Structure | DSA Tutorial

Sorting linked list: There are many algorithms to sort a linked list, like the bubble sort, merge sort, etc., so today we are going to sort a linked list by exchanging the values of nodes using the bubble sort algorithm.

Sorting a linked list using the bubble sort algorithm

In a bubble sort algorithm to sort a linked list that has n items, we need to iterate over the list n-1 times. Like in the example, we have a list of 5 items, then we need to iterate over the list for 4 times.

To sort a linked list, first, we need three references: p, q, and end. In the first iteration, we set the end variable to None. And in every iteration, we set the p variable to the first node of the list and the q variable to the second node of the list.

If in the iteration the value of the linked part of node p is equal to the end, then we break the iteration and continue to the next iteration.

If the info part of node p is greater than the info part of node q, then we swap the values of node p and q; otherwise, we refer p and q to the next node of the list. So in the given example list, the value of node p is not greater than the value of the q node, so we refer to p and q as the next node of the list.

Here, the value of node p is not greater than the value of node q, so we go to the next nodes.

Here, the value of node p is greater than the value of node q, so we swap them.

Next, we go to the next nodes. Here, the value of node p is not greater than the value of node q, so we don’t swap them.

Now we go to the next nodes of the list. Here, the value of the linked part of node p is equal to the end variable. So here the first iteration ends.

Now, after iteration one ends, the last node of the list becomes sorted, so we refer to the end variable as the last node of the list.

Now the second iteration starts, and in the second iteration, we refer to the variables p and q as the first and second node of the list and swap the values of nodes p and q if the value of node p is greater than the value of node q.

This condition will run till the linked part of node p does not become equal to the end variable, as you see in the figures below.

And after every iteration, we update the value of the variable end. because if we iterate the list over two times, then the last two nodes of the list become sorted. So we don’t need to check them again.

So after performing the n-1 iterations over the linked list. where n is the size of the list. Now our list becomes sorted.

def bubble_sort_exdata(self):
    end = None
    while end != self.start.link:
        p = self.start
        while p.link != end:
            q = p.link
            if p.info > q.info:
                p.info, q.info = q.info, p.info
            p = p.link
        end = p

def bubble_sort_exdata(self):
    end = None
    while end != self.start.link:
        p = self.start
        while p.link != end:
            q = p.link
            if p.info > q.info:
                p.info, q.info = q.info, p.info
            p = p.link
        end = p