リストとは
リスト（連結リスト：Linked List）とは、データそのものと「次のデータがメモリ上のどこにあるかを示す情報（ポインタ）」をセットにした要素（ノード）を、鎖のようにつなぎ合わせて複数のデータを管理するデータ構造です。配列と違い、データがメモリ上でバラバラの位置にあっても問題なく、データの追加や削除をする際に周りのデータをズラす必要がないため、途中の挿入・削除が非常に素早く行える利点があります。
具体例
列車の車両連結の仕組みに似ています。車両（ノード）が連結器（ポインタ）で繋がっており、3両目と4両目の間に新しい車両を割り込ませる場合、前後の連結器の向きを掛け替えるだけで完了します。
// 連結リストのノード構造の簡易イメージ
class Node {
constructor(data) {
this.data = data; // データ本体
this.next = null; // 次のノードへの参照ポインタ
}
}もう少し詳しく
リスト（連結リスト/線形リスト：Linked List）は、データ本体と、次の要素がメモリ上のどこにあるかを示す「ポインタ（参照情報）」を格納した構造体（ノード）を鎖のように繋いでいくデータ構造です。配列のようにメモリ上で連続した場所に並んでいる必要がなく、メモリの空いている場所（バラバラの住所）にノードを動的に作成してリンクで繋ぐため、プログラムの実行中に要素数を制限なく増減させることができます。リストの最大の特徴は、データの挿入・削除が容易な点です。例えば、要素Aと要素Bの間に新しく要素Cを割り込ませる場合、AのポインタをCに向け、CのポインタをBに向けるという、わずか数箇所のポインタ書き換え（O(1)の処理）だけで完了し、データを移動させる必要がありません。一方で、特定の要素にアクセスするためには、先頭ノード（ヘッド）からポインタを一つずつ順に辿っていく（シーケンシャルアクセス）必要があるため、N番目の要素にアクセスするのにはO(N)の時間がかかり、配列のような高速なランダムアクセスはできません。
試験でのポイント
試験では、連結リストの構造図（データ部とポインタ部）を見ながら、要素の「挿入」や「削除」の処理におけるポインタの書き換え順序を正しく選ばせる問題が定番です。ポインタを書き換える順序を誤ると、後続のリストへの参照が失われてしまうため、順序のロジックが問われます。また、片方向だけに辿れる「単方向リスト」、双方向に辿れる「双方向リスト」、末尾と先頭を繋いだ「循環リスト」といったバリエーションの特性の違いもポイントです。
関連する用語
ポインタ（メモリ上のアドレスを指し示す変数）、単方向リスト（一方通行のリンクを持つ連結リスト）、双方向リスト（前後のノードへのリンクを持つ連結リスト）。