Insertion Sort for Singly LInked List Using Python

Let's see How Insertion sort work on linked list.

In This Post we're gonna talk about Insertion Sort for singly linked list.

First Check out Basic Operation on Singly Linked list.

Code:

class LinkedList:

def __init__(self):

self.head = None

""" Insertion Sort"""

def insertionSort(self,head_ref):

sortedLL = None # sorted linked list for entering data in from main linked list

cur = head_ref

while cur:

nxt = cur.next # take cur.next in nxt bcz sortedInsert will overwrite cur

sortedLL = self.sortedInsert(sortedLL, cur)

cur = nxt

head_ref = sortedLL

return head_ref

def sortedInsert(self,head_ref, NewNode):

if head_ref is None or head_ref.data > NewNode.data:

NewNode.next = head_ref

head_ref = NewNode

else:

cur = head_ref

while cur.next != None and cur.next.data < NewNode.data:

cur = cur.next

NewNode.next = cur.next

cur.next = NewNode

return head_ref

Time Complexity:

• Best:𝛺(n)
• Average: Θ(n*n)
  
• Worst: O(n*n)

Space Complexity: O(1)

Note: if You have any suggestion put in comments.

Thank You 😊😊

Other Sorting Algorithms:

• Bubble Sort for Singly Linked list
• Merge Sort for Singly Linked List 
• Quick Sort for Singly Linked list