は、最も基本的なデータ構造の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" が掲載された。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値を格納するか、空のリストを指す。
ファイル:Singly-linked-list.svg3つの整数値を格納した片方向リスト
双方向リスト 双方向リスト（doubly-linked list）は、より洗練された連結リスト。各ノードには2つのリンクがあり、1つが次のノード（前方リンク）、もう1つが後ろのノード（後方リンク）を指す。リストの先頭のノードには後ろのノードがないので、後方リンクにはヌル値を格納するか、空のリストを指す。リストの最後尾のノードには次のノードがないので、前方リンクにはヌル値を格納するか、空のリストを指す。
3つの整数値を格納した双方向リスト
低レベルの言語の中には、XOR連結リストを使って双方向リストの2つのリンクを1つのワードで表せるようにしたものもあるが、この技法は一般には使われない。
循環リスト 循環リスト（circularly-linked list）では、先頭と最後尾のノードを相互に連結する。循環リストには片方向のものも双方向のものもある。循環リストを辿る場合、任意のノードから出発して、好きな方向にたどっていき、最初のノードに戻ってくるまで続ける。つまり、循環リストは先頭や最後尾といったものが存在しないリストと考えることもできる。循環リストはデータ格納用バッファの管理によく使われ、1つのノードを使っているスレッド（やプロセス）が他のノードを全て参照したい場合などに便利である。
リスト全体を指すポインタは、アクセスポインタと呼ばれることがある。
3つの整数値を格納した循環リスト
片方向循環リスト 片方向循環リスト（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分探索木などのデータ構造の方が、ごく小さいデータ量であっても性能的に優れている。しかし、木構造のサブセットという範囲を超えて連結リストを動的に生成することもあり、より効率的にそのような構成のデータを扱うのに使われる。
トレードオフ コンピュータプログラミングと設計におけるほとんどの選択と同様、あらゆる状況に適した方法は存在しない。連結リストというデータ構造も状況によってはうまく機能するが、別の状況には適さない。以下では、連結リスト構造に関するトレードオフについて説明する。一般に動的に変化するデータの集まりがあって、要素の追加・削除が頻繁に行われ、新たな要素を追加する位置が重要となる場合、連結リストが適しているといえる。
連結リストと配列 配列 連結リスト 検索 O(1) O(n) 最後尾での挿入/削除 O(1) O(1) or O(n)最後尾へのリンクを保持していれば O(1) だが、最後尾を探すために先頭から辿る必要がある場合は O(n) 途中での挿入/削除（位置指定あり） 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)" で実現可能である。