TechCodeview

配列 そして リンクされたリスト メモリ内のデータを整理するには 2 つの方法があります。の違いを理解する前に、 配列 そしてその リンクされたリスト 、まず見てみましょう 配列で そして リンクされたリスト 。

文字列をJavaに変換する

配列とは何ですか?

同じ型の要素を含むデータ構造。データ構造はデータを編成する方法です。配列はデータを順番に編成するため、データ構造です。配列はメモリの大きな塊であり、メモリが小さなブロックに分割されており、各ブロックは何らかの値を格納できます。

10 個の値で構成される配列を作成したと仮定すると、各ブロックには整数型の値が格納されます。異なる型の配列に値を格納しようとすると、それは正しい配列ではなくなり、コンパイル時エラーがスローされます。

配列の宣言

配列は次のように宣言できます。

 data_type name of the array[no of elements] 

配列を宣言するには、まず配列の型を指定し、次に配列の名前を指定する必要があります。角括弧内で、配列に含める要素の数を指定する必要があります。

例を通して理解しましょう。

 int a[5]; 

上の例では、 ' を使用して 5 つの要素の配列を宣言しました。 ある ' の名前 整数 データ・タイプ。

リンクリストとは何ですか?

リンク リストは、ランダムに保存されたノードのコレクションです。各ノードは 2 つのフィールドで構成されます。 データ そして リンク 。ここで、データはその特定のノードに格納されている値であり、リンクは次のノードのアドレスを保持するポインタです。

配列とリンクリストの違い

データ構造のどちらが優れているかは言えません。つまり、配列と リンクされたリスト 。あるデータ構造はある種類の要件には適しており、別のデータ構造は別の種類の要件には適しているという可能性があります。データ構造に対して頻繁に実行される操作は何か、データのサイズなど、さまざまな要素がデータ構造の選択に基づいて選択されます。次に、いくつかのパラメータに基づいて、配列とリンク リストの違いを確認します。

1. 要素へのアクセスのコスト

配列の場合、配列のサイズに関わらず、要素へのアクセスには一定の時間がかかります。配列では要素が連続して格納されるため、要素のベース アドレスがわかっていれば、配列内の任意の要素のアドレスを簡単に取得できます。配列内の任意の要素のアドレスを取得するには、単純な計算を実行する必要があります。したがって、配列内の要素にアクセスするには、 ○(1) 時間の複雑さの観点から。

リンクされたリストでは、要素は連続して格納されません。複数のブロックで構成されており、各ブロックはノードとして表されます。各ノードには 2 つのフィールドがあります。つまり、1 つはデータ フィールド用で、もう 1 つは次のノードのアドレスを格納します。リンク リスト内のノードを見つけるには、まずヘッド ノードと呼ばれる最初のノードを決定する必要があります。リスト内の 2 番目のノードを見つける必要がある場合は、最初のノードからたどる必要があり、最悪の場合、最後のノードを見つけるためにすべてのノードをたどることになります。要素にアクセスする平均的なケースは O(n) です。

配列内の要素にアクセスするコストはリンク リストよりも低いと結論付けられます。したがって、要素にアクセスするための要件が​​ある場合は、配列を選択することをお勧めします。

2. 要素の挿入にかかるコスト

挿入には 3 つのシナリオが考えられます。

ジャワの睡眠

要素を先頭に挿入します。新しい要素を先頭に挿入するには、まず要素を右にシフトして最初の位置にスペースを作成する必要があります。したがって、時間の計算量はリストのサイズに比例します。 n が配列のサイズの場合、時間計算量は O(n) になります。

リンク リストの場合、リンク リストの先頭に要素を挿入するには、新しいノードを作成し、最初のノードのアドレスが新しいノードに追加されます。このようにして、新しいノードが最初のノードになります。したがって、時間の計算量はリストのサイズに比例しません。時間計算量は一定、つまり O(1) になります。

最後に要素を挿入する

配列がいっぱいでない場合は、インデックスを介して新しい要素を直接追加できます。この場合、時間計算量は一定、つまり O(1) になります。配列がいっぱいの場合は、まず配列を別の配列にコピーし、新しい要素を追加する必要があります。この場合、時間計算量は O(n) になります。

リンクされたリストの最後に要素を挿入するには、リスト全体を走査する必要があります。リンク リストが n 個の要素で構成されている場合、時間計算量は O(n) になります。

要素を中間に挿入する

i に要素を挿入するとします。^番目配列の位置。 n/2 個の要素を右にシフトする必要があります。したがって、時間計算量は要素の数に比例します。平均的な場合、時間計算量は O(n) になります。

文字列ビルダーJava

リンクされたリストの場合、新しい要素を挿入する必要がある位置まで移動する必要があります。ただし、いかなる種類のシフトも実行する必要はありませんが、n/2 位置までトラバースする必要があります。かかる時間は要素の数 n に比例し、平均的な場合の時間計算量は O(n) になります。

結果として得られるリンク リストは次のとおりです。

使いやすさ

配列の実装はリンク リストに比べて簡単です。リンク リストを使用してプログラムを作成する場合、プログラムではセグメンテーション違反やメモリ リークなどのエラーが発生しやすくなります。したがって、リンク リストでプログラムを作成するときは、十分な注意が必要です。

ダイナミックなサイズ

リンクされたリストのサイズは動的ですが、配列は静的です。ここで、静的とは、実行時にサイズを決定できないという意味ではありませんが、一度サイズが決定すると変更することはできません。

3. メモリ要件

配列内の要素はメモリの 1 つの連続したブロックに格納されるため、配列のサイズは固定されます。サイズ 7 の配列があり、その配列が 4 つの要素で構成されている場合、残りのスペースは未使用であるとします。 7 つの要素が占めるメモリ:

メモリ空間 = 7*4 = 28 バイト

ここで、7 は配列内の要素の数、4 は整数型のバイト数です。

リンク リストの場合、未使用のメモリはありませんが、余分なメモリはポインタ変数によって占有されます。データが整数型の場合、1 つのノードが占める合計メモリは 8 バイト、つまりデータ用に 4 バイト、ポインタ変数用に 4 バイトになります。リンク リストが 4 つの要素で構成されている場合、リンク リストが占有するメモリ空間は次のようになります。

ウェブドライバー

メモリ空間 = 8*4 = 32 バイト

データ部分のサイズが大きい場合は、リンク リストの方が適しています。データが 16 バイトであると仮定します。配列が占有するメモリ空間は 16*7=112 バイトですが、リンク リストは 20*4=80 バイトを占有します。ここでは、データのサイズに 16 バイトとポインタ変数の 4 バイトを加えた 20 バイトを指定しています。より大きなサイズのデータ​​を選択している場合、リンクされたリストの消費メモリは少なくなります。それ以外の場合は、サイズを決定するために採用している要因によって異なります。

配列とリンク リストの違いを表形式で見てみましょう。