SortedSetならぬSortedListの良い実装はありませんか

質問

「SortedSet」の重複を許さない制限を取り払ったクラス、（あえていうならば）「SortedList」なる高速な実装はないでしょうか。
頻繁に挿入と削除を繰り返すので、TreeSetのように木構造が望ましいのですが、自分でＢ木とか何とか木を実装するのも骨が折れるので、そのようなライブラリや、こうすれば簡単にできるよ！的なテクニックがあれば教えていただければと思います。

今はArrayListよりはLinkedListの方がましかなという理由でこんな感じで実装しています。

interface SortedList <E extends Comparable<E>>
{
　public void add(E v);
　public boolean remove(E v);
　public E get(int i);
}

class SortedLinkedList <E extends Comparable<E>>
　extends LinkedList<E>
　implements SortedList<E>
{
　public void add(E v) {
　　int i=0, size=size();
　　for(i=0; i<size; i++)
　　　if(v.compareTo( get(i) )<0)
　　　　break;
　　add(i, v);
　}
　public boolean remove(E v) {
　　return super.remove(v);
　}

　public E get(int i) {
　　return get(i);
　}
}

回答No.1

noname#49428 · ベストアンサー

これでは、要素の追加（挿入）でしかソートされないので、SortedSetの代替にはなりませんね？
LinkedListのget実行速度は、めちゃめちゃ遅いので返ってパフォーマンス低下してるんじゃないでしょうか。

実装を簡単にするなら、追加または削除のたびにCollection#sortをすればいいんじゃないでしょうか。

お礼

ご回答ありがとうございます。
最初はsort()を使っていたのですが、私が利用しているプログラムからアクセスする分には
　Collection#sort<ArrayList<LinkedList
の順番でした。
（というのもおそらくgetで先頭の方しかみていないためです）

>これでは、要素の追加（挿入）でしかソートされないので、SortedSetの代替にはなりませんね？

一応削除でもソートされます。
ソート済みの列から１つ抜いてもソート済みの列になるはずなので・・・
違う意味でしたらごめんなさい。

プログラムの特性によって使い分けるのがよさそうですね。

回答No.2

choconamacream

値の重複を許して、反復処理に向いているコレクションに、LinkedHashMap<K,V>っていうのがありますが。

参考URL：

http://java.sun.com/j2se/1.5.0/ja/docs/ja/api/java/util/LinkedHashMap.html

お礼

ご回答ありがとうございます。
ただ、Mapである点と挿入順でソートされる点で私が望むクラスではないようです。