連結リスト

連結リスト（れんけつリスト、英語: Linked list）は、最も基本的なデータ構造の1つであり、他のデータ構造の実装に使われる。リンクリスト、リンクトリストとも表記される。
一連のノードが、任意のデータフィールド群を持ち、1つか2つの参照（リンク）により次（および前）のノードを指している。連結リストの主な利点は、リスト上のノードを様々な順番で検索可能な点である。連結リストは自己参照型のデータ型であり、同じデータ型の別のノードへのリンク（またはポインタ）を含んでいる。連結リストは場所が分かっていれば、ノードの挿入や削除を定数時間で行うことができる（場所を探すのにかかる時間はリスト上の順番の条件などにも依存するし、後述する片方向リストなのか双方向リストなのかにも依存する）。連結リストにはいくつかの種類があり、片方向リスト、双方向リスト、線形リスト、循環リストなどがある。
連結リストは多くのプログラミング言語で実装可能である。LISP や Scheme 、Prologといった言語は組み込みでこのデータ構造を持っていて、連結リストにアクセスするための操作も組み込まれている。手続き型やオブジェクト指向型の言語（C言語、C++、Java）では、連結リストを作るには mutable（更新可能）な参照を必要とする。

歴史

線形リストは、1955年から1956年ごろ、ランド研究所にてアレン・ニューウェル、Cliff Shaw、ハーバート・サイモンが Information Processing Language (IPL) の主要データ構造として開発したのが最初である。IPL はいくつかの初期の人工知能プログラム（General Problem Solver など）で使われた。線形リストを箱と矢印で表すという今ではお馴染みの記法は、1957年2月の "Proceedings of the Western Joint Computer Conference" に掲載されたニューウェルと Shaw の "Programming the Logic Theory Machine" という論文で使われている。ニューウェルとサイモンは1975年、「人工知能、認知心理学、リスト処理の基盤を築いた」ことに対してチューリング賞を受賞した。
マサチューセッツ工科大学 (MIT) の Victor Yngve は、自然言語処理、特に機械翻訳向けに開発した COMIT という言語学向けのプログラミング言語で線形リストをデータ構造として使っている。これに関する論文は1958年、"Mechanical Translation" に "A programming language for mechanical translation" と題して掲載された。
1958年、ジョン・マッカーシーが MIT で開発したLISPは "list processor" の略であり、1960年に "Communications of the ACM" にその設計に関する論文 "Recursive Functions of Symbolic Expressions and Their Computation by Machine, Part I" が掲載された。LISP の主要なデータ構造の一つとして線形リストが採用されている。
1960年代初期までに、線形リストやそれを基本的なデータ構造とする言語が一般化した。MIT リンカーン研究所の Bert Green は1961年3月、"IRE Transactions on Human Factors in Electronics" に "Computer languages for symbol manipulation" という論文を書き、線形リストを使った手法の利点をまとめている。同様の論文は1964年4月、Communications of the ACM に Bobrow と Raphael の "A Comparison of list-processing computer languages" が掲載されている。
Technical Systems Consultants (TSC) 社は、片方向リストをファイル構造に利用したオペレーティングシステム FLEXを開発した。ディレクトリがファイルの第一セクターを指し、その後のファイルの中身も線形リストのポインタを辿ることで得られるようになっていた。FLEX から派生したオペレーティングシステムとして Smoke Signal Broadcasting社が開発したものがあるが、こちらは双方向リストを同じ用途に使っていた。
IBM社が System/360やSystem/370向けに開発したTSSでも、ファイルシステムに双方向リストを使っていた。そのディレクトリ構造は UNIX のものと似ており、ディレクトリはファイルや他のディレクトリを格納でき、任意の深さまで階層構造を作ることができた。システムがクラッシュしたとき、このファイルシステム構造の一部がディスクに書き戻されていない場合があり、これを修復するためのユーティリティ "flea" が開発された。これは双方リストの前方リンクと後方リンクの一貫性をチェックすることで問題を検出する。

線形リスト

線形リストには、片方向リストと双方向リストがあり、どちらも任意の位置でデータの追加・削除が"O(1)"時間でできるのが特長である。しかし、ソートされた配列や木構造と違い、データの検索はO(n)時間かかってしまうという欠点がある（ソートされていない配列は線形リストと同じ"O(n)"の検索時間である）。

片方向リスト

