Question

how do you write a bubble sort function in python that sorts a linked list and if any duplicate are placed bext ti each other?

Answer 1

# -*- coding: utf-8 -*-
"""
Created on Wed Sep 18 11:50:03 2019

@author: pavan
"""

# -*- coding: utf-8 -*-
"""
Created on Wed Sep 18 11:24:11 2019

@author: pavan
"""
#creating a node which contains data and referrence of next node
class Node:
    def __init__(self, data):
        self.item = data
        self.next = None
#creating a linked list which contains following functions
#printing linked list
#inserting new node to the linked list
# sort function gives us the sorted linked list using bubble sort     
class linkedlist:
    def __init__(self):
        self.root = None
    def printing_list(self):#checks the empty condition for linked list
      if self.root is None:
          print("List is empty")
          return
      else:
         n = self.root
         while n is not None:
            print(n.item , " ")#printing data inside every node sequencially
            n = n.next
    def insertingnode(self, data):
        new_node = Node(data)
        if self.root is None:
            self.root = new_node
            return
        n = self.root
        while n.next is not None:
            n= n.next
        n.next = new_node;#inserting a new node to the linked list at the end
    def sort(self):#this is the actual bubble sort code
        if self.root is None:
          print("List has no element")
          return
        else:
           n = self.root
           while n is not None:
               k=self.root
               while k.next is not None:
                     if(k.item>k.next.item):#checking adjacent node's data#swap if those are not in ascending order
                         t=k.item
                         k.item=k.next.item
                         k.next.item=t
                     k=k.next
               n=n.next
             
            
new_linkedlist = linkedlist()#creating an object to the linkedlist class
#inserting nodes to the linked list
new_linkedlist.insertingnode(5)
new_linkedlist.insertingnode(15)
new_linkedlist.insertingnode(10)
new_linkedlist.insertingnode(15)
new_linkedlist.insertingnode(5)

#sorting and printing linked list
new_linkedlist.sort()
new_linkedlist.printing_list()

output for the above code