連結リスト

最近の主な更新 2006-05-28 - 第二版 2001-xx-xx - 初版 はじめに 配列はプログラミングの際に用いられるデータ構造として最も基本的なもので ある．配列が表現しているのは，順序付けされた n（>= 0）個の節点の並 びである．各節点には特定の型のデータが保持される．このような構造は，よ り抽象的な用語で線形リスト（もしくは単にリスト）と呼ばれる． 配列は，節点の番号（配列の添字）を指定することで，任意の節点に一定時間 （O(1)）でアクセスできるという長所を持つ．一方，リストへの節点の挿入， 削除は得意ではない．例えば，リストの先頭に新しい節点を挿入しようとする と，配列の各要素を一つずつ後ろにずらすという作業が必要になるため，計算 量としては O(n) となる．削除についても同様で，ある要素を削除すると，そ の要素から後ろにある要素全てを一つずつ前にずらす必要がある