連結リスト（れんけつリスト、（英語: 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 が掲載された[1]。LISP の主要なデータ構造の一つとして片方向リストによる木構造が採用されている[2]。

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つのリンクを持つが、最後尾のノードは先頭のノードをリンクしている。片方向リストと同様、新たなノードを挿入する場合、既に参照を持っているノードの次の位置にのみ挿入できる。このため、片方向循環リストでは、最後尾のノードを指している参照を保持しておくことが多く、それによって、先頭位置に高速に挿入可能とするだけでなく、先頭ノードから最後尾のノードまでを順に辿ることも可能にしている。[3]
双方向循環リスト

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

線形リストには「ダミーノード」または「番兵ノード; 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)[4]
途中での挿入/削除（位置指定あり）O(n)O(1)
永続性なし片方向で有り