c - ベクターとリンクリストADTの違い

Question

ACプログラミング言語のコンテキストでのVectorとLinkedListADTの違いを誰かに説明してもらえますか。

ありがとう。

Answer 1

Cでは、C++stdライブラリのように直接利用できる「ベクトル」および「リスト」データ型はありません。しかし、「抽象データ型」の観点から、ベクトルは通常、連続したストレージを表すと見なされ、リンクリストは互いにリンクされた個々のセルによって表されると見なされます。ベクトルは高速の一定時間のランダムアクセス読み取りおよび書き込み操作を提供しますが、ベクトル要素の挿入と削除には線形時間がかかります。リストには、読み取りと書き込みを行う要素を見つけるための線形ルックアップパフォーマンスがありますが、要素の場所が指定されている場合、挿入と削除は一定時間になります。リストの最初と最後に一定時間で項目を追加することもできます（ADT実装がリストの最後の要素の場所をキャッシュする場合）。

Answer 2

ベクトルは、多くの場合、配列としてのメモリの連続ブロックとして実装されます。一方、各要素は1つ以上の他の要素へのポインタを保持しているため、リストはメモリ全体に分散できます（二重にリンクできます）。これにより、ベクターにアクセス速度の利点がもたらされますが、挿入/削除の利点がリストされます。

Answer 3

基本的に、ベクトルは連続したメモリに存在します。リンクリストには、前の構造と次の構造へのポインタが含まれています。ベクトルはランダムアクセスの方が速く、リンクリストは成長に適しています。

http://www.codeguru.com/forum/archive/index.php/t-309352.html

Answer 4

ベクトルは動的配列です。内部の要素はメモリ内で隣接しています。リンクリスト内の要素は隣接していません。