2

リンクされたリストの実装ではなく、JavaのVectorベース実装を使用する動機は何ですか? Stackは同期化されており、利点 (およびオーバーヘッド) を継承していることに気付きましたVectorが、これらのデータ構造は通常、リンクされたリストベースの構造としてテキストで教えられているだけでなく、LL は基になる配列がいっぱいになるときにコストのかかるサイズ変更を回避しているように感じます。

Vectorsサイズ変更があっても、償却分析を使用して O(1) であることは理解しています。したがって、これを考慮しても大した違いはないかもしれませんが、それでもなおその理論的根拠を理解したいと思います。

4

2 に答える 2

6

連結リストには次の欠点があります。

  • 要素ごとのストレージ オーバーヘッド
  • 要素から要素へのポインタ/参照に従わなければならないことによる計算の複雑さ
  • キャッシュの局所性が悪い

もちろん、これらは連結リストの一般的な欠点にすぎません。それらが何に基づいて何を基準にするかの決定に影響を与えたかどうかはわかりませQueueんStack.

于 2012-07-06T19:14:18.490 に答える
4

ベクトルは、そのデータを連続したメモリに格納します。これはキャッシングに適しています。

リンクされたリストは、メモリ内で非常に断片化する可能性があります。

于 2012-07-06T19:13:44.287 に答える