先頭へ戻る

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

Programming Place Plus トップページ -- 用語集

先頭へ戻る

名称

解説

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

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

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

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

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

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

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

連結リストの考え方や実装方法を、アルゴリズムとデータ構造編【データ構造】第3章アルゴリズムとデータ構造編【データ構造】第4章で解説しています。

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

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

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

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

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


参考リンク

更新履歴


用語集のトップページへ

Programming Place Plus のトップページへ



はてなブックマーク に保存 Pocket に保存 Facebook でシェア
Twitter でツイート Twitter をフォロー LINE で送る
rss1.0 取得ボタン RSS 管理者情報 プライバシーポリシー