4 リスト

4.1 原理

リストは前後のデータのある位置をメモリーに入れることにより，データの列(ここでは 数列)を構成する．最初のデータの位置を元に，それから順にたどりすべてのデータをつ なぎデータ列(数列)を構成する．この様子を図1に示す．

図 1: リスト

このようにすると，ここのデータは順にアクセス(シーケンシャルアクセス)することにな り，その速度は一般に遅い．一方，データの削除と挿入は，データの位置を記憶するポイ ンターを変更するだけなので，高速になる．

4.2 プログラム

教科書のList 3-3(p.75-77)では，リスト10に示す構造体を用いてリストを 作っている．

• *prevが前のノードを示すポインターである．
• *nextが次のノードを示すポインターである．
• *dataがこのノードのデータである．

リスト10 リストを表 す構造体(転載について)

   1 typedef struct tagListNode
   2 {
   3     struct tagListNode *prev;    /* 前の要素へのポインタ */
   4     struct tagListNode *next;    /* 次の要素へのポインタ */
   5     int data;   /* この要素がもっているデータ */
   6 } ListNode;

4.3 リストと配列の違い

配列もリストも，複数のデータの値と順序を記憶するデータ構造である．しかし，その使 い方はかなり異なり，その性質をよく理解しなくてはならない．

配列は目的のデータにランダムアクセスが可能で，目的のデータの値を得たり，データの 値の変更が高速にできる．添え字を指定するだけで，それらが可能である．しかし，デー タの削除と挿入には計算回数が多くなる．たとえば，10番目のデータを削除するとなると， 11番目を10番目に移動，12番目を11番目に移動，13番目を12番目に移動$\cdots$ とデータ を順次移動させる必要がある．

一方，リストは目的のデータにアクセスするためには，シーケンシャルアクセス ⁶を行う． そのため，データへのアクセス回数が多くなり配列より低速になる．しかし，データの削 除と挿入は簡単で，その前後へのノードのポインターの値を変更するだけである．したがっ て，挿入と削除は高速になる．

表 2: 配列とリストとの違い

	配列	リスト
データへのアクセス	添え字によるランダムアクセス可能	リストを順にたどる
アクセスのための計算量	$O(1)$	$O(N)$
データの挿入/削除	計算コスト大 $O(N)$	計算コスト小 $O(1)$
メモリーのコスト	小	配列より大

[転載について]
このペー ジ中のリスト10のプログラムは，教科書として使用している以下の書籍

書名	プログラミングの宝箱　アルゴリズムとデータ構造 ISBN4-7973-2419-8
著作者	紀平拓男・春日伸弥
出版社	ソフトバンク　パブリッシング株式会社

から転載しました．この転載に関しては，著者と版元に許諾を得ています．

ホームページ: Yamamoto's laboratory
著者: 山本昌志