連結リスト
出典: フリー百科事典『ウィキペディア（Wikipedia）』 (2024/04/07 16:50 UTC 版)
応用
連結リストは他のデータ構造の構成要素として使われる。例えば、スタック、キューなどである。
ノードのデータ部が別の連結リスト（へのポインタ）という構成も可能である。これを応用すると様々なデータ構造をリストで構成できる。これはLISPを起源とする方法であり、LISP では連結リストは主要なデータ構造とされ、今では関数型言語で一般に使われている。
連結リストを使って連想配列を実装することもあり、これを連想リスト（association list）と呼ぶ。このような連結リストの応用にはあまり利点がない。平衡2分探索木などのデータ構造の方が、ごく小さいデータ量であっても性能的に優れている。しかし、木構造のサブセットという範囲を超えて連結リストを動的に生成することもあり、より効率的にそのような構成のデータを扱うのに使われる。
トレードオフ
コンピュータプログラミングと設計におけるほとんどの選択と同様、あらゆる状況に適した方法は存在しない。連結リストというデータ構造も状況によってはうまく機能するが、別の状況には適さない。以下では、連結リスト構造に関するトレードオフについて説明する。一般に動的に変化するデータの集まりがあって、要素の追加・削除が頻繁に行われ、新たな要素を追加する位置が重要となる場合、連結リストが適しているといえる。
連結リストと配列
| 配列 | 連結リスト | |
|---|---|---|
| 検索 | O(1) | O(n) |
| 最後尾での挿入/削除 | O(1) | O(1) or O(n)[4] |
| 途中での挿入/削除（位置指定あり） | 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つのリストがそれぞれ長さ である場合、連結にかかる時間は となる。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)" で実現可能である。
- ^ “RECURSIVE FUNCTIONS OF SYMBOLIC EXPRESSIONS AND THEIR COMPUTATION BY MACHINE (Part I) (12-May-1998)”. www-formal.stanford.edu. 2024年4月7日閲覧。
- ^ “McCarthy et al. LISP I Programmer's Manual. — Software Preservation Group”. softwarepreservation.org. 2024年4月7日閲覧。
- ^ a b Preiss, Bruno R. (1999年), Data Structures and Algorithms with Object-Oriented Design Patterns in Java, Wiley, p. page 97, 165, ISBN 0471-34613-6
- ^ 最後尾へのリンクを保持していれば O(1) だが、最後尾を探すために先頭から辿る必要がある場合は O(n)
- 連結リストのページへのリンク
