連結リストのソースを表示

{{読み仮名|'''連結リスト'''|れんけつリスト|{{lang-en|Linked list}}}}は、最も基本的な[[データ構造]]の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" と題して掲載された。

1960年、[[ジョン・マッカーシー]]等が MIT で開発した[[LISP]]は "list processor" の略であり、"Communications of the ACM" にその設計に関する論文 "Recursive Functions of Symbolic Expressions and Their Computation by Machine, Part I" が掲載された<ref name="lisp-recursive">{{Cite web |title=RECURSIVE FUNCTIONS OF SYMBOLIC EXPRESSIONS AND THEIR COMPUTATION BY MACHINE (Part I) (12-May-1998) |author= |work=www-formal.stanford.edu |date= |access-date=7 April 2024 |url= https://www-formal.stanford.edu/jmc/recursive.html}}</ref>。LISP の主要なデータ構造の一つとして片方向リストによる[[木構造 (データ構造)|木構造]]が採用されている<ref name="LISP-I-MANUAL">{{Cite web |title=McCarthy et al. LISP I Programmer's Manual. — Software Preservation Group |author= |work=softwarepreservation.org |date= |access-date=7 April 2024 |url= https://www.softwarepreservation.org/projects/LISP/book/LISP%20I%20Programmers%20Manual.pdf/view}}</ref>。

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]]を開発した。[[ディレクトリ]]が[[ファイル (コンピュータ)|ファイル]]の第一セクターを指し、その後のファイルの中身も線形リストのポインタを辿ることで得られるようになっていた。FLEX から派生したオペレーティングシステムとして Smoke Signal Broadcasting社が開発したものがあるが、こちらは双方向リストを同じ用途に使っていた。

[[IBM]]社が [[System/360]]や[[System/370]]向けに開発した[[タイムシェアリングシステム|TSS]]でも、[[ファイルシステム]]に双方向リストを使っていた。そのディレクトリ構造は [[UNIX]] のものと似ており、ディレクトリはファイルや他のディレクトリを格納でき、任意の深さまで階層構造を作ることができた。システムがクラッシュしたとき、このファイルシステム構造の一部がディスクに書き戻されていない場合があり、これを修復するためのユーティリティ "flea" が開発された。これは双方リストの前方リンクと後方リンクの一貫性をチェックすることで問題を検出する。

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

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

<div class="center">[[ファイル:Singly-linked-list.svg]]<br /><span style="font-size:90%;">''3つの整数値を格納した片方向リスト''</span></div>

==== 双方向リスト ====
'''双方向リスト'''（doubly-linked list）は、より洗練された連結リスト。各ノードには2つのリンクがあり、1つが次のノード（前方リンク）、もう1つが後ろのノード（後方リンク）を指す。リストの先頭のノードには後ろのノードがないので、後方リンクにはヌル値を格納するか、空のリストを指す。リストの最後尾のノードには次のノードがないので、前方リンクにはヌル値を格納するか、空のリストを指す。

<div class="center">[[File:Doubly-linked-list.svg]]<br /><span style="font-size:90%;">''3つの整数値を格納した双方向リスト''</span></div>

低レベルの言語の中には、[[XOR連結リスト]]を使って双方向リストの2つのリンクを1つのワードで表せるようにしたものもあるが、この技法は一般には使われない。

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

リスト全体を指すポインタは、アクセスポインタと呼ばれることがある。

<div class="center">[[File:Circularly-linked-list.svg]]<br /><span style="font-size:90%;">''3つの整数値を格納した循環リスト''</span></div>

