理論的な観点から、順序付きリストと配列の違いは何ですか？

Question

違いはありますか、同じものに対して2つの用語がありますか？

Answer 1

アレイとリストの間にはいくつかの類似点がありますが、それらはさまざまな目的で使用されています。

アレイはメモリの連続したセグメントであり、リストは単なる束のノードであり、それぞれには「次の」ノードへのポインタ（および双方向リストの場合は「前の」ノード）。

O（1）でランダムアクセスをサポートしていますが、要素を配列に削除/挿入するのが遅いのはO（n）です。削除/挿入要素。 一方、効率的なランダムアクセス（効率的な連続的なトラバーサルをサポートする）をサポートしていませんが、挿入と削除は高速です - O（1）。

詳細画像は： およびthis linkです。

Answer 2

配列内の項目は必ずしも特定の順序である必要はありません。

一般的に、リスト内の特定のポイントにアイテムを追加することは、新しいアイテムを同等のポイントのアレイに追加するよりも迅速に行うことができます。 （配列内では、他のエントリをシャッフルする必要がありますが、リスト内では、最大3つの要素で適切なポインタを調整するだけです）。リストや配列から要素を削除する場合も同様です。

リストにN ^thアイテムへのアクセスにはO（N）時間がかかりますが、アレイのO（1）時間です。

Answer 3

配列とリストは異なるデータ構造です。配列は必ずしも順序付けられていません。

O（N）の挿入、削除は、O（N）よりも高速に実行できます（バイナリ検索など）。通常の配列では、検索はO（N）です。配列では、O（1）のメンバーにランダムアクセスできますが、これはリスト内でO（N）が必要です。