アルゴリズムとデータ構造（連結リスト・双方向リスト）

2022年2月13日2024年3月5日

前回の記事では、リスト（配列）について、解説しました。

リストは、要素の挿入、削除といった操作を行う場合、時間がかかること示しました。

また、リストは要素数が事前に定義が必要でした。

今回は、可変長のデータ構造で、要素の挿入・削除の時間が定数時間で行える、線形リスト及び双方向リストを紹介します。

連結リスト

連結リスト（Linked List）は、以下のようにリストの要素をポインタで繋いだデータ構造です。

線形リストは、線形リスト（Linear List）とも呼ばれます。

連結リストでは、要素数がわかっていない状況でも、連結リストが持つ要素数を可変させることができるので、使用できます。

しかし、ポインタ分の容量が増えるので、リストよりデータ使用量は増えます。Initは先頭のポインタを指します。最後の要素にはNULLを格納し、それ以上先の要素は存在しないことを示します。

この連結リストに対して、前回記事と同様に、以下の操作を行うことを考えます。

このリストに対して以下の操作を行うことを考えます。

順番に一つずつ見ていきましょう。

位置\(p\)の次の位置に要素\(x\)の挿入する場合を考えます。この場合、以下の図のように、まず位置pが指す要素を追加する要素に変更します。追加した要素が指す先を、pの次の位置にします。

つまり、ポインタの張り替える操作だけで完結するので、要素数には依存せず定数時間で終了します。

したがって、\(O(1)\)となります。

位置\(p\)の次の位置の要素を削除する場合を考えます。

この場合、

追加した要素が指す先を、pの次の位置にします。

先頭から順にi番目まで、ポインタを辿る必要があるので、最悪の場合\(O(n)\)となります。

つまり、リストと異なりシーケンシャルのアクセス方法となります。

要素xの検索は、Initから順番にxかどうか判定する必要があるので、\(O(n)\)となります。

Top()は単純にInitが先頭を指すので、\(O(1)\)で先頭の位置を取得することができます。

最後の位置を取得するには、Initから順番に辿り、次の要素がNULL（辿れなくなる）になるまで、走査する必要があるので\(O(n)\)となります。

位置pが指す次の要素がp+1になるので、定数時間\(O(1)\)となります。

連結リストは、次の要素のポインタしか持たないため、後ろ向きには辿ることができません。

そのため、Initから順番に今の位置がpになっているかどうか判定することで、p-1を取得します。

したがって、\(O(n)\)となります。

双方向リスト（Linked List）は、連結リストを拡張したデータ構造です。

連結リストは、各要素は次の要素のポインタを持っていましたが、双方向リストは以下の図のように、前の要素のポインタを持つように拡張されています。

連結リストよりもデータ使用量は多くなりますが、連結リストでは時間がかかるPreviousなどが定数時間で行えることが特徴です。

Initは先頭の要素を指すポインタ、Finは最後の要素を指すポインタを表しています。

双方向リストに対しても、以下の操作を行うことを考えます。

順番に一つずつ見ていきましょう。