1

In Java I want to store elements in ascending order by size. Before insertion I need to treat all the smaller elements. So I start enumerating the list treating smaller elements, and when I meet a larger element, I want to insert the new node before this larger element. What data structure would be the good choice? ArrayList may not be a good choice as it shifts elements to the right when inserting in the middle. I looked at the API of LinkedList, but I do not find methods for inserting before/after a given node in the list. There is an add method that "inserts the specified element at the specified position in this list", but it requires the position as an integer. So does it mean that the Java implementation traverses the list from the beginning until it finds the specified position? It seems quite expensive. I have the position (a node) where I want to insert, just some references should be changed correctly to include the new node in the list. Any suggestions?

Thanks,

Jabba

Update: Thanks everyone for the answers, I could solve the problem with LinkedList using ListIterator. Then I made a comparative test and I got some surprising results. So, the goal is to maintain elements in a list/array in a sorted way. For this I compared four alternatives: (1) Vector, (2) ArrayList, (3) LinkedList, and (4) MyLinkedList, this is my own implementation (very simple). For the test I created an array with 1000 elements and I filled it with random integers between 1 and 100. Then I added these elements in each container in a loop. When this array was added 30 times: MyLinkedList (2.7 sec), LinkedList (6.6 sec), ArrayList (6.9 sec), Vector (7.5 sec). Adding the array 100 times: MyLinkedList (80.7 sec), ArrayList (82.5 sec), Vector (92.7 sec), LinkedList (176.3 sec). Adding the array 200 times: ArrayList (304.3 sec), Vector (332.7 sec), MyLinkedList (381.2 sec), LinkedList (610.4 sec). Conclusion: ArrayList is always faster than Vector. Since it's not synchronised, it's not very surprising. Though the difference is not too significant. If the list is not too large (up to 100,000 elements in my case), I got the best performance with an own implementation. Surprisingly LinkedList performs quite poor. As the size of the list grows, LinkedList is worse and worse. Final conclusion: if the list is not too big, you can have the best performance with an own implementation. If the size of the list is very big, use ArrayList. This result surprises me because ArrayList has to move lots of elements while a linked list only has to change some references. But as ArrayList is based upon an array, despite the high number of shifts it can outperform a linked list.

Extra info: In all four cases, when inserting a new element, I enumerate the list from the beginning until I find a larger element, then I insert the new node before it. I do this because the application needs to process the smaller elements. That's why I don't do binary search on Vector and ArrayList.

Wesley Murch
  • 101,186
  • 37
  • 194
  • 228
Jabba
  • 19,598
  • 6
  • 52
  • 45

6 Answers6

2

You can consider a TreeSet if your list does not have duplicate elements. The TreeSet keeps the elements in sorted order for you. It guarantees log(n) time for add, remove etc.

Vincent Ramdhanie
  • 102,349
  • 23
  • 137
  • 192
2

I looked at the API of LinkedList, but I do not find methods for inserting before/after a given node in the list.

It exists, but it is hidden in the ListIterator interface returned by the LinkedList.listIterator() method.

This is done to avoid exposing the list nodes themselves.

Michael Borgwardt
  • 342,105
  • 78
  • 482
  • 720
0

Well, first thought is you might use SortedList, which would solve the problem for you immediately.

(Except, durn, SortedList was in my imagination. Some other language.)

ArrayList#sort might help.

Failing that, you want a List implementation that implements the [two-parameter add method][1].

[1]: http://download.oracle.com/javase/1.4.2/docs/api/java/util/List.html#add(int, java.lang.Object)

Charlie Martin
  • 110,348
  • 25
  • 193
  • 263
0

I'm looking at Java API and there isn't a SortedList class in Java. You can use Collections utils from java.util such as Collections.sort(listToSort, comparator)[1] to get the ordering you want.

You'll either have to use TreeSet or make your own SortedList class that wraps around an existing List interface and sorts on add.

Daniel Fath
  • 16,453
  • 7
  • 47
  • 82
  • Yes, but I'd need a list that maintains the order, i.e. ordered at all times. Calling `sort()` after each insertion is too expensive. – Jabba Nov 01 '10 at 19:49
  • Ok, in that case try using `Collection.binarySearch(list)` to find the right place to insert. See discussion [here](http://stackoverflow.com/questions/416266/sorted-collection-in-java). Unless you make your own wrapper class with your own insert method you can't do it any other way using Java API. – Daniel Fath Nov 01 '10 at 20:07
  • @Jabba - why do you need the list in sorted order at all times? Do you have consumers that read the list between updates? And have you actually tried sorting the list after each insertion to see what the time difference is? I'm willing to bet that using an `ArrayList` and calling `Collections.sort()`, which uses an optimized mergesort, is going to be far faster than the insertion sort that you've implemented. – Anon Nov 03 '10 at 15:54
  • Several people asked why I need to process the smaller elements. This is specific to my problem. Actually I store sets in the list, and these sets are represented by the class BitSet. When I insert a new set, I need to verify if it has a proper subset in the list. That's why I enumerate the smaller elements. If the list is not sorted, I should enumerate all elements; if sorted I can stop when I meet a larger element. Later on I need to process them in ascending order by size. – Jabba Nov 03 '10 at 18:03
0

What type of processing do you need to do on the smaller elements before insertion of a new element?

In Java I want to store elements in ascending order by size. Before insertion I need to treat all the smaller elements. So I start enumerating the list treating smaller elements, and when I meet a larger element, I want to insert the new node before this larger element. What data structure would be the good choice?

I don't have a good grasp of what you need to do but you may want to take a look at the heap data structure that is implemented as java.util.PriorityQueue in Java. Nevertheless, take into account that java.util.PriorityQueue provides sorted removal of elements but no sorted iteration of elements. See the Java: How do I use a PriorityQueue? post for an example.

Community
  • 1
  • 1
Jaime Soto
  • 3,168
  • 1
  • 21
  • 19
0

Have you looked at TreeMap? It will auto sort as soon as you put a new value in.

I also looked at Trees (as in DefaultMutableTreeNode) and Documents (as in XML and DOM) the problems I saw there where they both allow a node to have multiple children while my understanding of a pure LinkedList is that each node has only one parent and one child.

Hope this is more helpful than my last post...

BigMac66
  • 1,528
  • 5
  • 19
  • 35