Member Avatar for 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?

  • 4 Contributors
  • 5 Replies
  • 122 Views
  • 3 Months Discussion Span
  • Latest Post Latest Post by Andreas Hollman

Dani AI

Generated

A few practical ways to keep a Java list sorted on every add, with tradeoffs and a safe insertion pattern you can reuse.

First, for a LinkedList the usual fast-and-simple approach is to walk the list with a ListIterator and insert at the first spot that compares greater-or-equal. That avoids a global sort on each add and keeps insertion O(n) in the worst case (scan) with O(1) local insertion. Note the common pitfall ran into: stop (return) immediately after inserting, otherwise the iterator will keep moving and you can end up adding the same element again. already hinted at inserting in place; the snippet below shows a concise, correct way to do it using a Comparator.

public static <T> void insertSorted(LinkedList<T> list, T value, Comparator<? super T> cmp) {
    ListIterator<T> it = list.listIterator();
    while (it.hasNext()) {
        T cur = it.next();
        if (cmp.compare(value, cur) <= 0) {
            it.previous();
            it.add(value);
            return;
        }
    }
    it.add(value); // append at end
}

Alternatives and when to use them:

  • ArrayList + Collections.binarySearch to find insertion index, then list.add(index, value). Searching is O(log n) but insertion is O(n) because of shifting.
  • TreeSet / TreeMap give O(log n) inserts and ordered traversal, but TreeSet removes duplicates; use a TreeMap with counts or a multiset implementation if duplicates matter.
  • PriorityQueue is great for repeated min removals but does not present a sorted view for iteration.
  • For concurrent access consider ConcurrentSkipListSet/Map (sorted, concurrent).

Practical guidance: for few inserts or streaming inserts, insert-on-add is fine. For many inserts followed by reads, collecting then calling Collections.sort once is often faster. If you want library help (as mentioned), pick one that matches semantics (multiset vs set, stable ordering) and check benchmarks before using for large data.

Recommended Answers

All 5 Replies

Member Avatar for 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

Member Avatar for 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!

Edited by powerage because: n/a
Member Avatar for 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!

Member Avatar for 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)

Member Avatar for 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 (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 ).

// 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 + ", ");
}
Be a part of the DaniWeb community

We're a friendly, industry-focused community of developers, IT pros, digital marketers, and technology enthusiasts meeting, networking, learning, and sharing knowledge.