Create a sorted list

[alkeshtech]

Hi guys,
I am wondering how can I create a sorted linked list, without using Collection.sort(). Is there a way I can add element in a list in a sorted fashion?

[JamesCherrill]

Whenever you add an element, iterate thru the existing list elements until you find the right place to insert the new element. That way the list will always be in sorted order

[powerage]

I too am trying to figure this one out. I am looping through the list but what happens when you get to the end() and the condition is never met for the insert? I tried after the loop:

std::list<Entry>::iterator i = entryList.begin();
for(; i != entryList.end(); i++){
  if (i < entry)
     entryList.insert(i,entry);
  }
}
// this does not seem to work!
if ( i == entryList.end())
     entryList.push_back(entry);

what does work is:

entryList.push_front(entry);
entryList.sort();

Fine for small lists but would imagine take a toll on larger ones!

[powerage]

I too am trying to figure this one out. I am looping through the list but what happens when you get to the end() and the condition is never met for the insert? I tried after the loop:

std::list<Entry>::iterator i = entryList.begin();
for(; i != entryList.end(); i++){
  if (i < entry)
     entryList.insert(i,entry);
  }
}
// this does not seem to work!
if ( i == entryList.end())
     entryList.push_back(entry);

what does work is:

entryList.push_front(entry);
entryList.sort();

Fine for small lists but would imagine take a toll on larger ones!

Figured out my problem. I wasn't breaking out of the loop and it was adding the entries that met the condition twice. Once in the for loop and then once after it because the iterator was at the end every time!

[JamesCherrill]

I too am trying to figure this one out. I am looping through the list but what happens when you get to the end() and the condition is never met for the insert?

In that case the new element must belong on the end of the list (ie sorts after every existing entry)

[Andreas Hollman]

Hi guys,
I am wondering how can I create a sorted linked list, without using Collection.sort(). Is there a way I can add element in a list in a sorted fashion?

I used the happy-collections library (Apache License Version 2.0) to decorate LinkedList with a SortedList decorator. To increase the performance of the sorted List you should use decorated TreeList from appache Collections (here is an benchmark test).

// create SortedList
List<Integer> sortedList = 
	Collections_1x0.sortedList( 
			new LinkedList<Integer>(),//list
			new Comparator<Integer>() {
				@Override
				public int compare(Integer o1, Integer o2) {
					return o1.compareTo(o2);
				}
			}, //comparator
			SortType.Linked,//type defines the sorting algorithm
			false,//inverted
			true//doSort
			);

// add some elements
sortedList.add(2);
sortedList.add(9);
sortedList.add(7);
sortedList.add(4);
sortedList.add(4);
sortedList.add(8);
sortedList.add(1);
sortedList.add(5);
sortedList.addAll(Arrays.asList(new Integer[] { 5, 0, 6, 5, 3, 4 }));
// print sorted list
for (Integer i : sortedList) {
	System.out.print(i + ", ");
}