片方向リスト（singly-linked list）は、最も単純な連結リストであり、ノード毎に1つのリンクを持つ。このリンクはリスト上の次のノードを指し、リストの最後尾ならNull値を格納するか、空のリストを指す。

双方向リスト

双方向リスト（doubly-linked list）は、より洗練された連結リスト。各ノードには2つのリンクがあり、1つが次のノード（前方リンク）、もう1つが後ろのノード（後方リンク）を指す。リストの先頭のノードには後ろのノードがないので、後方リンクにはヌル値を格納するか、空のリストを指す。リストの最後尾のノードには次のノードがないので、前方リンクにはヌル値を格納するか、空のリストを指す。
低レベルの言語の中には、XOR連結リストを使って双方向リストの2つのリンクを1つのワードで表せるようにしたものもあるが、この技法は一般には使われない。

循環リスト

循環リスト（circularly-linked list）では、先頭と最後尾のノードを相互に連結する。循環リストには片方向のものも双方向のものもある。循環リストを辿る場合、任意のノードから出発して、好きな方向にたどっていき、最初のノードに戻ってくるまで続ける。つまり、循環リストは先頭や最後尾といったものが存在しないリストと考えることもできる。循環リストはデータ格納用バッファの管理によく使われ、1つのノードを使っているスレッド（やプロセス）が他のノードを全て参照したい場合などに便利である。
リスト全体を指すポインタは、アクセスポインタと呼ばれることがある。

片方向循環リスト

片方向循環リスト（singly-circularly-linked list）では、各ノードは線形の片方向リストと同じように1つのリンクを持つが、最後尾のノードは先頭のノードをリンクしている。片方向リストと同様、新たなノードを挿入する場合、既に参照を持っているノードの次の位置にのみ挿入できる。このため、片方向循環リストでは、最後尾のノードを指している参照を保持しておくことが多く、それによって、先頭位置に高速に挿入可能とするだけでなく、先頭ノードから最後尾のノードまでを順に辿ることも可能にしている。

双方向循環リスト

双方向循環リスト（doubly-circularly-linked list）では、各ノードは線形の双方向リストと同じように2つのリンクを持つが、先頭ノードの後方リンクは最後尾ノードを指し、最後尾ノードの前方リンクは先頭ノードを指す。双方向リストと同様、挿入も削除もその位置に隣接するノードへの参照が1つあれば、高速に行える。構造的には双方向循環リストには先頭も最後尾もないが、一般に外部のアクセスポインタを用意して、先頭または最後尾のノードを指しておくことが多い。そして、双方向リストでの番兵ノードのように順序を把握するのに使われる。

番兵ノード

線形リストには「ダミーノード」または「番兵ノード; sentinel node」と呼ばれるものが、リストの先頭や最後尾に置かれることがある。番兵ノードにはデータは格納されない。その目的は、全てのノードのリンクが常にノードのデータ構造を指していることを保証して、いくつかの操作を高速化することである。LISPではそのような設計がされており、nil と呼ばれる特別な値は片方向リストの最後尾を示すと決められている。nil は CAR 操作でも CDR 操作でも nil を返すため、一部の操作を高速化できる。最後尾が nil でないリストは不適切（improper）である（不適切とは言っても使えないということではない）。

応用

連結リストは他のデータ構造の構成要素として使われる。例えば、スタック、キューなどである。
ノードのデータ部が別の連結リスト（へのポインタ）という構成も可能である。これを応用すると様々なデータ構造をリストで構成できる。これはLISPを起源とする方法であり、LISP では連結リストは主要なデータ構造とされ、今では関数型言語で一般に使われている。
連結リストを使って連想配列を実装することもあり、これを連想リスト（association list）と呼ぶ。このような連結リストの応用にはあまり利点がない。平衡2分探索木などのデータ構造の方が、ごく小さいデータ量であっても性能的に優れている。しかし、木構造のサブセットという範囲を超えて連結リストを動的に生成することもあり、より効率的にそのような構成のデータを扱うのに使われる。

トレードオフ

コンピュータプログラミングと設計におけるほとんどの選択と同様、あらゆる状況に適した方法は存在しない。連結リストというデータ構造も状況によってはうまく機能するが、別の状況には適さない。以下では、連結リスト構造に関するトレードオフについて説明する。一般に動的に変化するデータの集まりがあって、要素の追加・削除が頻繁に行われ、新たな要素を追加する位置が重要となる場合、連結リストが適しているといえる。

