1

展開された連結リストについて読んでいて、1 つを作成する 2 つの異なる方法を見つけました。私が持っている本は次のようなものを実装しています：

// Node
typedef struct node {
    int data;
    struct node *next;
} Node;

// Block of nodes
typedef struct linkedblock {
    struct linkedblock *next;
    Node *head;
    int nodeCount;
} LinkedBlock;

ただし、ウィキペディアは、LinkedBlockへのポインターではなくNode、配列を持っていることを示しています。これは、メモリが連続し、キャッシュの効率が向上するためではないでしょうか? このようにすることの他の利点はありますか？私の本がそれを実装する方法は、最適化されていない/悪いですか? 一般的な方法や優先される方法はありますか？

展開されたリンクリストを実装して、それらがどのように機能するかを学習できるようにしようとしていますが、将来使用する必要がある場合にも備えています (奇妙なことに、GitHub または他の場所で C 実装が見つかりません)。基本的に、2 つの方法のうち、実際のアプリケーションで使用される可能性が高い方法を知りたいと思います。また、これは学習に多くの時間を無駄にすべきではないデータ構造ですか? 私の他のアルゴリズムの本（CLRS）では、それについて言及されていないからです。

4

1 に答える 1

3

この本の実装はあまり役に立たないように見えます。実際には、標準のリンク リストよりも多くのメモリを (これらのLinkedBlock構造を格納するために) 使用するからです。展開されたリンク リストの主な利点の 1 つは、ノードごとに通常のリンク リストよりも多くのデータを格納できることです。これは、サイズを格納するために余分なスペースの単一の整数のみを使用する (スペース効率の良い) 配列と、いくつかのデータへのポインターを指定して効率的な挿入と削除を行う (時間効率の良い) リンク リストとの間のバランスです。

それらについて学ぶことの価値については、通常のリンクされたリストと同様のアルゴリズム特性を持っています。展開された連結リストを作成する利点のほとんどは、通常の連結リストと同じインターフェイスを使用するため、高速化が必要な、またはメモリを大量に使用する既存のアプリケーションがある場合です。漸近分析 (CLRS でも説明されています) について学んだことがあれば、展開された連結リストのメモリ使用量と時間効率が一定の係数だけ異なるため、漸近的には同じであることを認識できるかもしれません。

私の推奨事項は次のとおりです。それらが存在し、実際のアプリケーションでパフォーマンスを向上させることができることに注意してください。ただし、高速化しようとしている特定のアプリケーションがない限り、それらについてあまり心配する必要はありません。

于 2016-07-16T20:46:09.357 に答える