4

リンクされたリストのアプリケーションの良い例は何ですか? キューとスタックを連結リストとして実装するのが良い考えであることは知っていますが、具体的に高速な挿入時間を利用して問題を解決する連結リストの実用的で直接的な例はありますか? リンクされたリストに基づく他のデータ構造だけではありません。

プライオリティ キューに関するこの質問と同様の回答を期待しています:プライオリティ キュー アプリケーション

私は自分自身で 1 つ見つけました: ハッシュ テーブルとリンクされたリストで実装された LRU (最近使用されていない) キャッシュです。

Exceptionを持つクラスの例もありますInnerExeption

他には何があるの？

4

3 に答える 3

4

私は、米国の「大きな株式市場」で開発者として働いています。私たちが非常に高速に動作する理由の 1 つは、初期化後 (市場での 1 日が始まる前) にヒープの割り当て/割り当て解除を行わないことです。この手法は取引所に固有のものではなく、ほとんどのリアルタイム システムでも一般的です。

まず第一に、リストが拡大または縮小するときにヒープ割り当てを必要としないため、リンクされたリストは配列ベースのリストよりも優先されます。取引所の複数のアプリケーションで連結リストを使用しています。

  • 1 つのアプリケーションは、初期化中にすべてのオブジェクトをプール (リンクされたリスト) に事前に割り当てることです。したがって、新しいオブジェクトが必要なときはいつでも、リストの先頭を削除できます。
  • 別のアプリケーションが注文処理中です。すべての Order オブジェクトは、リンクされたリスト エントリ インターフェイスを実装します (前と次の参照があります)。そのため、顧客から注文を受け取ると、プールから Order オブジェクトを削除し、「処理する」リストに入れることができます。すべての Order オブジェクトは Linked List エントリを実装しているため、リスト内の任意のポイントに追加することは、前および次の参照を設定するのと同じくらい簡単です。

私の頭の上の例：

Interface IMultiListEntry {

    public IMultiListEntry getPrev(MultiList list);
    public void setPrev(MultiList list, IMultiListEntry entry);

    public IMultiListEntry getNext(MultiList list);
    public void setNext(MultiList list, IMultiListEntry entry);

}

Class MultiListEntry implements IMultiListEntry {

    private MultiListEntry[] prev = new MultiListEntry[MultiList.MAX_LISTS];
    private MultiListEntry[] next = new MultiListEntry[MultiList.MAX_LISTS];

    public MultiListEntry getPrev(MultiList list) {
        return prev[list.number];
    }
    public void setPrev(MultiList list, IMultiListEntry entry) {
        prev[list.number] = entry;
    }

    public IMultiListEntry getNext(MultiList list) {
        return next[list.number];
    }
    public void setNext(MultiList list, IMultiListEntry entry) {
        next[list.number] = entry;
    }

}

Class MultiList {

    private static int MAX_LISTS = 3;
    private static int LISTS = 0;

    public final int number = LISTS++;

    private IMultiListEntry head = null;
    private IMultiListEntry tail = null;

    public IMultiListEntry getHead() {
        return head;
    }

    public void add(IMultiListEntry entry) {
        if (head==null) {
            head = entry;
        } else {
            entry.setPrevious(this, tail);
            tail.setNext(this, entry);
        }
        tail = entry;
    }

    public IMultiListEntry getPrev(IMultiListEntry entry) {
        return entry.getPrev(this);
    }
    public IMultiListEntry getNext(IMultiListEntry entry) {
        return entry.getNext(this);
    }
}

あとは、MultiListEntry を拡張するか、IMultiListEntry を実装して、インターフェイス メソッドを MultiListEntry オブジェクトへの内部参照に委譲するだけです。

于 2013-09-14T14:08:48.173 に答える
0

答えは無限にある可能性があり、「良い例」は主観的な用語であるため、質問に対する答えは非常に議論の余地があります. もちろん例はあります。高速挿入の潜在的なニーズについて考える必要があります。

たとえば、タスク リストがあり、すべてのタスクを解決する必要があるとします。リストを見て、タスクが解決されたときに、新しいタスクを緊急に解決する必要があることに気付き、解決したばかりのタスクの後にタスクを挿入します。これはキューではありません。リストは将来レビューのために必要になる可能性があるため、リストをそのままにしておく必要があります。この場合、pop メソッドは許可されません。

別の例を挙げると、アルファベット順に並べられた一連の名前があります。特定の名前が格納されているオブジェクトを次に指しているオブジェクトを、どうにかして素早く判断できると仮定しましょう。名前をすばやく削除したい場合は、削除するオブジェクトの前の項目に移動するだけです。削除も、スタックやキューの場合よりも高速です。

最後に、挿入または削除後も保存する必要がある非常に大きなアイテムのセットを想像してください。この場合、大きなセット全体をコピーするよりも、削除するアイテムまたはアイテムを挿入する位置の前のアイテムを検索してから操作を行う方がはるかに高速です。

于 2013-09-14T13:30:40.943 に答える