双方向と片方向

双方向リストはノード毎に要するメモリ量が多くなるし、基本的な操作にかかる手間が多くなる。しかし、どちらの方向にもシーケンシャルアクセス可能であるため、扱いやすくなることが多い。特に、あるノードの削除をする場合、そのノードのアドレスさえ分かっていれば、定数時間でそれが可能である。挿入の場合も、挿入する位置（そのノードの前に新たなノードを挿入する）が判っていれば、双方向リストでは定数時間で挿入が可能である。片方向リストでは、挿入・削除の際に1つ前のノードのアドレスも知る必要がある。アルゴリズムによっては双方向のアクセスが必須な場合もある。一方、双方向リストでは尾部の共有はできないので、永続データ構造としては使えない。

循環と線形

循環リストは、本質的に環状の構造を表すのに適している。また、どのノードからでもリスト全体をたどることが可能である。また、（最後尾のノードを指す）ポインタを1つ保持しておけば、先頭と最後尾を同時に効率的にアクセス可能である。主な欠点は、繰り返し処理をする際に、微妙に複雑な配慮を要する点である。

番兵ノード

番兵ノードを使えば、全てのノードに次のノードや前のノードが存在することを保証でき、特定のリスト操作を単純化できる。しかし、（特に小さなリストを多数使用する場合）余分な領域を必要とするという欠点があり、他のリスト操作は逆に複雑化する。余分な領域を消費するのを防ぐため、番兵ノードはリストの先頭あるいは最後尾のノードへの参照として再利用されることがある。

連結リストの操作

連結リストを操作する場合、無効化され使われなくなった値の扱いに注意する必要がある。そのため、連結リストでの挿入・削除のアルゴリズムはある意味で巧妙である。ここでは、片方向リスト、双方向リスト、循環リストでのノードの追加と削除に関する擬似コードを示す。リストの終端を表すマーカー（あるいは番兵）としては "null" を使うが、その実装は様々なものが考えられる。

片方向リスト

ここでのノードのデータ構造には2つのフィールドがある。また、List の "firstNode" というフィールドがリストの先頭ノード（空のリストの場合は "null"）を指すとする。
 record Node {
    data // ノードに格納されるデータ    next // 次のノードへの参照（最後尾の場合は null）
 }
 record List {
     Node firstNode   // リストの先頭ノードを指す（空のリストの場合は null）
 }
片方向リストを辿るのは単純で、先頭ノードから各ノードの "next" リンクを最後まで辿っていく。
 node := list.firstNode
 while node ≠ null {
     (node.data に何かをする)
     node := node.next
 }
次のコードは片方向リスト上のあるノードの次に新たにノードを挿入する。あるノードの前にノードを挿入することはできない。その場合は挿入位置の前のノードを見つける必要がある。
 function insertAfter(Node node, Node newNode) { // newNode を node の次に挿入     newNode.next := node.next
     node.next    := newNode
 }
リストの先頭にノードを追加する場合、別の関数が必要である。この場合、firstNode を更新しなければならない。
 function insertBeginning(List list, Node newNode) { // 現在の先頭ノードの前にノードを挿入     newNode.next   := list.firstNode
     list.firstNode := newNode
 }
同様に、指定されたノードの次のノードを削除する関数と、リストの先頭のノードを削除する関数を示す。特定のノードを探して削除する場合、その前のノードを覚えておく必要がある。
 function removeAfter(Node node) { // このノードの次のノードを削除     obsoleteNode := node.next
     node.next := node.next.next
     destroy obsoleteNode
 }
 function removeBeginning(List list) { // 先頭ノードを削除     obsoleteNode := list.firstNode
     list.firstNode := list.firstNode.next          // 削除されるノードの次を指す     destroy obsoleteNode
 }
removeBeginning() は、削除するノードが最後のノードだった場合、"list.firstNode" を "null" にする。
逆方向に繰り返すことができないので、"insertBefore" や "removeBefore" といった操作を効率的に実装することはできない。
2つの片方向リストを連結したい場合、リストの最後尾を常に保持していないと効率的に処理できない。2つのリストがそれぞれ長さ  である場合、連結にかかる時間は  となる。LISP 系言語では、リストの連結には append を使う。
片方向リストの操作は先頭ノードの扱いが特殊であるが、先頭にダミー要素を追加することでこれを排除できる。これによって、"insertBeginning()" や "removeBeginning()" が不要となる。この場合、最初のデータを持ったノードは "list.firstNode.next" で参照可能である。

