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);
}
}