Python Bubble Sort to sort a Linear Linked List

Elements of a linear linked list can be sorted in many ways. In this post We will use Python Bubble Sort to sort a Linear linked list.

Working of Python Bubble Sort

Bubble sort works in passes, comparisons and interchanges. A pass is a complete round in which elements are compared and the biggest element still to be sorted, Bubbles out to its correct position.  

In a pass one element is compared with its next element. If the element is bigger than the next one, they are interchanged. If the element is smaller than its next element then no interchange takes place. The next element is then compared with its next element. This process is continued till the second last element is compared with the last element.

The total numbers of passes are one less than the total number of elements to be sorted. If N is the number of elements then number of passes is N-1. 8 elements will be sorted in 7 passes, 18 elements will be sorted in 17 passes and 100 elements will be sorted in 99 passes.

The number of comparisons in each pass is equal to Number of elements – the pass number. If N is the number of elements and Kth pass is being processed, then the number of comparisons is N-K. If you begin the number of passes with zero then the number of comparisons in Kth Pass will be N-K-1.

Python Bubble Sort Program for Linear Linked List

In this program the linear liked list is created using the user defined class Node. A node represents an element of the linked list with data and link part.

User defined class LinearList has two data members, start and nodecount. Start pointer stores address of first element of the linked list. Nodecount stores the number of nodes in the Linear Linked List.

The nodes of the linked list are added at the beginning. Every time a new node is added nodecount is incremented to update the number of nodes.

#user defined class for nodes
class Node:
    def __init__(self, data=None, link=None):
    def __str__(self):
        return str(

#user defined class for Linked list
class LinearList:
    def __init__(self, start=None,nodecount=0):
        self.nodecount=nodecount #stores number of nodes in linked list
    def addBegNode(self, value=None):#Adding nodes at beginning

    def printList(self):#traverse abd display nodes
        while ptr:
    def bubbsort(self):
        for i in range(self.nodecount-1):#for controlling passes of Bubble Sort
            while nxt:#Comparisons in passes
                    if prev==None:
#Create blank Linked List        
numele= input('How many elements to be added in the Linked List??')
#add nodes at begging in the Linked List
for cnt in range(int(numele)):
    ele= input('Enter a value to be added at the beginning of the Linked List ')
#Print Linked List  before sorting  
print("Linked List Initially")
#Print Linked List  After sorting  
print("Linked List after sorting")
Comparing First node with second node
Comparing a node with its next node


Python Bubble Sort Output

Be First to Comment

Leave a Reply

Your email address will not be published.