双方向リスト

双方向リストでは更新すべきポインタが増えるが、逆方向のポインタでリスト上の前の要素を参照できるため、操作に必要な情報は少なくて済む。これにより、新たな操作が可能となり、特殊ケースの関数が不要になる。ノードには前の要素を指す "prev" フィールドが追加される。また リスト構造の "lastNode" が最後尾のノードを指す。空のリストの場合、"list.firstNode" も "list.lastNode" も "null" である。
 record Node {
    data // ノードに格納されるデータ    next // 次のノードへの参照（最後尾の場合は null）
    prev // 前のノードへの参照（先頭の場合は null）
 }
 record List {
     Node firstNode   // リストの先頭ノードを指す（空のリストの場合は null）
     Node lastNode    // リストの最後尾ノードを指す（空のリストの場合は null）
 }
双方向リストでは双方向に繰り返しが可能である。方向は必要に応じて何度でも変えられる。
順方向
 node := list.firstNode
 while node ≠ null
     <node.data に対して何か行う>
     node := node.next
逆方向
 node := list.lastNode
 while node ≠ null
     <node.data に対して何か行う>
     node := node.prev
指定したノードの次に新たなノードを挿入する関数と、前に挿入する関数を示す。
 function insertAfter(List list, Node node, Node newNode)
     newNode.prev := node
     newNode.next := node.next
     if node.next = null
         list.lastNode := newNode
     else
         node.next.prev := newNode
     node.next := newNode
 function insertBefore(List list, Node node, Node newNode)
     newNode.prev := node.prev
     newNode.next := node
     if node.prev is null
         list.firstNode := newNode
     else
         node.prev.next := newNode
     node.prev    := newNode
空のリストを含むリストの先頭に新たなノードを挿入する関数が必要となる。
 function insertBeginning(List list, Node newNode)
     if list.firstNode = null
         list.firstNode := newNode
         list.lastNode  := newNode
         newNode.prev := null
         newNode.next := null
     else
         insertBefore(list, list.firstNode, newNode)
同様に、最後尾にノードを挿入する関数を示す。
 function insertEnd(List list, Node newNode)
     if list.lastNode = null
         insertBeginning(list, newNode)
     else
         insertAfter(list, list.lastNode, newNode)
ノードの削除は簡単で、firstNode と lastNode にだけ注意すればよい。
 function remove(List list, Node node)
   if node.prev = null
       list.firstNode := node.next
   else
       node.prev.next := node.next
   if node.next = null
       list.lastNode := node.prev
   else
       node.next.prev := node.prev
   destroy node
この手続きで、リストから1つだけ残っているノードを削除する場合、"firstNode" と "lastNode" が "null" に設定され、正しく処理が行われる。また、"removeBefore" や "removeAfter" といった手続きは不要であり、単に "remove(node.prev)" や "remove(node.next)" を呼び出せばよい。

循環リスト

循環リストには、片方向のものと双方向のものがある。循環リストでは環状にノードが連結されているので、"null" は使わない。キューのような前後関係のあるリストでは、リストの最後尾ノードへの参照を保持する必要がある。循環リストでは最後尾ノードの次のノードは先頭ノードである。要素の最後尾への追加や先頭からの削除は定数時間で可能である。
循環リストの利点は、任意のノードから開始してリスト全体をたどることができる点である。このため、"firstNode" や "lastNode" も保持する必要がないことが多いが、空のリストを表すには何らかの特別な表現が必要である。ここでは "lastNode" に "null" を格納することで空のリストを表す。これにより空でないリストでの追加・削除は大幅に単純化されるが、空のリストを特殊ケースとして扱う必要がある。

双方向循環リスト

someNode は空でないリストにある何らかのノードであるとする。ここでは任意の "someNode" から繰り返しを開始するものとしている。
順方向
 node := someNode
 do
     node.value について何か行う     node := node.next
 while node ≠ someNode
逆方向
 node := someNode
 do
     node.value について何か行う     node := node.prev
 while node ≠ someNode
