リスト（連結リスト/線形リスト：Linked List）は、データ本体と、次の要素がメモリ上のどこにあるかを示す「ポインタ（参照情報）」を格納した構造体（ノード）を鎖のように繋いでいくデータ構造です。配列のようにメモリ上で連続した場所に並んでいる必要がなく、メモリの空いている場所（バラバラの住所）にノードを動的に作成してリンクで繋ぐため、プログラムの実行中に要素数を制限なく増減させることができます。リストの最大の特徴は、データの挿入・削除が容易な点です。例えば、要素Aと要素Bの間に新しく要素Cを割り込ませる場合、AのポインタをCに向け、CのポインタをBに向けるという、わずか数箇所のポインタ書き換え（O(1)の処理）だけで完了し、データを移動させる必要がありません。一方で、特定の要素にアクセスするためには、先頭ノード（ヘッド）からポインタを一つずつ順に辿っていく（シーケンシャルアクセス）必要があるため、N番目の要素にアクセスするのにはO(N)の時間がかかり、配列のような高速なランダムアクセスはできません。