連結リスト | Programming Place Plus　用語集

名称

各データが、その後続のデータ（と場合によっては手前のデータ）への参照情報（そのデータを辿るために必要な情報）をもつデータ構造です。

連結リストに含まれる各データは、要素などと呼ばれます。

後続の要素への参照情報のみをもつ場合は単方向リスト、前後の要素への参照情報をもつ場合は双方向リストとも呼ばれます。

また、先頭にあたる要素と、末尾にあたる要素が存在する連結リストは、線形リストとも呼ばれます。一方、先頭と末尾の概念がなく、要素が円環状に接続されている連結リストは、循環リストとも呼ばれます。

参照情報は、Ｃ言語のポインタのような機能を使えば、前後の要素を指し示すようにして表現できます。Ｃ言語では、連結リストの各要素を次のような構造体で表現します。

struct Node {
     int  data;          // データ本体（型はデータの種類に応じて変更する）
     struct Node* next;  // 次の要素への参照情報
     struct Node* prev;  // 前の要素への参照情報
};

このコードは、前後の要素への参照情報を持っているので、双方向リストを表現しています。単方向リストでは prev を取り除きます。

C++ の標準ライブラリには、双方向リストを実装した std::list（C++編【標準ライブラリ】第６章）、単方向リストを実装した std::forward_list があります。

配列と違って、要素数を固定的にする必要性がない長所があります。新たな要素には、新たにメモリを割り当てて、連結リストにつなげられます。

また、要素を挿入したり、要素を削除したりする処理の効率が良いことも長所として挙げられます。これは配列とちがって、ほかの要素の位置をずらす処理が不要で、前後の要素の参照情報を更新するだけ済むためです。

ただし、挿入する位置や、削除する要素の位置を探し出す部分で効率が悪い可能性があります。これは、連結リストではランダムアクセスができず、参照情報を使って先頭から順に辿っていく（シーケンシャルアクセス）必要があるからです。

また、配列と違い、（一般的によくある使い方では）メモリ上に要素が連続的に並ばないため、キャッシュヒットの確率が低いことを欠点とされることがあります。