ループの最後で終了条件のチェックをしている点に注意されたい。これは、リストに "someNode" という1つのノードしかない場合に重要である。
次の関数は双方向循環リスト上のノードの次に新たなノードを追加する。
 function insertAfter(Node node, Node newNode)
     newNode.next := node.next
     newNode.prev := node
     node.next.prev := newNode
     node.next      := newNode
"insertBefore" を実現したければ、単に "insertAfter(node.prev, newNode)" を行えばよい。空のリストへのノードの追加は次の特殊関数が必要となる。
 function insertEnd(List list, Node node)
     if list.lastNode = null
         node.prev := node
         node.next := node
     else
         insertAfter(list.lastNode, node)
     list.lastNode := node
先頭に挿入したければ、"insertAfter(list.lastNode, node)" を実行すればよい。ノードの削除では空のリストにうまく対処する必要がある。
 function remove(List list, Node node)
     if node.next = node
         list.lastNode := null
     else
         node.next.prev := node.prev
         node.prev.next := node.next
         if node = list.lastNode
             list.lastNode := node.prev;
     destroy node
双方向リストと同様、"removeAfter" と "removeBefore" は "remove(list, node.prev)" と "remove(list, node.next)" で実現可能である。

内部収納と外部収納の例

ここでは、家族とその構成員の連結リストを処理するコードを例として示す。内部収納の場合、構造体は次のようになる。
 record member { // 家族のメンバー     member next
     string firstName
     integer age
 }
 record family { // 家族
     family next
     string lastName
     string address
     member members // この家族のメンバーのリストの先頭 }
家族のリストと各家族のメンバーを表示するルーチンは、内部収納の場合、次のようになる。
 aFamily := Families // 家族リストの先頭から開始 while aFamily ≠ null { // 家族リスト上でループ     家族に関する情報を印字     aMember := aFamily.members // その家族のメンバーのリストの先頭を得る     while aMember ≠ null { // メンバーのリスト上でループ         メンバーに関する情報を印字         aMember := aMember.next
     }
     aFamily := aFamily.next
 }
外部収納を使うと、構造体は次のようになる。
 record node { // 汎用リンク構造体     node next
     pointer data // ノードに付属するデータを指す汎用ポインタ }
 record member { // 家族構成員に関する構造体     string firstName
     integer age
 }
 record family { // 家族に関する構造体     string lastName
     string address
     node members // この家族のメンバーのリストの先頭 }
家族のリストと各家族のメンバーを表示するルーチンは、外部収納の場合、次のようになる。
 famNode := Families // 家族リストの先頭から開始 while famNode ≠ null { // 家族リスト上でループ     aFamily = (family)famNode.data // ノードから家族データ構造体を取り出す     家族に関する情報を印字     memNode := aFamily.members // その家族のメンバーのリストの先頭を得る     while memNode ≠ null { // メンバーのリスト上でループ
         aMember := (member)memNode.data // ノードからメンバーデータ構造体を取り出す         メンバーに関する情報を印字         memNode := memNode.next
     }
     famNode := famNode.next
 }
外部収納を使った場合、データ構造体を取り出して型変換するという余分なステップが必要になる。これは、2種類の連結リストが同じデータ構造（node）を使っているためである。
あるメンバーがいくつの家族に属することができるかがコンパイル時に分かっている場合、内部収納の方が適している。しかし、1人のメンバーが任意の個数の家族に属する可能性がある場合、かつその数が実行時にならないと分からない場合、外部収納にする必要がある。

検索の高速化

連結リストで特定の要素を探す場合、たとえそれがソート済みであっても一般に O(n) の時間を要する（線型探索）。これは連結リストの重大な欠点である。これを改善するいくつかの方法が存在する。
ソートされていないリストでは、平均検索時間を短縮する単純なヒューリスティックとして "Move To Front" と呼ばれる手法がある。これは、1度検索して見つかったノードをリストの先頭に移動させるという方式である。これは一種の簡単なキャッシュ構成法であり、最も後に検索したノードを再度検索する場合に高速化される。
もう1つの一般的な手法は、より効率的な外部のデータ構造を使ってノードにインデックスを付けるというものである。例えば、赤黒木やハッシュテーブルを構築し、その要素が連結リストの各ノードへの参照を持つようにする。1つのリストに対して、そのようなインデックスを複数構築できる。この手法の欠点は、ノードの追加や削除の度にインデックス側の更新が必要となる点である。少なくともインデックスを再利用する前に更新が必要である。