Friday, November 22, 2013

Inserting an element into sorted linked list

Given a sorted linked list write a program to insert data into it's correct position. 
For example consider the following linked list

1 -> 3 -> 4 -> 5 

Inserting 2 should change the list to

1 -> 2 -> 3 -> 4 -> 5

Inserting 0 should change it to

0 -> 1 -> 2 -> 3 -> 4 ->5

Inserting 6 should change it to

0 -> 1 -> 2 -> 3 -> 4 -> 5 -> 6. 

The three examples indicate three different cases to be considered while inserting into a sorted linked list.

Case 1: List can be empty or new element is added as the first element
Case 2: New element can be inserted anywhere in the middle of the linked list
Case 3: New element is added as the last element.

The following diagram illustrates the insert process.




In the following C++ program case 1 is handled in one block and case 2 and 3 are handled in the last block.