連結リスト【linked list】リンクリスト

概要

連結リスト（linked list）とは、基本的なデータ構造の一つで、複数のデータを格納することができ、各データが一つ前あるいは後(もしくはその両方)のデータへの参照情報(リンク、ポインタ)を持っている構造のこと。

同種の要素を複数格納できる「コンテナ」（container）あるいは「コレクション」（collection）と呼ばれるデータ構造の一種である。各要素はデータ自体の他に自分の隣の要素を指し示す所在情報（リンク）を持っている。これをたどることで、各要素に順番にアクセスすることができる。

前あるいは後ろの要素は一つだけ持つことができ、途中で枝分かれはしない。先頭から末尾まで数珠繋ぎに要素を連結したものを「線形リスト」（linear linked list）、すべての要素が円環状に連結されていて先頭や末尾が存在しないものを「循環リスト」（circular linked list）という。

各要素が自分の次（後ろ）の要素へのリンクのみを持っているようなものを「単方向リスト」（singly linked list）あるいは「片方向リスト」と呼び、前から後ろへ一方向にしかたどることができない。一方、自分の一つ前と一つ後の両方へのリンクを持っているようなものを「双方向リスト」（doubly linked list）と呼び、前後に自由にたどることができる。

LISPなど関数型言語の多くは言語仕様として最初から用意されている組み込みデータ型の一つに連結リストが含まれている。手続き型言語ではデータ型としては用意されていないことが多いが、オブジェクト指向のクラスの仕組みを用いて実装し、標準クラスライブラリとして提供している言語もある（Javaや.NET言語など）。