Use app×
Join Bloom Tuition
One on One Online Tuition
JEE MAIN 2025 Foundation Course
NEET 2025 Foundation Course
CLASS 12 FOUNDATION COURSE
CLASS 10 FOUNDATION COURSE
CLASS 9 FOUNDATION COURSE
CLASS 8 FOUNDATION COURSE
+2 votes
1.9k views
in Computer by (69.2k points)

Formulate an algorithm to perform insertion sort on a linked list. 

1 Answer

+3 votes
by (69.7k points)
selected by
 
Best answer

Simple Insertion sort is easily adaptable to singly linked list. In this method there is an array link of pointers, one for each of the original array elements. Initially link[i] = i + 1 for 0 < = I < n-1 and link [n-1] = -1. Thus the array can be thought of as a linear link list pointed to by an external pointer first initialized to 0. To insert the kth element the linked list is traversed until the proper position for x[k] is found, or until the end of the list is reached. At that point x[k] can be inserted into the list by merely adjusting the list pointers without shifting any elements in the array. This reduces the time required for insertion but not the time required for searching for the proper position. The number of replacements in the link array is O (n).

Each node from the unsorted linked list is to be detached one by one from the front and attached to the new list pointed by s head. While attaching, the value got stored in each node is considered so that it is inserted at the proper position. 

Welcome to Sarthaks eConnect: A unique platform where students can interact with teachers/experts/students to get solutions to their queries. Students (upto class 10+2) preparing for All Government Exams, CBSE Board Exam, ICSE Board Exam, State Board Exam, JEE (Mains+Advance) and NEET can ask questions from any subject and get quick answers by subject teachers/ experts/mentors/students.

Categories

...