Apply Insertion Sort for Singly Linked List in Python
In this tutorial, we shall apply Insertion Sort on a singly linked list in Python. For starters, a Singly Linked List is a data structure in which the elements are “linked” via pointers.
In a singly linked list, every node consists of two parts:
1. Data
2. A pointer to the next node
A class Node is created with the attributes ‘data’ and ‘next’. The push function inserts the entered elements and updates the linked list in backward order.
1. Create an empty list (sorted_list) which will finally contain our result.
2. Traverse along the cur_list and for every node, we insert it in the correct position in sorted_list.
3. Return the sorted_list.
Insertion Sort for Singly Linked List
Below is our given Python program for applying insertion sort for the singly linked list:
class Node: def __init__(self, data): self.data = data self.next = None def insert_sort(href): sorted_list = None cur_list = href while (cur_list != None): next = cur_list.next sorted_list = sort(sorted_list, cur_list) cur_list = next href = sorted_list return href def sort(href, node): current = None if (href == None or href.data >= node.data): node.next = href href = node else: current = href while (current.next != None and current.next.data < node.data): current = current.next node.next = current.next current.next = node return href def printlist(head): temp = head while(temp != None): print(temp.data) temp = temp.next def push(href, data): node = Node(0) node.data = data node.next = href href = node return href # Driver program to test above functions a = None a = push(a, 15) a = push(a, 42) a = push(a, 31) a = push(a, 12) a = push(a, 100) a = insert_sort(a) print("\nLinked List after sorting ") printlist(a)
Output
Linked List after sorting 12 15 31 42 100
Thank You for Reading and Keep Learning 🙂
- Also Read: Bogo Sort in Python
Leave a Reply