==== 片方向循環リスト ====
'''片方向循環リスト'''（singly-circularly-linked list）では、各ノードは線形の片方向リストと同じように1つのリンクを持つが、最後尾のノードは先頭のノードをリンクしている。片方向リストと同様、新たなノードを挿入する場合、既に参照を持っているノードの次の位置にのみ挿入できる。このため、片方向循環リストでは、最後尾のノードを指している参照を保持しておくことが多く、それによって、先頭位置に高速に挿入可能とするだけでなく、先頭ノードから最後尾のノードまでを順に辿ることも可能にしている。
<ref name="bruno99">{{Citation | title=Data Structures and Algorithms with Object-Oriented Design Patterns in Java | url=http://www.brpreiss.com/books/opus5/html/page97.html | first=Bruno R.  | last=Preiss | isbn=0471-34613-6 | publisher=Wiley | date=1999年 | page= page 97, 165 }} </ref>

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

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

== 応用 ==
連結リストは他のデータ構造の構成要素として使われる。例えば、[[スタック]]、[[キュー (コンピュータ)|キュー]]などである。

ノードのデータ部が別の連結リスト（へのポインタ）という構成も可能である。これを応用すると様々なデータ構造をリストで構成できる。これは[[LISP]]を起源とする方法であり、LISP では連結リストは主要なデータ構造とされ、今では[[関数型言語]]で一般に使われている。

連結リストを使って[[連想配列]]を実装することもあり、これを'''連想リスト'''（association list）と呼ぶ。このような連結リストの応用にはあまり利点がない。[[平衡2分探索木]]などのデータ構造の方が、ごく小さいデータ量であっても性能的に優れている。しかし、木構造のサブセットという範囲を超えて連結リストを動的に生成することもあり、より効率的にそのような構成のデータを扱うのに使われる。

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

=== 連結リストと配列 ===
{|style="float: right" class="wikitable"
!          !! 配列 !! 連結リスト
|-
| 検索 || O(1) || O(''n'')
|-
| 最後尾での挿入/削除 || O(1) || O(1) or O(''n'')<ref>最後尾へのリンクを保持していれば O(1) だが、最後尾を探すために先頭から辿る必要がある場合は O(n)</ref> 
|-
| 途中での挿入/削除（位置指定あり） || 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
  }

次のコードは片方向リスト上のあるノードの次に新たにノードを挿入する。あるノードの前にノードを挿入することはできない。その場合は挿入位置の前のノードを見つける必要がある。

[[File:CPT-LinkedLists-addingnode.svg|center]]

  '''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
  }

同様に、指定されたノードの次のノードを削除する関数と、リストの先頭のノードを削除する関数を示す。特定のノードを探して削除する場合、その前のノードを覚えておく必要がある。

[[File:CPT-LinkedLists-deletingnode.svg|center]]

  '''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 系言語では、リストの連結には <code>append</code> を使う。

片方向リストの操作は先頭ノードの扱いが特殊であるが、先頭にダミー要素を追加することでこれを排除できる。これによって、"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 フィールドに格納することでなされる。例えば、次のようになる。

{| class="wikitable"
!インデックス!!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|| || || ||
|}

この例で、<code>ListHead</code> は 2 になっており、そこがリストの先頭ノードである。3番と5から7番のエントリはリスト上に含まれていない。これらのセルはリストに新たに追加することが可能である。<code>ListFree</code> という整数変数を用意してフリーリストを構成しておくと扱いやすくなる。全てのエントリが使われている場合、配列の大きさを拡張するか、一部要素を削除して空きを作らないと、新たな要素をリストに追加できなくなる。

次のコードは、リストを辿って、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 (Lisp)|cons]]セル」と呼ぶ。consセルには [[CARとCDR|"car" 部分と "cdr" 部分]]があり、"car" 部はそのノードのデータへの参照、"cdr" 部は次のノードへの参照を格納している。consセルは他のデータ構造にも使われるが、主な用途はリストを構成することである。

[[抽象データ型]]やテンプレートをサポートする言語では、連結リストの抽象データ型やテンプレートを使って、連結リストを構築できる。

[[オブジェクト指向プログラミング]]言語では、次のようなクラスが連結リスト用に用意されている。

* [[C++]]（[[Standard Template Library|STL]]） - <tt>std::list<T></tt>クラス（<tt><list></tt>）
* [[Java]] - <tt>java.util.{{Javadoc:SE|java/util|LinkedList}}</tt>クラス
* [[.NET Framework|.NET]] - <tt>System.Collections.Generic.LinkedList<T></tt>クラス

以下に、[[C言語]]での片方向リストの例を示す。

<syntaxhighlight lang='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;
}
</syntaxhighlight>

