一目でわかるアルゴリズム「配列と連結リスト」

データ構造はソフトウェア開発の最も基本的な部分であり、プログラミングの内部的な強さを反映しています。大学のコンピュータの授業でデータ構造を本格的に学んだ人も多いと思いますが、実際のプロジェクト開発ではあまり使われていないと感じています。

実際には、使用頻度が低いというわけではなく、使用する場合は多くの高級言語やフレームワークのコンポーネントによってカプセル化されており、実際に自分で実装する必要がある箇所は比較的少ないです。しかし、他の人がそれをカプセル化しているからといって、それを無視してよいというわけではありません。プログラマーの内なる力であるデータ構造は、時間をかけて学ぶ価値があります。私はその本を開いてレビューします。

[[273724]]

この記事では、最もよく使用される「配列」と「リンクリスト」から始めます。しかし、配列とリンクリストについて説明する前に、まずデータの論理構造の分類について見てみましょう。一般的に、データの論理構造は次の 2 つのタイプに分けられます。

線形: 直線的に接続された構造です。この記事で説明する配列やリンクリストはこのカテゴリに属します。キューやスタックなども存在します。

非線形: 名前が示すように、データ間の関係はヒープ、ツリー、グラフなど非線形です。

分類がわかったところで、「配列」と「リンクリスト」の原理を詳しく見ていきましょう。

1. 配列とは何ですか?

配列は、同じタイプのデータの有限の集合であり、メモリ内の連続したメモリ領域です。

以下のように表示されます。

配列の添え字は 0 から始まります。上図の配列には 6 つの要素があり、対応する添え字は 0、1、2、3、4、5 です。同時に、配列に格納されるデータの型は一貫している必要があります。たとえば、上図に格納されているデータはすべてデジタル型です。配列内のすべての要素は、上図の右側に示すように、メモリ空間の一部に「連続的に」格納されます。要素間には他のストレージ分離はありません。また、配列は連続したメモリ空間を必要とするため、配列を定義するときにその固定サイズを事前に指定する必要があり、変更することはできません。

配列アクセス:

配列はランダムアクセスをサポートしているため、アクセス操作において独自のパフォーマンス上の利点があります。つまり、添字を通じて配列内の任意の要素にランダムにアクセスできます。配列要素のストレージは連続的であるという原理により、次のように、要素のオフセットを配列メモリ空間の最初のアドレスに追加することで、特定の要素のメモリアドレスを計算できます。

配列[n]のアドレス = 配列メモリ空間の最初のアドレス + 各要素のサイズ * n

上記の式から、インデックスを介して配列内のデータにアクセスする場合、配列全体をトラバースする必要がないため、配列のアクセス時間の複雑さは O(1) であることがわかります。もちろん、ここで注意すべき点は、インデックスでアクセスせず、コンテンツを介して配列内の要素を検索する場合、時間の複雑さは O(1) ではないということです。極端な場合には、配列全体の要素をトラバースする必要があり、時間の複雑さは O(n) になることがあります。もちろん、異なる検索アルゴリズムに必要な時間の複雑さは異なります。

配列の挿入と削除:

また、配列要素の連続性が求められるため、要素の挿入や削除を行う際の配列の効率は低下します。

配列の途中に新しい要素を挿入する場合は、新しい要素のためのスペースを確保するために、隣接するすべての要素を 1 つ後ろの位置に移動する必要があります。上の図を例に挙げてみましょう。添字 2 の位置に新しい要素 11 を挿入する必要がある場合、添字 2、3、4、5 の元の要素を順番に 1 つ後ろの位置に移動してから、新しい要素を添字 2 の位置に挿入する必要があります。最終的に、新しい配列は次のようになります。

 23、4、11、6、15、5、7

新しい要素を配列の先頭に挿入する場合、元の配列全体を 1 つ後ろへ移動する必要があります。このとき、時間の計算量は最悪のケース、つまり O(n) になります。新しい要素を配列の最後に挿入する場合、他の要素を移動する必要はありません。このとき、時間の計算量は最良のケース、つまり O(1) になります。したがって、平均すると、配列挿入の時間計算量は O(n) になります。

配列の削除は配列の挿入と似ています。

したがって、全体的には配列のアクセス効率は高くなりますが、挿入と削除の効率は低くなります。ただし、配列の挿入と削除の効率を向上させる方法はあります。以下で「リンクリスト」について学んでみましょう。

2. 「リンクリスト」とは何ですか?

リンクリストは、物理ストレージユニット上の非連続かつ非シーケンシャルなストレージ構造です。データ要素の論理的な順序は、リンクリスト内のポインタリンクの順序によって実現されます。通常、挿入と削除が比較的頻繁に行われるシナリオで使用されます。

上の図は「単一のリンクリスト」の例です。リンクリストは配列のように連続したスペースを必要としません。散在したメモリスペースのみを必要とするため、メモリスペースの要件は配列よりも低くなります。

リンクリストの各ノードは、「ポインタ」によってリンクされています。各ノードは 2 つの部分で構成されます。1 つはデータ (上図の Data)、もう 1 つは後続ポインタ (次のノードのアドレスを格納するために使用) です。このチェーンでは、最初のノードは Head と呼ばれ、最後のノードのポインタは NULL を指します。

