連結リスト
連結リスト（れんけつリスト、英語: Linked list）は、最も基本的なデータ構造の1つであり、他のデータ構造の実装に使われる。リンクリスト、リンクトリストとも表記される。
出典: フリー百科事典『ウィキペディア（Wikipedia）』
連結リストは、複数のノードからなり、あるノードから別のノードへのリンク（参照、ポインタ）を持つことで順序を持たせたデータ構造です。
最後のリンクは Null を指すことで終わりを意味します。
連結リストのそれぞれのノードは、自身のデータと、次のノードを指すリンクを持ちます。
スタックやキューといったデータ構造を表すための土台として使われます。
単純な連結リストは、インデックスを持っておらず、配列のようなランダムアクセスを行うことができません。最初にアクセスできるのは、ルート、つまり先頭のノードだけです。
連結リストの利点
配列はサイズが事前に決まっていますが、連結リストはサイズが事前には決まっていない動的なデータ構造であり、要素の追加を制限なく行うことができます。
また、配列と異なり、実行時に必要なだけのメモリを確保するだけで済みます。
また、連結リストは、連続したデータの最初へのデータの挿入や削除が\(O (1)\)で行うことができ、\( O (N) \)である配列より高速になります。
連結リストの欠点
連結リストは、データ自身とその次のノードへのリンクを持つので、データ一つあたりの記憶領域が、データ自身しか持たない配列より大きくなります。
連結リストのデータを読み込む際は、インデックスを用いて任意のデータにアクセスできる配列とは異なり、必ず一番最初のデータから一つずつアクセスしていかなければなりません。
一方向の連結リストの場合は、逆順のデータへのアクセス（最後から先頭へのアクセス）がとても大変なものになります。この問題をクリアするために、次のノードへのポインタだけでなく前のノードへのポインタを持つ双方向の連結リストを使いますが、メモリ効率はより悪くなってしまいます。
連結リストの操作
値の挿入 Insert
連結リストの先頭へのデータの挿入は、次のノードへのポインタを更新するだけで終わり、\( O(1) \)で行うことができます。配列ではこの操作に\( O (N) \)かかるので、 配列と比較した場合の 連結リストの大きな利点です。
逆に、単純な連結リストの場合、最後尾へのデータの挿入は、ポインタが Null を示すノード（つまり最後尾のノード）へ到着するまで\( O (N) \) になり、ポインタの更新は\( O (1) \)なので、計\( O (N) \)かかります。配列はこの操作を\( O (1) \) で行えます。
値の削除 Remove
連結リストの先頭のデータの削除は、挿入と同様に\( O (1) \) で、途中のデータの削除はそのデータへ到着するまで\( O(N) \) の計算量が必要になり\( O(N) \) になります。
双方向連結リスト Doubly linked list
片方向の連結リストでは難しかった逆順のデータへのアクセスを行うために、双方向の連結リストが使われます。
双方向の連結リストは、ノードが次のノードへのポインタと前のノードへのポインタを保持します。先頭のノードのポインタと最後のノードのポインタは、Null を指します。
このようなデータ構造にすることにより、先頭ノードから、または最後のノードからの両方向から、リストの探索を行うことができるようになります。
ポインタが増える分、双方向の連結リストは片方向の連結リストと比べて多くのメモリを消費します。
配列と連結リストの比較
要素の取り出し
配列の方が速いです。
配列はインデックスを使ったランダムアクセスにより\( O (1) \) で要素を取り出せます。
連結リストは、リストの先頭から一つずつ要素を確認する必要があり、\( O (N) \) の計算量になります。
要素の削除
ケースバイケースです。
配列は最初の値の削除は\( O(N) \)、最後の値の削除は\( O(1) \) の計算量になります。
連結リストは最初の値の削除は\( O(1) \)、最後の値の削除は\( O(N) \) の計算量になります。
具体的な操作を考えると、要素の削除を行う際 、配列では配列全体の再構成を行いますが、連結リストではポインタの指し示すノードを変更するだけです。
メモリ
配列の方が優れます。
配列はデータ以外のメモリは必要としませんが、連結リストはポインタの分必要なメモリが増えます。
