連結リスト
連結リスト（れんけつリスト、テンプレート:Lang-en）は、最も基本的なデータ構造の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値を格納するか、空のリストを指す。
3つの整数値を格納した片方向リスト
双方向リスト
双方向リスト（doubly-linked list）は、より洗練された連結リスト。各ノードには2つのリンクがあり、1つが次のノード（前方リンク）、もう1つが後ろのノード（後方リンク）を指す。リストの先頭のノードには後ろのノードがないので、後方リンクにはヌル値を格納するか、空のリストを指す。リストの最後尾のノードには次のノードがないので、前方リンクにはヌル値を格納するか、空のリストを指す。
3つの整数値を格納した双方向リスト
低レベルの言語の中には、XOR連結リストを使って双方向リストの2つのリンクを1つのワードで表せるようにしたものもあるが、この技法は一般には使われない。
循環リスト
循環リスト（circularly-linked list）では、先頭と最後尾のノードを相互に連結する。循環リストには片方向のものも双方向のものもある。循環リストを辿る場合、任意のノードから出発して、好きな方向にたどっていき、最初のノードに戻ってくるまで続ける。つまり、循環リストは先頭や最後尾といったものが存在しないリストと考えることもできる。循環リストはデータ格納用バッファの管理によく使われ、1つのノードを使っているスレッド（やプロセス）が他のノードを全て参照したい場合などに便利である。
リスト全体を指すポインタは、アクセスポインタと呼ばれることがある。
3つの整数値を格納した循環リスト
片方向循環リスト
片方向循環リスト（singly-circularly-linked list）では、各ノードは線形の片方向リストと同じように1つのリンクを持つが、最後尾のノードは先頭のノードをリンクしている。片方向リストと同様、新たなノードを挿入する場合、既に参照を持っているノードの次の位置にのみ挿入できる。このため、片方向循環リストでは、最後尾のノードを指している参照を保持しておくことが多く、それによって、先頭位置に高速に挿入可能とするだけでなく、先頭ノードから最後尾のノードまでを順に辿ることも可能にしている。 [1]
双方向循環リスト
双方向循環リスト（doubly-circularly-linked list）では、各ノードは線形の双方向リストと同じように2つのリンクを持つが、先頭ノードの後方リンクは最後尾ノードを指し、最後尾ノードの前方リンクは先頭ノードを指す。双方向リストと同様、挿入も削除もその位置に隣接するノードへの参照が1つあれば、高速に行える。構造的には双方向循環リストには先頭も最後尾もないが、一般に外部のアクセスポインタを用意して、先頭または最後尾のノードを指しておくことが多い。そして、双方向リストでの番兵ノードのように順序を把握するのに使われる[1]。
番兵ノード
線形リストには「ダミーノード」または「番兵ノード; sentinel node」と呼ばれるものが、リストの先頭や最後尾に置かれることがある。番兵ノードにはデータは格納されない。その目的は、全てのノードのリンクが常にノードのデータ構造を指していることを保証して、いくつかの操作を高速化することである。LISPではそのような設計がされており、nil と呼ばれる特別な値は片方向リストの最後尾を示すと決められている。nil は CAR 操作でも CDR 操作でも nil を返すため、一部の操作を高速化できる。最後尾が nil でないリストは不適切（improper）である（不適切とは言っても使えないということではない）。
応用
連結リストは他のデータ構造の構成要素として使われる。例えば、スタック、キューなどである。
ノードのデータ部が別の連結リスト（へのポインタ）という構成も可能である。これを応用すると様々なデータ構造をリストで構成できる。これはLISPを起源とする方法であり、LISP では連結リストは主要なデータ構造とされ、今では関数型言語で一般に使われている。
連結リストを使って連想配列を実装することもあり、これを連想リスト（association list）と呼ぶ。このような連結リストの応用にはあまり利点がない。平衡2分探索木などのデータ構造の方が、ごく小さいデータ量であっても性能的に優れている。しかし、木構造のサブセットという範囲を超えて連結リストを動的に生成することもあり、より効率的にそのような構成のデータを扱うのに使われる。
トレードオフ
コンピュータプログラミングと設計におけるほとんどの選択と同様、あらゆる状況に適した方法は存在しない。連結リストというデータ構造も状況によってはうまく機能するが、別の状況には適さない。以下では、連結リスト構造に関するトレードオフについて説明する。一般に動的に変化するデータの集まりがあって、要素の追加・削除が頻繁に行われ、新たな要素を追加する位置が重要となる場合、連結リストが適しているといえる。
連結リストと配列
| 配列 | 連結リスト | |
|---|---|---|
| 検索 | O(1) | O(n) |
| 最後尾での挿入/削除 | O(1) | O(1) or O(n)[2] |
| 途中での挿入/削除（位置指定あり） | O(n) | O(1) |
| 永続性 | なし | 片方向で有り |
| 局所性 | 大 | 小 |
連結リストは配列と比較したとき、いくつかの利点を持つ。リストでは要素の挿入は無制限に可能であるが、配列はサイズが決まっているために限界があり、配列を大きくしようとしても、メモリのフラグメンテーションによって不可能なこともある。同様に、配列から要素の多くを削除すると領域の無駄となったり、サイズを小さくする必要が生じる。
複数のリストが尾部を共有することで、さらにメモリを節約できる場合もある。つまり、先頭が複数あって、末尾が1つになっている構造が可能である。これを使って、何らかのデータの古いバージョンと新しいバージョンを同時に保持することが可能であり、簡単な永続データ構造の例となっている。
一方、配列はランダムアクセス性に優れており、連結リストがシーケンシャルアクセスを得意とするのと対照的である。片方向リストは一方向にしか辿れない。従って、ヒープソートのようにインデックスによって高速に要素を参照する必要がある場合、連結リストは不向きである。シーケンシャルアクセスも多くのマシン上では、連結リストよりも配列の方が高速である。これは、キャッシュメモリの効果と参照の局所性によるものである。連結リストはキャッシュメモリからはほとんど何も恩恵を受けない。
連結リストの別の欠点は、参照のための余分な領域を必要とする点である。このため、キャラクタやブーリアン型のような小さなデータ要素を連結リストで操作するのは（1文字ごとにノードを割り当てて文字列操作を実現するなど）、速度の面でもメモリ消費の面でも無駄が多く、現実的でない。
これらの問題の一部を改善する連結リストの派生データ構造がいくつか存在する。Unrolled linked list は各ノードに複数の要素を格納するもので、キャッシュ性能を向上させ、参照時のメモリのオーバヘッドを低減させる。CDRコーディングも参照を参照すべき実データと置換することで同様の効果が得られる。
配列との比較で利点と欠点を明確にする好例として、ジョセファスの問題を解くプログラムの実装がある。ジョセファスの問題とは、人間が輪になって並んでいる状況で、そこから1人を選ぶというものである。ある人を開始点として、特定の方向に n 人を数えていく。n 番目の人に到達したら、その人を輪から外して、残りの人間で一回り小さい輪を作る。そして再び n 番目まで数えていく。これを1人だけが残るまで繰り返し、最後に残った人が選ばれた人ということになる。これを循環リストを使って表すのは直接的で分かり易いし、ノードの削除も簡単である。しかし、循環リストでは、現在のノードから n 番目のノードを見つけるには、リストを順に辿っていくしかない。配列であればインデックスの計算で即座に見つけられる。一方、配列では要素（ノード）の削除は容易ではなく、n 番目のノードを即座に見つけるという利点を生かすには、ノードを削除したときに残った要素を詰めてやる必要がある。
双方向と片方向
双方向リストはノード毎に要するメモリ量が多くなるし、基本的な操作にかかる手間が多くなる。しかし、どちらの方向にもシーケンシャルアクセス可能であるため、扱いやすくなることが多い。特に、あるノードの削除をする場合、そのノードのアドレスさえ分かっていれば、定数時間でそれが可能である。挿入の場合も、挿入する位置（そのノードの前に新たなノードを挿入する）が判っていれば、双方向リストでは定数時間で挿入が可能である。片方向リストでは、挿入・削除の際に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つのリストがそれぞれ長さ <math>n</math> である場合、連結にかかる時間は <math>O(n)</math> となる。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 Entry {
integer next; // 次のエントリの配列インデックス
integer prev; // 前のエントリ（双方向の場合）
string name;
real balance;
}
この構造体の配列を生成し、リストの先頭のインデックスを保持する整数変数を用意すれば、連結リストを構築できる。
integer listHead; Entry Records[1000];
要素間のリンクはリスト上の次（または前）の要素の配列インデックスを Next あるいは Prev フィールドに格納することでなされる。例えば、次のようになる。
| インデックス | Next | Prev | Name | Balance |
|---|---|---|---|---|
| 0 | 1 | 4 | Jones, John | 123.45 |
| 1 | -1 | 0 | Smith, Joseph | 234.56 |
| 2 (listHead) | 4 | -1 | Adams, Adam | 0.00 |
| 3 | Ignore, Ignatius | 999.99 | ||
| 4 | 0 | 2 | Another, Anita | 876.54 |
| 5 | ||||
| 6 | ||||
| 7 |
この例で、ListHead は 2 になっており、そこがリストの先頭ノードである。3番と5から7番のエントリはリスト上に含まれていない。これらのセルはリストに新たに追加することが可能である。ListFree という整数変数を用意してフリーリストを構成しておくと扱いやすくなる。全てのエントリが使われている場合、配列の大きさを拡張するか、一部要素を削除して空きを作らないと、新たな要素をリストに追加できなくなる。
次のコードは、リストを辿って、name と balance を表示するものである。
i := listHead;
while i >= 0 { // リスト上をループする
print i, Records[i].name, Records[i].balance // エントリの印字
i = Records[i].next;
}
この手法の利点は次の通りである。
- リンクとしてアドレスを使っていないので、リロケータブル（メモリ上でコピー可能）である。また、直接シリアライズしてディスクやネットワークに転送可能である。
- 小さいリストの場合、配列インデックスの方がポインタよりも小さくて済むことが多い。
- ノードがメモリ上に連続して存在するため、参照の局所性が向上する可能性がある。
- 素朴な動的メモリ確保でノード用にメモリを割り当てると無駄が生じる可能性があるが、この方式ではノード毎のオーバーヘッドはほとんどない。
- 事前に配列として確保されている範囲では、動的メモリ確保よりもノードの生成が高速化される。
ただし、この方式にはノード群のためのメモリ領域管理を独自に行わなければならないという欠点がある。このため、次のような問題が生じる。
- 実装が複雑になる。
- 全ノードを使い切ったとき、配列の拡張が困難か不可能な場合がある。汎用のメモリプールからノード用にメモリを確保するほうが容易である。
- 動的配列に要素を追加しようとすると、予期しないタイミングで定数時間ではなく線形時間（O(n)）がかかってしまう（平均すれば定数時間と言える）。
- 予想したよりもノード数の使用量が少ないと、メモリを無駄に確保することになる。
以上のような理由から、この手法は動的メモリ確保をサポートしていない言語で主に利用される。問題の多くは、配列生成時にリストの最大サイズが分かっている場合には問題ではなくなる。
言語サポート
LISPやScheme、Prologといったプログラミング言語は、片方向リストを組み込みで装備している。多くの関数型言語では、リストを構成するノードを「consセル」と呼ぶ。consセルには "car" 部分と "cdr" 部分があり、"car" 部はそのノードのデータへの参照、"cdr" 部は次のノードへの参照を格納している。consセルは他のデータ構造にも使われるが、主な用途はリストを構成することである。
抽象データ型やテンプレートをサポートする言語では、連結リストの抽象データ型やテンプレートを使って、連結リストを構築できる。
オブジェクト指向プログラミング言語では、次のようなクラスが連結リスト用に用意されている。
- C++（STL） - std::list<T>クラス（<list>）
- Java - java.util.テンプレート:Javadoc:SEクラス
- .NET - System.Collections.Generic.LinkedList<T>クラス
以下に、C言語での片方向リストの例を示す。
#include <stdio.h> /* for printf */
#include <stdlib.h> /* for malloc */
typedef struct ns {
int data;
struct ns *next;
} node;
node *list_add(node **p, int i) { /* add head */
node *n = malloc(sizeof(node)); /* you normally don't cast a return value for malloc */
n->next = *p;
*p = n;
n->data = i;
return n;
}
node *list_add_tail(node **p, int i) { /* add tail */
node *n;
node *ptr;
if (*p == NULL) {
n = list_add(p, i);
} else {
ptr = *p;
while (ptr->next != NULL) {
ptr = ptr->next;
}
n = malloc(sizeof(node));
n->next = NULL;
n->data = i;
ptr->next = n;
}
return n;
}
void list_remove(node **p) { /* remove head */
if (*p != NULL) {
node *n = *p;
*p = (*p)->next;
free(n);
}
}
void list_remove_tail(node **p) { /* remove tail */
if (*p != NULL) {
if( (*p)->next == NULL ) {
list_remove(p);
} else {
node *ptr = *p;
node *pre;
while (ptr->next != NULL) {
pre = ptr;
ptr = ptr->next;
}
pre->next = NULL;
free(ptr);
}
}
}
void list_remove_all(node **p) { /* remove all node */
while (*p != NULL) {
list_remove(p);
}
}
node **list_search(node **n, int i) {
while (*n != NULL) {
if ((*n)->data == i) {
return n;
}
n = &(*n)->next;
}
return NULL;
}
void list_print(node *n) {
if (n == NULL) {
printf("list is empty\n");
}
while (n != NULL) {
printf("print %p %p %d\n", n, n->next, n->data);
n = n->next;
}
}
int main(void) {
node *n = NULL;
list_add(&n, 0); /* list: 0 */
list_add(&n, 1); /* list: 1 0 */
list_add(&n, 2); /* list: 2 1 0 */
list_add(&n, 3); /* list: 3 2 1 0 */
list_add(&n, 4); /* list: 4 3 2 1 0 */
list_print(n);
list_remove(&n); /* remove first (4) */
list_remove(&n->next); /* remove new second (2) */
list_remove(list_search(&n, 1)); /* remove cell containing 1 (first) */
list_remove(&n->next); /* remove second to last node (0) */
list_remove(&n); /* remove last (3) */
list_print(n);
return 0;
}内部収納と外部収納
連結リストを構築する際、データをノードそのものに格納するか、別のデータ構造への参照のみを格納するかという選択を迫られる。前者を「内部収納; internal storage」、後者を「外部収納; external storage」と呼ぶ。内部収納の方がデータアクセスが効率化され、全体としてメモリ使用量が低減され、参照の局所性が向上し、リストに関するメモリ管理も簡素化される（データはノードと共に確保・解放される）。
一方、外部収納はより汎用的だという利点がある。データの内容に依存しないデータ構造とリスト操作コードを形成可能である。また、複数のノードで同じデータを共有することも容易に実現できる。内部収納の場合も、通常のリンクとは別に、同じ内容のデータを保持するノードを連結するフィールドを持てば、同様のことが可能になるが、リスト操作にあたってそれも考慮する必要が出てくる。
一般に、データ構造を複数の連結リストに属させる必要がある場合、外部収納が最善の手法である。データ構造うが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 は、各ノードに配列が置かれている形式の連結リストである。主に参照の局所性を高め、性能を向上させる目的で使われる。
- ハッシュテーブルは、ハッシュ値が衝突しているデータを保持する際に連結リストの構造を使うことがある。
特許問題
- Linked List Patented in 2006 (Slashdot)
- リンクトリストが2006年に特許承認 (スラッシュドット ジャパン)
脚注
参考文献
- 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. [1] HTML DVI PDF PostScript
- 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. PDF
- 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日）. Linux Kernel Linked List Explained.
関連項目
外部リンク
- Description Dictionary of Algorithms and Data Structures より
- スタンフォード大学 計算機科学科:
- SimCList, an open source C library for linked lists
- SGLib, an collection of algorithms for operating on linked lists (and other containers)
- Generic List Container Type for ANSI C by Jeff Hay
- shared singly linked list implementations
- Linked Lists Tutorial with diagrams and Java code example
- 各ノードが複数の線形リストに同時に属するという技法に関する特許 （この技法はこの特許が成立する何十年も前から広く使われていた）
- 各ノードが同時に複数の線形リストに属する技法（上記特許に抵触しない方式）
- ↑ 1.0 1.1 テンプレート:Citation
- ↑ 最後尾へのリンクを保持していれば O(1) だが、最後尾を探すために先頭から辿る必要がある場合は O(n)