リンクリストにはいくつかの種類があります。上の図は最も単純なものです。各ノードには、次のノードを指すポインタ (後続ポインタ) が 1 つだけあります。このリンクリストは、一方向リンクリストと呼ばれます。さらに、双方向リンクリスト、循環リンクリストなども存在します。

二重リンクリスト:

二重リンクリストと単一リンクリストの違いは、前者は両方向にポインターを持ち、後者は一方向にのみポインターを持つ点です。二重リンクリストの各ノードには 2 つのポインタがあり、1 つは前のノードを指し、もう 1 つは次のノードを指します。双方向リンクリストは、操作上、単一リンクリストよりもはるかに効率的ですが、余分なポインタスペースがあるため、少し多くのメモリを占有します。

循環リンクリスト:

実際、循環リンクリストは、一方向リンクリストをベースとして、末尾ノードのポインタが先頭ノードを指し、先頭と末尾が接続される点を除いて、特殊な一方向リンクリストです。

リンクリストアクセス

リンクリストの利点はアクセスではありません。リンクリストでは、最初のアドレスと添え字からノードのアドレスを計算できないため、リンクリスト内のノードを検索するには、一度に1つのノードをトラバースする必要があり、リンクリストのアクセス時間の複雑さはO(n)です。

リンクリストの挿入と削除

リンクリストのメモリ空間は非連続であるため、要素を挿入および削除するときに、配列のように他の要素を移動する必要がなく、ポインタを変更するだけで済みます。

たとえば、要素Eを削除するには:

たとえば、要素を挿入するには次のようにします。

要素の挿入と削除にはポインタの変更のみが必要で、データの移動は必要ないため、リンクリストの挿入と削除の時間計算量は O(1) です。ただし、これはノードを見つけた後の純粋な挿入または削除に必要な時間計算量を指します。

指定されたノードがまだ見つかっておらず、リンクリストの先頭のみが取得されている場合、このリンクリスト内の固定コンテンツを持つノードを削除するには、まずそのノードを見つける必要があります。この検索アクションは、トラバーサルアクションでもあります。このトラバーサル検索の時間計算量は O(n) です。2 つの合計時間計算量は、実際には O(n) です。

実際、削除するノードが見つかったとしても、削除ロジックは単純ではありません。上図の「ノード E の削除」を例に挙げます。現在のリンクリストポインタがノード E に配置されている場合、削除時に、ノード E の前のノード H の後継ポインタをノード A を指すように変更する必要があります。そうすると、ノード E は自動的に削除されます。ただし、現在のリンクリストポインタはノード E に配置されています。ノード H の後継ポインタを変更するにはどうすればよいでしょうか。「一方向リンクリスト」の場合、ノード H を見つけてその後継ポインタの内容を変更するには、リンクリスト全体を最初からトラバースする必要があるため、時間の計算量は O(n) です。ただし、「双方向リンクリスト」の場合は、トラバースする必要がなく、先行ポインタを介して直接ノード H を見つけることができ、時間の計算量は O(1) です。これが、「双方向リンクリスト」が「一方向リンクリスト」よりも優れている点です。

3. 「配列とリンクリスト」のアルゴリズムの実際の応用?

上記の紹介から、「配列」と「リンクリスト」にはそれぞれ独自の利点があり、時間の計算量も操作状況によって異なり、単純に O(1) または O(n) と述べることはできないことがわかります。そこで、以下に練習用によく使われるアルゴリズムの問題を挙げました。

アルゴリズムの問題: 単方向リンクリストを逆順にする
入力: 1->2->3->4->5-> NULL  
出力: 5->4->3->2->1-> NULL   
 
 /**
 *単リンクリストの定義。
 *パブリッククラスListNode{
 *整数値;
 * リストノード次へ;
 * リストノード( int x) { val = x; }
 * }
 */
クラスソリューション{
パブリックListNodeリバースリスト(ListNodeヘッド) {
        //最初のノードにはプレノードがないので、プレノード変数を定義します。デフォルトはnullです。
        ListNode pre = null ;
        //現在のノード変数を定義し、最初にヘッドノードを割り当てます
        リストノード curr = head;
        //現在指しているノードが空になるまで、リンクリスト全体を走査します。これが最後のノードです。
        while(curr != null ){
            //ループ本体では、現在のノードのポインター方向が変更されます。元々、現在のノードのポインターは次のノードを指していますが、今度は前のノードを指すように変更する必要があります。ただし、直接変更すると、チェーンが壊れて、後続のノードが見つからなくなります。そのため、次のノードを一時的に保存し、後で使用できるようにtempに割り当てる必要があります。
            リストノードtemp = curr.next ;
            //現在のノードの処理を開始し、現在のノードのポインタを前のノードにポイントします
            curr.next = pre;
            //現在のノードを変数preに代入します。つまり、preを1ステップ移動し、preは現在のノードを指します。
            前 = 現在の;
            // 以前に保存した一時ノード（次のノード）を現在のノード変数に割り当てます
            curr = temp ;
            //ループ本体はリンクリストのステータス変更を実行します:
            // NULL <-1 2->3->4->5-> NULL  
            // NULL <-1<-2 3->4->5-> NULL  
            // NULL <-1<-2<-3 4->5-> NULL  
            // NULL <-1<-2<-3<-4 5-> NULL  
            // NULL <-1<-2<-3<-4<-5
            //ループ本体をトラバースした後、preはノード5を指します
        }
        //完了しました。時間計算量は O(n) です。
戻り値:
    }
 }