連結リスト
連結リストは、最も基本的なデータ構造の1つであり、他のデータ構造の実装に使われる。リンクリスト、リンクトリストとも表記される。
一連のノードが、任意のデータフィールド群を持ち、1つか2つの参照(リンク)により次(および前)のノードを指している。連結リストの主な利点は、リスト上のノードを様々な順番で検索可能な点である。連結リストは自己参照型のデータ型であり、同じデータ型の別のノードへのリンク(またはポインタ)を含んでいる。連結リストは場所が分かっていれば、ノードの挿入や削除を定数時間で行うことができる(場所を探すのにかかる時間はリスト上の順番の条件などにも依存するし、後述する片方向リストなのか双方向リストなのかにも依存する)。連結リストにはいくつかの種類があり、片方向リスト、双方向リスト、線形リスト、循環リストなどがある。
連結リストは多くのプログラミング言語で実装可能である。LISP や Scheme 、Prologといった言語は組み込みでこのデータ構造を持っていて、連結リストにアクセスするための操作も組み込まれている。
線形リストは、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" が開発された。これは双方リストの前方リンクと後方リンクの一貫性をチェックすることで問題を検出する。
線形リストには「ダミーノード」または「番兵ノード; sentinel node」と呼ばれるものが、リストの先頭や最後尾に置かれることがある。番兵ノードにはデータは格納されない。その目的は、全てのノードのリンクが常にノードのデータ構造を指していることを保証して、いくつかの操作を高速化することである。LISPではそのような設計がされており、nil と呼ばれる特別な値は片方向リストの最後尾を示すと決められている。nil は CAR 操作でも CDR 操作でも nil を返すため、一部の操作を高速化できる。最後尾が nil でないリストは不適切(improper)である(不適切とは言っても使えないということではない)。
連結リストは他のデータ構造の構成要素として使われる。例えば、スタック、キューなどである。
ノードのデータ部が別の連結リスト(へのポインタ)という構成も可能である。これを応用すると様々なデータ構造をリストで構成できる。これはLISPを起源とする方法であり、LISP では連結リストは主要なデータ構造とされ、今では関数型言語で一般に使われている。
連結リストを使って連想配列を実装することもあり、これを連想リスト(association list)と呼ぶ。このような連結リストの応用にはあまり利点がない。平衡2分探索木などのデータ構造の方が、ごく小さいデータ量であっても性能的に優れている。しかし、木構造のサブセットという範囲を超えて連結リストを動的に生成することもあり、より効率的にそのような構成のデータを扱うのに使われる。
コンピュータプログラミングと設計におけるほとんどの選択と同様、あらゆる状況に適した方法は存在しない。連結リストというデータ構造も状況によってはうまく機能するが、別の状況には適さない。以下では、連結リスト構造に関するトレードオフについて説明する。一般に動的に変化するデータの集まりがあって、要素の追加・削除が頻繁に行われ、新たな要素を追加する位置が重要となる場合、連結リストが適しているといえる。
連結リストは配列と比較したとき、いくつかの利点を持つ。リストでは要素の挿入は無制限に可能であるが、配列はサイズが決まっているために限界があり、配列を大きくしようとしても、メモリのフラグメンテーションによって不可能なこともある。同様に、配列から要素の多くを削除すると領域の無駄となったり、サイズを小さくする必要が生じる。
複数のリストが尾部を共有することで、さらにメモリを節約できる場合もある。つまり、先頭が複数あって、末尾が1つになっている構造が可能である。これを使って、何らかのデータの古いバージョンと新しいバージョンを同時に保持することが可能であり、簡単な永続データ構造の例となっている。
一方、配列はランダムアクセス性に優れており、連結リストがシーケンシャルアクセスを得意とするのと対照的である。片方向リストは一方向にしか辿れない。従って、ヒープソートのようにインデックスによって高速に要素を参照する必要がある場合、連結リストは不向きである。シーケンシャルアクセスも多くのマシン上では、連結リストよりも配列の方が高速である。これは、キャッシュメモリの効果と参照の局所性によるものである。連結リストはキャッシュメモリからはほとんど何も恩恵を受けない。
連結リストの別の欠点は、参照のための余分な領域を必要とする点である。このため、キャラクタやブーリアン型のような小さなデータ要素を連結リストで操作するのは(1文字ごとにノードを割り当てて文字列操作を実現するなど)、速度の面でもメモリ消費の面でも無駄が多く、現実的でない。
これらの問題の一部を改善する連結リストの派生データ構造がいくつか存在する。Unrolled linked list は各ノードに複数の要素を格納するもので、キャッシュ性能を向上させ、参照時のメモリのオーバヘッドを低減させる。CDRコーディングも参照を参照すべき実データと置換することで同様の効果が得られる。
配列との比較で利点と欠点を明確にする好例として、ジョセファスの問題を解くプログラムの実装がある。ジョセファスの問題とは、人間が輪になって並んでいる状況で、そこから1人を選ぶというものである。ある人を開始点として、特定の方向に n 人を数えていく。n 番目の人に到達したら、その人を輪から外して、残りの人間で一回り小さい輪を作る。そして再び n 番目まで数えていく。これを1人だけが残るまで繰り返し、最後に残った人が選ばれた人ということになる。これを循環リストを使って表すのは直接的で分かり易いし、ノードの削除も簡単である。しかし、循環リストでは、現在のノードから n 番目のノードを見つけるには、リストを順に辿っていくしかない。配列であればインデックスの計算で即座に見つけられる。一方、配列では要素(ノード)の削除は容易ではなく、n 番目のノードを即座に見つけるという利点を生かすには、ノードを削除したときに残った要素を詰めてやる必要がある。
双方向リストはノード毎に要するメモリ量が多くなるし、基本的な操作にかかる手間が多くなる。しかし、どちらの方向にもシーケンシャルアクセス可能であるため、扱いやすくなることが多い。特に、あるノードの削除をする場合、そのノードのアドレスさえ分かっていれば、定数時間でそれが可能である。挿入の場合も、挿入する位置(そのノードの前に新たなノードを挿入する)が判っていれば、双方向リストでは定数時間で挿入が可能である。片方向リストでは、挿入・削除の際に1つ前のノードのアドレスも知る必要がある。アルゴリズムによっては双方向のアクセスが必須な場合もある。一方、双方向リストでは尾部の共有はできないので、永続データ構造としては使えない。
循環リストは、本質的に環状の構造を表すのに適している。また、どのノードからでもリスト全体をたどることが可能である。また、(最後尾のノードを指す)ポインタを1つ保持しておけば、先頭と最後尾を同時に効率的にアクセス可能である。主な欠点は、繰り返し処理をする際に、微妙に複雑な配慮を要する点である。
番兵ノードを使えば、全てのノードに次のノードや前のノードが存在することを保証でき、特定のリスト操作を単純化できる。しかし、(特に小さなリストを多数使用する場合)余分な領域を必要とするという欠点があり、他のリスト操作は逆に複雑化する。余分な領域を消費するのを防ぐため、番兵ノードはリストの先頭あるいは最後尾のノードへの参照として再利用されることがある。
連結リストを操作する場合、無効化され使われなくなった値の扱いに注意する必要がある。そのため、連結リストでの挿入・削除のアルゴリズムはある意味で巧妙である。ここでは、片方向リスト、双方向リスト、循環リストでのノードの追加と削除に関する擬似コードを示す。リストの終端を表すマーカー(あるいは番兵)としては "null" を使うが、その実装は様々なものが考えられる。
LISPやScheme、Prologといったプログラミング言語は、片方向リストを組み込みで装備している。多くの関数型言語では、リストを構成するノードを「consセル」と呼ぶ。consセルには "car" 部分と "cdr" 部分があり、"car" 部はそのノードのデータへの参照、"cdr" 部は次のノードへの参照を格納している。consセルは他のデータ構造にも使われるが、主な用途はリストを構成することである。
抽象データ型やテンプレートをサポートする言語では、連結リストの抽象データ型やテンプレートを使って、連結リストを構築できる。
オブジェクト指向プログラミング言語では、次のようなクラスが連結リスト用に用意されている。
C++(STL) - <tt>std::list<T></tt>クラス(<tt></tt>)
Java - <tt>java.util.java/util</tt>クラス
.NET - <tt>System.Collections.Generic.LinkedList<T></tt>クラス
以下に、C言語での片方向リストの例を示す。
連結リストを構築する際、データをノードそのものに格納するか、別のデータ構造への参照のみを格納するかという選択を迫られる。前者を「」、後者を「」と呼ぶ。内部収納の方がデータアクセスが効率化され、全体としてメモリ使用量が低減され、参照の局所性が向上し、リストに関するメモリ管理も簡素化される(データはノードと共に確保・解放される)。
一方、外部収納はより汎用的だという利点がある。データの内容に依存しないデータ構造とリスト操作コードを形成可能である。また、複数のノードで同じデータを共有することも容易に実現できる。内部収納の場合も、通常のリンクとは別に、同じ内容のデータを保持するノードを連結するフィールドを持てば、同様のことが可能になるが、リスト操作にあたってそれも考慮する必要が出てくる。
一般に、データ構造を複数の連結リストに属させる必要がある場合、外部収納が最善の手法である。データ構造が1つの連結リストにしか属さない場合、内部収納の方が若干良いが、外部収納の汎用リスト操作パッケージが利用可能なら、それを利用するほうがよい場合もある。
いくつかの言語で採用されている別の手法として、いくつかの種類のデータ構造があって、それらの先頭部分の同じ位置にリストのための "next" および "prev" のフィールドが存在する場合がある。この場合、リスト操作は汎用的なルーチンを使い、個々のノード内のデータは個別のルーチンで処理する。様々な種類のメッセージを受信する際の構文解析などでよく使われる。メッセージのキューへの追加と削除は汎用的なルーチンで行われる。メッセージの種類がメッセージの先頭にあり、それを見て適切なメッセージ処理ルーチンを呼び出す。
ここでは、家族とその構成員の連結リストを処理するコードを例として示す。内部収納の場合、構造体は次のようになる。
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つのリストに対して、そのようなインデックスを複数構築できる。この手法の欠点は、ノードの追加や削除の度にインデックス側の更新が必要となる点である。少なくともインデックスを再利用する前に更新が必要である。
スタックとキューは連結リストを使って実装されることが多く、単にリストで許されている操作を制限するだけでよい。
スキップリストは、ポインタが階層化された連結リストであり、多数のノードを高速に飛ばして検索可能である。
二分木は、データ部も同じような連結リストへのリンクになっている連結リストと見なすこともできる。各ノードは2つのノードへのリンクになっており、それぞれが部分木の頂点を指している。
unrolled linked list は、各ノードに配列が置かれている形式の連結リストである。主に参照の局所性を高め、性能を向上させる目的で使われる。
ハッシュテーブルは、ハッシュ値が衝突しているデータを保持する際に連結リストの構造を使うことがある。
(Slashdot)
(スラッシュドット ジャパン)
Antonakos, James L. and Mansfield, Kenneth C., Jr. Practical Data Structures Using C/C++ (1999). Prentice-Hall. ISBN 0-13-280843-9, pp. 165–190
Collins, William J. Data Structures and the Java Collections Framework (2002,2005) New York, NY: McGraw Hill. ISBN 0-07-282379-8, pp. 239–303
Cormen, Thomas H.; Leiserson, Charles E.; Rivest, Ronald L.; Stein, Clifford Introductions to Algorithms (2003).  MIT Press. ISBN 0-262-03293-7, pp. 205–213, 501–505
Green, Bert F. Jr. (1961).  Computer Languages for Symbol Manipulation.  IRE Transactions on Human Factors in Electronics. 2 pp. 3-8.
McCarthy, John (1960). Recursive Functions of Symbolic Expressions and Their Computation by Machine, Part I. Communications of the ACM.
Donald Knuth. Fundamental Algorithms, Third Edition. Addison-Wesley, 1997. ISBN 0-201-89683-4. Sections 2.2.3–2.2.5, pp.254–298.
Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, and Clifford Stein. Introduction to Algorithms, Second Edition. MIT Press and McGraw-Hill, 2001. ISBN 0-262-03293-7. Section 10.2: Linked lists, pp.204–209.
Newell, Allen and Shaw, F. C. (1957). Programming the Logic Theory Machine.  Proceedings of the Western Joint Computer Conference. pp. 230-240.
Parlante, Nick (2001). Linked list basics. Stanford University.
Sedgewick, Robert Algorithms in C (1998). Addison Wesley. ISBN 0-201-31452-5, pp. 90–109
Shaffer, Clifford A. A Practical Introduction to Data Structures and Algorithm Analysis (1998). NJ: Prentice Hall. ISBN 0-13-660911-2, pp. 77–102
Wilkes, Maurice Vincent (1964). An Experiment with a Self-compiling Compiler for a Simple List-Processing Language. Annual Review in Automatic Programming 4, 1. Published by Pergamon Press.
Wilkes, Maurice Vincent (1964). Lists and Why They are Useful. Proceeds of the ACM National Conference, Philadelphia 1964 (ACM Publication P-64 page F1-1); Also Computer Journal 7, 278 (1965).
Kulesh Shanmugasundaram (2005年4月4日). .