3 リストと配列

リストと配列の違いについて，比較を行う．

3.1 メモリーへの格納の仕方

順序づけられたデータのことをリストと言う．このリストは，データ構造のリストとは異 なるので注意すること．一般には，各々のデータはカンマで区切り表現する．この順序づ けられたデータの例としては，数列がある．

$$2,\,63,\,43,\,12,\,24,\,77,\,5,\,23,\,18,\,37,\,81,\,57,\,29,\,62,\,49,\,30$$

数列に限らず，成績表等もリストの例である．

$$( ,83),\,( ,73),\,( ,49),\,( ,55),\,( ,95),\,( ,35)$$

順序づけられたデータ--リスト--をコンピュータープログラムで取り扱う場合，配列あ るいはリストと呼ばれるデータ構造が使われる²．例えば，数列

$$63,\,27,\,82,\,79,\,12$$

をこれらのデータ構造で表現する．配列のモデルとメモリーへの格納の様子は，図 1のようになる．その特徴は，次の通りである． -4pt

• 配列の添字を使って，順序を表している．
• メモリーの連続した領域に，データの順序通りに格納される．

図 1: 配列のモデルとメモリーの様子．

それに対して，リストは図2のように表現することができる．その特徴は， 次の通りである． -4pt

• ポインターを使って，順序を表している．
• メモリーの連続した領域にデータを格納する必要がない．また，データの順序通 りに値を格納する必要もない．

図 2: リストのモデルとメモリーの様子．

3.2 データの挿入

配列とリストにデータを挿入する場合を考える．先ほど示した数列の63の次に99を挿入す ることを考える．

配列の場合，図3のようにしてデータを挿入する．後ろの方からひ とつずつ，右側に値をコピーする．そして，データを挿入する場所にあった値をのコピー が終われば，そこに挿入する値をコピーする．挿入する場所にもよるが，データ数に比例 してコピーの手間は増える．データ数を$N$とするとコピーの回数--コンピューターの処 理回数--は，$N/2$程度である．もちろん，コピー回数は挿入する場所にも依存するが， 平均して$N/2$となる．これを$O(N)$と表現する．「オーダー$N$」と読む．$N$に比例し て処理の回数が増える-- ということを表している．

図 3: 配列のデータの挿入の様子．

それに対して，リストの場合は図4のようにしてデータを挿入する． データ63のポインターを99に接続し，データ99のポインターを27に接続する．この方法だ と，データがいくらあっても処理の回数は同じである．$O(1)$である．配列に比べて，処 理の回数は少なく，コンピューターで高速の処理ができる．データ数が多くなるとその差 は顕著になる．

配列とリストではデータを挿入する場合，処理の回数が決定的に異なる．リストの方が処 理の回数が少ない．処理の回数が異なるのは，データのメモリーへの格納の仕方による． 配列は頑固に，データと同じ並びで連続した領域に，値を格納する．一方，リストはメモ リーに適当に格納して，順序を表すポインターを使う．

図 4: リストのデータの挿入の様子．

3.3 データの削除

次に，先ほど99を挿入した数列

$$63,\,99,\,27,\,82,\,79,\,12$$

から，99を削除することを考える．

配列の場合，図5に示した方法で，データを削除する．挿入とは逆に， 前の方から順番にコピーを繰り返す．最後のデータ--図5の最後の 12--は意味のないデータとなる．このような方法では，データの数$N$とすると平均して $N/2$回の処理が必要である．したがって，$O(N)$となる．

図 5: 配列のデータの削除の様子．

リストの場合，図6に示した方法で，データを削除する．データ63のポ インターをデータ27に接続して，データ99を削除する．データ数とは関係なく処理の回数 は決まっており，オーダーは$O(1)$となる．配列よりも高速な処理ができ，データ数が多 くなればその差は顕著になる．

図 6: リストのデータの削除の様子．

3.4 データへのアクセス

次に，データのアクセスを考える．図1や2のように，配列 やリストを用いて，数列

$$63,\,27,\,82,\,79,\,12$$

がメモリーに格納されているとする．これの79というデータにアクセスするにはどうする か?

配列の場合，a[3]とすれば79のデータにアクセスすることができる．それぞれのデー タは配列名と添字により，アクセスできる．これは，個々のデータに名前が付いているよ うなものである．コンピューターはなんの迷いも無く目的のメモリーアドレスが分かる． これはデータの順序通りにメモリーにすき間無く値が格納されているから，可能なのであ る．データへアクセスする場合の処理のオーダーは$O(1)$となる．次の述べるリストより も格段に高速である．

リストの場合，目的のデータへのアクセスは手間がかかる．データのある場所が分かるの は先頭のデータのみである．これは後で述べる特別な方法で先頭のデータのみ分かるよう にしている．先頭のデータ63の次のデータ $\rightarrow$27の次のデータ $\rightarrow$82 の次のデータ $\rightarrow$79--というように先頭からたぐりよせなくてはならない．こ のように先頭からたぐり寄せなくてはならないのは，それぞれのデータに名前が無いから である．したがって，$N$個のデータがある場合，処理の平均的な回数は$N/2$となる． $O(N)$である．配列よりも処理の回数が増える．

3.5 リストと配列の違い

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

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

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

また，データの個数の柔軟性はリストの方が高い．配列の場合，要素の数はコンパイル時 に予め指定する必要がある．連続したメモリー領域を確保するためである．配列の場合， データ数が予め分からない場合は，十分大きなメモリー領域を確保することになる．その ため，メモリーを無駄遣いすることがある．それに対して，リストはデータの個数は後で 追加/削除できる．

これらの違いをまとめると，表2のようになる．一般的には， データの追加/削除が多い場合にはリスト，データのアクセスが多い場合には配列を使う．

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

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

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