Single Link List

Single Link List

The following C++ code will explains the implementation of Single Link List.

The following implementation is in object oriented using the SingleLinkList class and sll object. The implemented ADT functions of Single Link List are insert, print, search, modify and delete.

Insertion sort

In insertion sort, we compares adjacent elements and swap them, if they are out of order. We take the next element and insert into the sorted list that we maintained in the beginning of the array and repeats the procedure on it and so on.

Advantages: 

Insertion sort provides several advantages

• Insertion sort takes advantage of pre-sorting
• Simple implementation
• Efficient for small data sets
• Stable: does not change the relative order of elements with equal keys
• O(1) extra space
• O(n²) comparisons and swaps
• Adaptive: O(n) time when nearly sorted
• Very low overhead
• Online: New elements can be added during the sort