We have discussed Insertion Sort for arrays. In this article we discuss about linked list.
Singly Linked List:
Singly Linked List is a collection of ordered set of elements. A Node in singly linked list has two parts – data part and link part. Data part of the node contains the actual information which is represented as node. Link part of the node contains address of next node linked to it.
It can be traversed in only one direction because the node stores only next pointer. So, it can’t reverse linked list.
Algorithm for Insertion Sort for Singly Linked List :
- Create an empty sorted (or result) list
- Traverse the given list, do following for every node.
- Insert current node in sorted way in sorted or result list.
- Change head of given linked list to head of sorted (or result) list.
Insertion Sort for Singly Linked List:
In C language, program is given below:
[pastacode lang=”c” manual=”%2F*%20C%20program%20for%20insertion%20sort%20on%20a%20linked%20list%20*%2F%0A%23include%3Cstdio.h%3E%0A%23include%3Cstdlib.h%3E%0A%20%0A%2F*%20Link%20list%20node%20*%2F%0Astruct%20node%0A%7B%0A%20%20%20%20int%20data%3B%0A%20%20%20%20struct%20node*%20next%3B%0A%7D%3B%0A%20%0A%2F%2F%20Function%20to%20insert%20a%20given%20node%20in%20a%20sorted%20linked%20list%0Avoid%20sortedInsert(struct%20node**%2C%20struct%20node*)%3B%0A%20%0A%2F%2F%20function%20to%20sort%20a%20singly%20linked%20list%20using%20insertion%20sort%0Avoid%20insertionSort(struct%20node%20**head_ref)%0A%7B%0A%20%20%20%20%2F%2F%20Initialize%20sorted%20linked%20list%0A%20%20%20%20struct%20node%20*sorted%20%3D%20NULL%3B%0A%20%0A%20%20%20%20%2F%2F%20Traverse%20the%20given%20linked%20list%20and%20insert%20every%0A%20%20%20%20%2F%2F%20node%20to%20sorted%0A%20%20%20%20struct%20node%20*current%20%3D%20*head_ref%3B%0A%20%20%20%20while%20(current%20!%3D%20NULL)%0A%20%20%20%20%7B%0A%20%20%20%20%20%20%20%20%2F%2F%20Store%20next%20for%20next%20iteration%0A%20%20%20%20%20%20%20%20struct%20node%20*next%20%3D%20current-%3Enext%3B%0A%20%0A%20%20%20%20%20%20%20%20%2F%2F%20insert%20current%20in%20sorted%20linked%20list%0A%20%20%20%20%20%20%20%20sortedInsert(%26sorted%2C%20current)%3B%0A%20%0A%20%20%20%20%20%20%20%20%2F%2F%20Update%20current%0A%20%20%20%20%20%20%20%20current%20%3D%20next%3B%0A%20%20%20%20%7D%0A%20%0A%20%20%20%20%2F%2F%20Update%20head_ref%20to%20point%20to%20sorted%20linked%20list%0A%20%20%20%20*head_ref%20%3D%20sorted%3B%0A%7D%0A%20%0A%20%0A%2F*%20function%20to%20insert%20a%20new_node%20in%20a%20list.%20Note%20that%20this%0A%20%20function%20expects%20a%20pointer%20to%20head_ref%20as%20this%20can%20modify%20the%0A%20%20head%20of%20the%20input%20linked%20list%20(similar%20to%20push())*%2F%0Avoid%20sortedInsert(struct%20node**%20head_ref%2C%20struct%20node*%20new_node)%0A%7B%0A%20%20%20%20struct%20node*%20current%3B%0A%20%20%20%20%2F*%20Special%20case%20for%20the%20head%20end%20*%2F%0A%20%20%20%20if%20(*head_ref%20%3D%3D%20NULL%20%7C%7C%20(*head_ref)-%3Edata%20%3E%3D%20new_node-%3Edata)%0A%20%20%20%20%7B%0A%20%20%20%20%20%20%20%20new_node-%3Enext%20%3D%20*head_ref%3B%0A%20%20%20%20%20%20%20%20*head_ref%20%3D%20new_node%3B%0A%20%20%20%20%7D%0A%20%20%20%20else%0A%20%20%20%20%7B%0A%20%20%20%20%20%20%20%20%2F*%20Locate%20the%20node%20before%20the%20point%20of%20insertion%20*%2F%0A%20%20%20%20%20%20%20%20current%20%3D%20*head_ref%3B%0A%20%20%20%20%20%20%20%20while%20(current-%3Enext!%3DNULL%20%26%26%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20current-%3Enext-%3Edata%20%3C%20new_node-%3Edata)%0A%20%20%20%20%20%20%20%20%7B%0A%20%20%20%20%20%20%20%20%20%20%20%20current%20%3D%20current-%3Enext%3B%0A%20%20%20%20%20%20%20%20%7D%0A%20%20%20%20%20%20%20%20new_node-%3Enext%20%3D%20current-%3Enext%3B%0A%20%20%20%20%20%20%20%20current-%3Enext%20%3D%20new_node%3B%0A%20%20%20%20%7D%0A%7D%0A%20%0A%2F*%20BELOW%20FUNCTIONS%20ARE%20JUST%20UTILITY%20TO%20TEST%20sortedInsert%20*%2F%0A%20%0A%2F*%20Function%20to%20print%20linked%20list%20*%2F%0Avoid%20printList(struct%20node%20*head)%0A%7B%0A%20%20%20%20struct%20node%20*temp%20%3D%20head%3B%0A%20%20%20%20while(temp%20!%3D%20NULL)%0A%20%20%20%20%7B%0A%20%20%20%20%20%20%20%20printf(%22%25d%20%20%22%2C%20temp-%3Edata)%3B%0A%20%20%20%20%20%20%20%20temp%20%3D%20temp-%3Enext%3B%0A%20%20%20%20%7D%0A%7D%0A%20%0A%2F*%20A%20utility%20function%20to%20insert%20a%20node%20at%20the%20beginning%20of%20linked%20list%20*%2F%0Avoid%20push(struct%20node**%20head_ref%2C%20int%20new_data)%0A%7B%0A%20%20%20%20%2F*%20allocate%20node%20*%2F%0A%20%20%20%20struct%20node*%20new_node%20%3D%20new%20node%3B%0A%20%0A%20%20%20%20%2F*%20put%20in%20the%20data%20%20*%2F%0A%20%20%20%20new_node-%3Edata%20%20%3D%20new_data%3B%0A%20%0A%20%20%20%20%2F*%20link%20the%20old%20list%20off%20the%20new%20node%20*%2F%0A%20%20%20%20new_node-%3Enext%20%3D%20(*head_ref)%3B%0A%20%0A%20%20%20%20%2F*%20move%20the%20head%20to%20point%20to%20the%20new%20node%20*%2F%0A%20%20%20%20(*head_ref)%20%20%20%20%3D%20new_node%3B%0A%7D%0A%20%0A%20%0A%2F%2F%20Driver%20program%20to%20test%20above%20functions%0Aint%20main()%0A%7B%0A%20%20%20%20struct%20node%20*a%20%3D%20NULL%3B%0A%20%20%20%20push(%26a%2C%205)%3B%0A%20%20%20%20push(%26a%2C%2020)%3B%0A%20%20%20%20push(%26a%2C%204)%3B%0A%20%20%20%20push(%26a%2C%203)%3B%0A%20%20%20%20push(%26a%2C%2030)%3B%0A%20%0A%20%20%20%20printf(%22Linked%20List%20before%20sorting%20%5Cn%22)%3B%0A%20%20%20%20printList(a)%3B%0A%20%0A%20%20%20%20insertionSort(%26a)%3B%0A%20%0A%20%20%20%20printf(%22%5CnLinked%20List%20after%20sorting%20%5Cn%22)%3B%0A%20%20%20%20printList(a)%3B%0A%20%0A%20%20%20%20return%200%3B%0A%7D” message=”c” highlight=”” provider=”manual”/]OUTPUT:
Linked List before sorting 30 3 4 20 5 Linked List after sorting 3 4 5 20 30[ad type=”banner”]