※「セキュリティ保護のため...」というメッセージが出る方・日本語が入力できない方へ
■リスト(連結構造)■

リスト(list)というのは、データを「論理的に」並べたものをいう。ここで実際の物理的な順序は問わない。むしろ物理的な順序とは関係なく、そのリストの途中にデータを追加したり削除したりすることが高速にできるようなデータ構造を持つものを言う。

一般にはリストは「いもづる式」のポインタによって管理されている。下記の２つのリストは論理的におなじものである。

ａ．　start=1 　　　　　　　　　　 　　　　　(data)　　　(pointer) 　 　　1 　ＣＡＲＯＬＬＡ　　 2　　　 　　2 　ＰＲＩＵＳ　　　　 3　　　 　　3 　ＣＲＯＷＮ　　　　 4　　　 　　4 　ＧＯＬＦ　　　　　 5　　　 　　5 　ＳＫＹＬＩＮＥ　　 6　　　 　　6 　ＭＡＲＫ２　　　　 7　　　 　　7 　ＤＥＭＩＯ

ｂ．　start=3 　　　　　(data)　　　(pointer) 　　1 　ＣＲＯＷＮ　　　　 2　　 　　2 　ＧＯＬＦ　　　　　 4　　 　　3 　ＣＡＲＯＬＬＡ　　 6　　 　　4 　ＳＫＹＬＩＮＥ　　 7　　 　　5 　ＤＥＭＩＯ　　　　　　　 　　6 　ＰＲＩＵＳ　　　　 1　　 　　7 　ＭＡＲＫ２　　　　 5

リストはむろんCOBOLやFORTRANなどでも自分でポインタを管理することにより実現できるが、C++, Lisp, Prologue, Perl などでは処理系でサポートしてくれるため、楽である。

リストの操作

リストを管理するためには一般に下記のような処理は必須である。

• 個数を返す。（固定長の配列はありえても固定長のリストはありえない）
• 後ろに追加する／前に追加する／途中に追加する
• 後ろから削除する／先頭を削除する／途中を削除する
• リストの合成／部分リストの作成／リストの分割
• リスト内の検索／一括検索／置換／カウント
• リストを逆順にする

リストの意義

リストの処理というのは、このあと述べるトゥリー、待ち行列、ラウンドロビンなどを処理するための技術の基礎であり、この手のいわゆる基本プログラミングを覚えたい人にとっては、まずきっちりと身につけておかなければならない技術である。