LinkedList, inserting elements in ascending order by size

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 pos开发者_运维问答ition 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.

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.

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.

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)

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.

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.

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...