java - ArrayDeque の O(1) 時間の複雑さで取得 (get()) を実現する方法はありますか?

Question

addfront、addback、および検索の時間の複雑さが O(1) であると想定されるクラスに ArrayDeque を使用しようとしています。検索に toArray() を使用することしか考えられませんでしたが、残念ながら O(n) です。O(1) である ArrayDeque の検索メソッドを実装する方法はありますか?

Answer 1

API には、ArrayDequeこれを行う方法はありません。

ArrayDequeただし、その implementsのカスタム サブクラスを作成することはできますget。このようなもの：

public E get(int i) {
    if (i < 0 || i > size()) {
        throw new ....("out of bounds");
    }
    long pos = this.head + i; 
    if (pos >= this.elements.length) {
        pos -= this.elements.length;
    }
    return this.elements[(int) pos];
}

注: このコードはコンパイル/デバッグされていません。自己責任！

これは、 APIO(1)の既存の操作のパフォーマンスには影響しません。ArrayDeque

---

アップデート

上記は、ArrayDequeアクセスしているフィールドがパッケージ プライベートであるため、標準クラスのサブクラスとしては機能しません。ただし、元のクラスをコピーして、上記のメソッドをコピーに追加することはできます。

(OpenJDK コードベースからコードをコピーし、GPLv2 要件を満たしていることを確認してください。)