要素の順序を保持するデータ構造を探しています (クライアントが要素を移動する可能性があるため、データ構造の存続期間中に変化する可能性があります)。
高速検索、特定の要素の前後への挿入、特定の要素の削除、最初と最後の要素のルックアップ、および特定の要素から開始する双方向の反復を可能にする必要があります。
良い実装は何でしょうか?
これが私の最初の試みです：
リンク リストとディクショナリを含むcollections.abc.Iterableとの両方から派生したクラス。collections.abc.MutableSetディクショナリのキーは要素であり、値はリンク リスト内のノードです。ディクショナリは、指定された要素のノードの検索を処理します。要素が見つかると、リンクされたリストは前後の挿入、削除、および反復を処理します。ディクショナリは、関連するキーと値のペアを追加または削除することで更新されます。明らかに、このアプローチでは、要素はハッシュ可能で一意である必要があります (そうでなければ、各要素が自動割り当ての数値識別子で表され、それらの識別子のみがキーとして格納される別の間接レイヤーが必要になります)。
これは、またはよりも漸近的な複雑さにおいて厳密に優れているように思えますが、間違っている可能性があります。[編集: @roliu が指摘したように間違っています。orとは異なり、 の数値インデックスで要素を見つけることはできません。今のところはありますが、必要に応じて何らかの方法で作成できると確信しています。]listcollections.dequelistdequeO(1)O(N)O(log N)