トップC-Tips > リスト構造

リスト構造

1.リスト構造

リスト構造で扱うデータ型は以下の例のような型をしていて、このデータを格納する入れ物を「セル」ともいう。

    struct cell_t {
        struct cell_t *next;	// 自己参照構造体
        int data;
    };

あるデータをポインタで結んだデータ構造をリスト構造という。リスト構造には以下の3種類がある。

(1)連結リスト
リストに含まれる各要素(セル)をポインタによって、つなぎ合わせたデータ構造。 一番最後のデータは次を指すデータがないので、NULLポインタをセットしておく。
(2)双方向リスト
セルは前のデータ・後ろのデータの両方のポインタを持っている。 連結リストとは違い、前にも後ろにもデータを辿って行くことができる。 リストの途中にセルを追加したり、リスト途中のセルを削除することができる。
    struct cell_t {
        struct cell_t *prev;	// 前のセルを指す 
        struct cell_t *next;	// 後ろのセルを指す
        int data;
    };
(3)循環リスト
先頭と末尾を繋いで、輪にする。先頭という概念がない。

2.連結リスト

連結リストのプログラム例を以下に示す。 スタックのように、追加セルはリストの先頭に置かれる。リスト途中のセルの削除には向かない。 すなわち、スタックをリスト構造で実現するもの。 配列による実装とはことなり、スタックサイズに制限がない。 (コンピュータのメモリ容量による限界はある)

list1.c

実行結果を下に示す。一番後から追加したデータが先頭にきていることが観測できる。

c:\MH\www\c-tips\data-structure>list1 34 12 56
56
12
34

リスト途中のセルを削除するには、 削除するセルを指定するのではなく、削除する前のセルを指定するような関数ならば作ることができる。 また、指定したセルの後ろにセルを挿入する関数を作ることもできる。

3.双方向リスト

前後を指すポインタがあれば、リストの任意の位置へのセルの追加や削除が自由に行える。

list2.c

実行結果を下に示す。

c:\MH\www\c-tips\data-structure>list2
-[3]
-[3]-[9]
-[5]-[3]-[9]
-[5]-[3]-[2]-[9]
-[5]-[2]-[9]
-[5]-[2]