8

配列を使用して連結リストを実装する方法を知っています。たとえば、構造体を次のように定義します。

struct Node{
    int data;
    int link;
}

「data」は情報を格納し、「link」は次のノードの配列にインデックスを格納します。

「通常の」リンクリストと比較して、配列を使用してリンクリストを実装することの利点と欠点は何ですか? 任意の提案をいただければ幸いです。

4

4 に答える 4

10

リンクリストを配列でバックアップすると、両方の欠点が発生します。したがって、これはおそらくそれを実装するためのあまり良い方法ではありません。

いくつかの直接的な欠点：

  1. 配列（現在アイテムに使用されていないエントリ）にデッドスペースがあり、メモリを消費します
  2. 無料のエントリを追跡する必要があります-いくつかの挿入と削除の後、これらの無料のエントリはどこにでもある可能性があります。
  3. 配列を使用すると、リンクリストのサイズに上限が課せられます。

私はいくつかの利点があると思います：

  1. 64ビットシステムを使用している場合、「ポインタ」が占めるスペースは少なくなります（ただし、空きエントリに必要な余分なスペースは、おそらくこの利点を上回ります）。
  2. mmap()アレイをディスクにシリアル化し、呼び出しで簡単に読み戻すことができます。ただし、移植性のために何らかのプロトコルバッファを使用する方がよいでしょう。
  3. 配列内の要素がメモリ内で互いに近接していることについて、いくつかの保証を行うことができます。
于 2012-05-07T07:14:23.820 に答える
2

「通常の」リンクリストと比較して、配列を使用したリンクリストの実装の利点と欠点は何ですか?

リンクされたリストには、次の複雑さがあります。

  • cons x xs : O(1)
  • 追加 nm : O(n)
  • インデックス i xs : O(n)

表現が厳密で連続した配列を使用している場合、複雑さが異なります。

  • cons は古い配列をコピーする必要があります: O(n)
  • append では、両方の配列を新しい連続したスペースにコピーする必要があります: O(n + m)
  • index は配列アクセスとして実装できます: O(1)

つまり、配列に関して実装されたリンク リスト API は、配列のように動作します。

リンクされたリストまたは厳密な配列のツリーを使用することで、これをいくらか軽減できます。これにより、ロープまたはフィンガー ツリーまたは遅延シーケンスが発生します。

于 2012-05-08T11:51:43.493 に答える
0

スタックインは2つの方法で実装します。最初は配列を使用し、2番目はリンクリストを使用します。

配列を使用する際のいくつかの欠点は、ほとんどのプログラマーがスタック実装でリンクリストを使用することです。

1つ目は、リンクリストを使用したスタックです。最初はスタックサイズを宣言せず、スタック内のデータストアを制限しません。2つ目は、それを宣言して使用するためのポインターエッセイのリンクリストです。

リンクリストで使用されるポインタは1つだけです。その呼ばれるトップポインタ。

スタックはlifoメソッドを使用します。しかし、リンクリストプログラムの実装にはいくつかの欠点があります。

ほとんどのプログラマーは、いいねリストを使用してスタック実装を使用します。

于 2012-06-21T08:13:03.310 に答える
0

Array 実装を使用すると、リストのノードにシーケンシャルかつ高速にアクセスできますが、ポインターを使用して Linked list を実装すると、ノードにランダム アクセスできます。配列の実装は、固定番号を扱う場合に役立ちます。リストの途中からノードを挿入/削除する必要がある場合は、後ですべてのノードをシフトする必要があるため、パフォーマンスに関する限り、配列のサイズ変更はコストがかかるためです。これとは逆に、わからない場合はポインター実装を使用する必要があります。このようなリストは効率的に拡大/縮小でき、ノードをシフトする必要がないため、必要なノードの数を減らすことができます。ポインターを逆参照して参照するだけで実行できます。

于 2013-10-19T23:01:58.840 に答える