配列といえば、誰もがよく知っているものです。開発プロセスでは、どんな言語を使っていても、必ず配列を使っています。通常、配列はデータ型であることを知って、実際には、配列も基本的なデータ構造です。データ構造としての配列は、時間を理解するとき、なじみがないかもしれません。ここでは、独自の学習ノートとして配列のデータ構造の基本的な概念とアプリケーションを記録します。
配列とは
配列は、[1,2,3]のjsのような配列ですが、これはデータ型であることを知っているかもしれませんが、ここで配列のデータ構造の定義は次のとおりです。
リニアテーブルとは
線形表とは、データが一列に並んだ構造のことで、各線形表は最大で前後2方向のデータを持ちます。もちろん、線形表構造である配列以外にも、スタックやキュー、連鎖リストなど、配列を持つ線形表と同じ構造を持つものもあります。線形表構造に加えて、非線形表構造もあります。例えば、ツリー、ヒープ、グラフは、データが前後に線形に接続されていないため、非線形です。
配列の特徴
- まず、すべての配列は、連続したメモリ空間とデータの同じ種類のため、これらの2つの特性のため、配列は、非常に効率的なランダムアクセスをサポートしています。しかし、これらの2つの機能のため、それはまた、配列のデータ構造データの挿入につながる、削除は非常に非効率的になります。継続性の要件があるため、多くのデータ移動操作は、パフォーマンスに影響を与えます。
- 配列が添え字に基づいてランダムにデータにアクセスできる原理は何ですか？そのおおよその理由は、配列が定義されるとき、コンピュータはデータを格納するためのスペースをメモリに割り当てます。この割り当てられたスペースは、配列の各データを格納するためにより小さなメモリセルに分割されます。各メモリ・セルはメモリ・アドレスに対応しており、ランダムな要素にアクセスする必要があるときに、メモリ・アドレスが照会されます。
- 配列と連鎖リストの違い：
- 配列はランダムアクセスをサポートし、添え字に基づくアクセスの時間的複雑さは、挿入や削除に適していないことです。
- 連鎖リストは挿入や削除に適していますが、ルックアップには適していません。
アレイの挿入と削除が非効率的なのはなぜですか？
前述したように、配列はメモリ上のデータの連続性を維持するために、挿入や削除操作の非効率化につながります。では、具体的になぜ非効率になるのか、詳しく説明しましょう。
スティービー
ここで、配列のi番目の位置にデータを挿入する必要があるとします。新しいデータのためにi番目の位置を解放するために、iからnの部分の要素を順次1つ後ろに移動する必要があります。挿入操作の時間的複雑度は？ 要素を配列の末尾に挿入する場合、データを移動する必要はなく、時間複雑度は.しかし、要素を配列の先頭に挿入した場合、すべてのデータを順番に1つ戻す必要があるので、最悪の時間複雑度は.各位置に要素が挿入される確率は同じなので、平均的な場合の所要時間は . 配列のデータが順番に並んでいる場合、ある位置に新しい要素が挿入されると、先ほど説明したようにi番目以降のデータを移動しなければなりません。しかし、配列に格納されたデータに規則性がない場合、配列は単に格納されたデータの集まりとして扱われます。この場合、大規模なデータシフトを避けるために、配列をi番目の位置に挿入したいのであれば、i番目の位置にあるデータを配列要素の末尾に直接移動させ、新しい要素を直接i番目の位置に入れるという簡単な方法があります。この処理テクニックを使用すると、与えられたシナリオでi番目の位置に要素を挿入する時間の複雑さは、次のように削減されます。
挿入と同様に、i番目の位置のデータを削除する場合、メモリの連続性のためにデータを移動する必要があります。挿入と同様に、配列の末尾のデータを削除する場合、最良の場合の時間複雑度は次のようになり、先頭のデータを削除する場合、最悪の場合の時間複雑度は次のようになります。実際には、いくつかの特殊なシナリオでは、配列内のデータの連続性を追求する必要はありません。 複数の削除操作が一緒に実行される場合、削除の効率ははるかに高くなります。
