An Efficient data structure for Sorted List

I want to save my objects according to a key in the attributes of m开发者_运维知识库y object in a sorted fashion. Later on I'll access these objects sequentially from max key to min key. I'll do some search tasks as well.

I consider to use either AVL tree or RB Tree. As far as i know they are nearly equivalent in theory(Both have O(logn)). But in practice which one might be better in performance in my situation. And is there a better alternative than those, considering that I'll mostly do insert and sequentially access to the ds.

Edit: I'm going to use java

For what it's worth, in C#, SortedDictionary<K, V> is implemented as a red-black tree, and in many implementations of the STL in C++, std::map<K, T> is implemented as a red-black tree.

Also, from Wikipedia on AVL vs. red-black trees:

The AVL tree is another structure supporting O(log n) search, insertion, and removal. It is more rigidly balanced than red-black trees, leading to slower insertion and removal but faster retrieval. This makes it attractive for data structures that may be built once and loaded without reconstruction, such as language dictionaries (or program dictionaries, such as the order codes of an assembler or interpreter).

Which ever is easiest for you to implement, you won't get better insertion than log(n) with a sorted list and we'd probably need a lot more detail than what you've provided to decide if there are other factors that make another structure more appropriate.

As you're doing it in Java, consider using a TreeSet (although it's a Set, so you can't have duplicate entries)...