第五回-02 : リストの概念

本ページでは「リスト」(双方向リスト、リンクリストなどとも呼ばれる) を詳しく解説する。

配列とその問題点

まず、複数のデータを格納するデータ構造を考えよう。
最初に学んだのは配列である。例えば 10 個の要素をもつ int 型の配列は以下のように定義される。 

int x[10];


この例では組み込み型の int を例にしたが、もちろんクラスの配列も同様に定義できるのであった。

このような配列の問題点は、「配列の要素数がコンパイル時に確定してないなければならない」ことである。

コンパイル後 (すなわち、プログラム利用時) に配列のサイズを指定したいときは、
第四回の演習問題１で取り扱ったように ポインタと new 演算子を用いるのであった。 

int n;
int *x;

//  なんらかの方法で n を決める

x = new int[n]; // メモリの動的確保

//  x[n] を配列のように利用できる

delete[] x;  // 利用した領域の開放


このように new 演算子を用いて確保したメモリ領域は、やはり配列と同様に利用できる。

さて、第二回演習で stack を、 第四回演習で queue を取り扱ったが、
そのいずれも本質的には上記の「配列」または「new で動的に確保したメモリ」 を用いて実現されていたことに注意しよう。

しかし、「配列」および「new で動的に確保したメモリ」には以下のような問題がある。 これらを図で説明したのが以下である。



(1) は、配列 x[10] を配列 x[12] に拡張しようとしているが、これはできない。

(2) は配列 x[5] の 3 番目の要素 x[2] に値「6」を挿入しようとしている。 これは不可能ではないが、以下の問題がある。 以上の問題を解決するデータ構造が以下で取り扱う「リスト」である。

リスト～その概念

リストは、以下の図の様に node が双方向にポインタで接続されているような構造 をもつ。



node それ自体クラスであるが、int 型を格納するリストを作りたいのであれば、 node のメンバに int 型の変数をもたせてやれば良い。

上図中の矢印は全てポインタと考えれば良い。
すなわち、node クラスのオブジェクトは左の node と右の node を指すポインタ (たとえば *left と *right) を、
そして list クラスは先頭の node を指すポインタ *root と末尾の node を指すポインタ *last を持つ。

このとき、リストの末尾に要素を加えるには、以下の模式図に示すような手続きに従えば良い。



すなわち、last ポインタが指す node の右側に新たな node を追加し (new 演算子を使うことが思い浮かぶだろうか)、
last ポインタが新たな node を指すようにつけ変えれば良い。
リストの先頭に node を加えることも同様にできる。

node と node の間に新たな node を追加することも以下のように、 new によるオブジェクトの作成とポインタのつけ変えによって実現できる。
配列と異なり、要素のコピーは必要ないことに注意しよう。



ただし、このためには「何番目と何番目の要素の間」を指すために node に index が必要になる。
それはやや繁雑になるので、ここでは取り扱わない。

←第五回-01 : テンプレート ／ 第五回-03 : リストの実装と利用→

第五回トップページへ

クラスから入る C++ へ戻る