== 内部収納と外部収納 ==
{{出典の明記|section=1|date=2019-04}}
<!-- コンピュータサイエンスの分野では、storage は通例「記憶域」と訳す。英語版Wikipediaからの直訳らしいが、そもそもの出典が不明。英語版の定義の時点で怪しい。 -->
連結リストを構築する際、データをノードそのものに格納するか、別のデータ構造への参照のみを格納するかという選択を迫られる。前者を「{{要出典範囲|date=2019-04|内部収納; internal storage}}」、後者を「{{要出典範囲|date=2019-04|外部収納; 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]] は、各ノードに配列が置かれている形式の連結リストである。主に[[参照の局所性]]を高め、性能を向上させる目的で使われる。
* [[ハッシュテーブル]]は、ハッシュ値が衝突しているデータを保持する際に連結リストの構造を使うことがある。

==特許問題==
* [http://yro.slashdot.org/article.pl?sid=07/03/19/112247  Linked List Patented in 2006] (Slashdot)
* [https://srad.jp/story/07/03/20/0942255/  リンクトリストが2006年に特許承認] (スラッシュドット ジャパン)
{{節スタブ}}

== 脚注 ==
{{Reflist}}

== 参考文献 ==
* Antonakos, James L. and Mansfield, Kenneth C., Jr. ''Practical Data Structures Using C/C++'' (1999). Prentice-Hall. ISBN 0-13-280843-9, pp. 165&ndash;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&ndash;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&ndash;213, 501&ndash;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''. <span style="font-size:90%;">[http://www-formal.stanford.edu/jmc/recursive.html] [http://www-formal.stanford.edu/jmc/recursive/recursive.html HTML] [http://www-formal.stanford.edu/jmc/recursive.dvi DVI] [http://www-formal.stanford.edu/jmc/recursive.pdf PDF] [http://www-formal.stanford.edu/jmc/recursive.ps PostScript]</span>
* [[ドナルド・クヌース|Donald Knuth]]. ''Fundamental Algorithms'', Third Edition. Addison-Wesley, 1997. ISBN 0-201-89683-4. Sections 2.2.3&ndash;2.2.5, pp.254&ndash;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&ndash;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''. <span style="font-size:90%;">[http://cslibrary.stanford.edu/103/LinkedListBasics.pdf PDF]</span>
* Sedgewick, Robert ''Algorithms in C'' (1998). Addison Wesley. ISBN 0-201-31452-5, pp. 90&ndash;109
* Shaffer, Clifford A. ''A Practical Introduction to Data Structures and Algorithm Analysis'' (1998). NJ: Prentice Hall. ISBN 0-13-660911-2, pp. 77&ndash;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日]]）. [http://isis.poly.edu/kulesh/stuff/src/klist/ Linux Kernel Linked List Explained].

== 関連項目 ==
* [[番兵]]
* [[データ構造]]
* [[グラフ理論]]

== 外部リンク ==
* [http://nist.gov/dads/HTML/linkedList.html Description] Dictionary of Algorithms and Data Structures より
* [[スタンフォード大学]] 計算機科学科: 
** [http://cslibrary.stanford.edu/103/ Introduction to Linked Lists]
** [http://cslibrary.stanford.edu/105/ Linked List Problems]
* [http://mij.oltrelinux.com/devel/simclist/ SimCList, an open source C library for linked lists]
* [https://sglib.sourceforge.net/ SGLib, an collection of algorithms for operating on linked lists (and other containers)]
* [http://home.earthlink.net/~jrhay/src/wwwsrc/src.html Generic List Container Type for ANSI C] by Jeff Hay
* [http://www.cs.chalmers.se/~noble/manual/sllist.html shared singly linked list implementations]
* [http://www.mycsresource.net/articles/programming/data_structures/linkedlists Linked Lists Tutorial with diagrams and Java code example]
* [https://www.google.com/patents?vid=USPAT7028023 各ノードが複数の線形リストに同時に属するという技法に関する特許] （この技法はこの特許が成立する何十年も前から広く使われていた）

{{データ構造}}

{{Normdaten}}
{{DEFAULTSORT:れんけつりすと}}
[[Category:データ構造]]