任意の場所に要素を追加、追加、検索するためにO（1）を持つデータ構造体とは何ですか？

Question

私はJavaのソリューションを探していますが、一般的な答えもOKです。

Vector/ArrayListは、追加と取り込みではO（1）ですが、前置きではO（n）です。

LinkedListのは、検索のために（Javaでのような二重リンクリストを実装）（1）追記及びプリペンドためのOであるが、O（N）。

のDeque（ArrayDeque）は、上記のすべてのためにO（1）であるが、任意のインデックスにある要素を取得することはできません。私の心の中で

要件が上記内側2可変長リスト（プリペンドとアペンドするための1つに対して1つ）を有し、また、ここで検索中に要素を取得するかを決定するために、オフセット記憶満たすデータ構造。

Answer 1

ダブルエンドキューを探しています。これはあなたがC++ STLで望むやり方で実装されています。これはあなたが指摘することができますが、Javaでは指摘できません。あなたは、2つの配列を使用し、 "ゼロ"がどこにあるかを格納することによって、標準的なコンポーネントから自分自身をロールバックすることができます。これは、ゼロから遠くに移動するとメモリが無駄になる可能性がありますが、あまりにも大きくなると、デイスクを新しい配列にクロールすることができます。実際には2つのアレイを管理する際にあまり装飾性を必要としない

よりエレガントな解決策は、事前に割り当てられたアレイ上の円形アレイを課すことです。これには、push_front、push_back、およびその背後にある配列のサイズ変更を実装する必要がありますが、サイズ変更などの条件ははるかにクリーンになります。

Answer 2

あなたの考えが働く可能性があります。これらの操作だけがサポートする必要がある場合は、2つのベクターが必要です（HeadとTailと呼んでください）。前に追加するには、頭に追加し、追加するには、末尾に追加します。要素にアクセスするには、インデックスがhead.Lengthより小さい場合はhead [head.Length-1-index]を返し、そうでない場合はtail [index-head.Length]を返します。これらの操作はすべて明らかにO（1）です。

Answer 3

あなたはOとしてベクトル/ ArrayListに追加扱う場合には（1） - それは本当にありませんが、実際には十分に近いかもしれない -
（EDIT - 明確にする - 追加はが一定時間を償却することができますつまり、平均では加算はO（1）になりますが、スパイクではかなり悪くなる可能性があります。コンテキストや正確な定数によっては、この動作が致命的になる可能性があります）。

（これはJavaではなく、いくつかの組み立てられた言語です...）。

「転送」と呼ばれる1つのベクター。 「後方」と呼ばれる第2のベクトル。 Forward.Append()を - 追加するように求め

。 Backwards.Append()を - 前に付加するように求め

。照会するよう求め

-

if (Index < Backwards.Size()) 
{ 
    return Backwards[ Backwards.Size() - Index - 1 ] 
} 
else 
{ 
    return Forward[ Index - Backwards.Size() ] 
} 

（とも範囲外であること、インデックスのために確認してください）。

Answer 4

JavaのArrayDequeには何らかの理由でが足りないため、必要なのはSTLのような両端キューです（deque）。

• Java equivalent of std::deque?

Answer 5

両端キュー（両端キューが）が、O（1）時間内にすべてのこれらの操作を提供するために実装することができる。いくつかの良い提案をして、ここでの実装へのリンクがありましたすべての実装ではありません。私はJavaのArrayDequeを使用したことがないので、あなたはランダムアクセスをサポートしていないと冗談を言っていると思っていましたが、あなたは本当に正しいです - "純粋な"両端キューとして、理由は分かりますが、確かに迷惑です...

非常に高速な両端キューを実装する理想的な方法は、特に前面と背面での取り外しの追加にのみ関心があるため、circular bufferを使用することです。私はJavaですぐに認識していませんが、私はObjective-Cでオープンソースフレームワークの一部として書いています。コードをそのまま、または独自のコードを実装するためのパターンとして使用できます。

ここには、WebSVN portal to the codeとrelated documentationがあります。実際の肉はCHAbstractCircularBufferCollection.mファイルにあります - appendObject:とprependObject:メソッドを探します。カスタム列挙子（Javaの "iterator"）も定義されています。基本的な循環バッファ・ロジックはかなり簡単です、そしてこれらの3つの集中#defineマクロで捕獲された：あなたはobjectAtIndex:方法で見ることができるように

#define transformIndex(index) ((headIndex + index) % arrayCapacity) 
#define incrementIndex(index) (index = (index + 1) % arrayCapacity) 
#define decrementIndex(index) (index = ((index) ? index : arrayCapacity) - 1) 

は、あなたが両端キュー内のN番目の要素にアクセスするために行うすべてがarray[transformIndex(N)]です。私はサイズが役立ちます0

希望の場合は、配列がいっぱい、または空であるheadIndex == tailIndexので、もしtailIndexは常に、最後に保存された要素を超えて一つのスロットを指して作ることに注意してください。 Java以外のコードを投稿することについて申し訳ありませんが、質問者はと答えました。

Answer 6

O（1）append、prepend、first、last、およびsizeをサポートするデータ構造体です。我々は簡単にこのようなベクターは、追記用O（1）でdeleteとupdate

import java.util.ArrayList; 

public class FastAppendArrayList<A> { 
    private ArrayList<A> appends = new ArrayList<A>(); 
    private ArrayList<A> prepends = new ArrayList<A>(); 

    public void append(A element) { 
     appends.add(element); 
    } 

    public void prepend(A element) { 
     prepends.add(element); 
    } 

    public A get(int index) { 
     int i = prepends.size() - index; 
     return i >= 0 ? prepends.get(i) : appends.get(index + prepends.size()); 
    } 

    public int size() { 
     return prepends.size() + appends.size(); 
    } 

    public A first() { 
     return prepends.isEmpty() ? appends.get(0) : prepends.get(prepends.size()); 
    } 

    public A last() { 
     return appends.isEmpty() ? prepends.get(0) : appends.get(prepends.size()); 
    }