Friday, October 11, 2013

Inserting an element into a sorted linked list

Given a sorted linked list, how do we insert data into the list in proper order?

This is nothing but a step in insertion sort. Simply iterate through the elements to find the position for given number and insert at that position.

Here is the Java code to do that. I have used the LinkedList class available in java utilities so that we need not implement the entire linked list class on our own.


import java.util.LinkedList;
import java.util.ListIterator;

/**
 * Created with IntelliJ IDEA.
 * User: Ravi
 * Date: 10/11/13
 * Time: 5:32 AM
 * To change this template use File | Settings | File Templates.
 */
public class SortedListDemo {
    public static void main(String[] args)
    {
        LinkedList<Integer> sortedList = new LinkedList<Integer>();

        sortedInsert(sortedList, 3);
        sortedInsert(sortedList, 1);
        sortedInsert(sortedList, 6);
        sortedInsert(sortedList, 4);
        sortedInsert(sortedList, 2);
        sortedInsert(sortedList, 5);

        System.out.println("Contents of the sorted list: " + sortedList);
    }
    public static void sortedInsert(LinkedList<Integer> sList, int data)
    {
        int pos = 0;

        for(int listData : sList )
        {
            if( listData > data)
                break;
            pos++;
        }

        //Alternative code for the above loop using an iterator
        /*
        ListIterator<Integer> listIterator = sList.listIterator();
        while( listIterator.hasNext() && listIterator.next() < data )
            pos++;
        */
        //insert the data in its correct position
        sList.add(pos, data);
    }
}