こんにちは、めのんです！
前回予告したように今回は線形リストの解説をします。
「線形リスト」というのはCの仕様ではなくてデータ構造です。
すごく基本的なデータ構造なんですけど、Cではそのようなものも自分で作るのが基本です。
線形リストってそもそも何なの？
「線形リスト」というのは、ノードを数珠つなぎにして列を作ります。
あまりくどくど説明するより実際のコードを示した方がいいでしょうね。
PHPで作ってみる
まずはPHPで線形リストを作ってみましょう。
<?php
$nodes = [];
for ($i = 0; $i < 10; $i++)
{
$nodes[$i] = [
'value' => $i,
'next' => $i + 1
];
}
$nodes[count($nodes) - 1]['next'] = -1;
print_r($nodes);
このコードを実行すると次のような結果になります。
Array
(
[0] => Array
(
[value] => 0
[next] => 1
)
[1] => Array
(
[value] => 1
[next] => 2
)
[2] => Array
(
[value] => 2
[next] => 3
)
[3] => Array
(
[value] => 3
[next] => 4
)
[4] => Array
(
[value] => 4
[next] => 5
)
[5] => Array
(
[value] => 5
[next] => 6
)
[6] => Array
(
[value] => 6
[next] => 7
)
[7] => Array
(
[value] => 7
[next] => 8
)
[8] => Array
(
[value] => 8
[next] => 9
)
[9] => Array
(
[value] => 9
[next] => -1
)
)このサンプルでは10要素の配列にひとつずつノードを作って、’next’キーで次のノードがどこかを指すように設定しています。
とりあえず前から順に数珠つなぎにしています。
最後の要素のnextには-1を入れていますが、これは番兵です。
つまりnextが-1ならそこで線形リストは終わりになります。
線形リストの内容を出力する
この線形リストを先頭から順に出力してみます。
$top = 0;
for ($pos = $top; $pos >= 0; $pos = $nodes[$pos]['next'])
{
printf("%d\n", $nodes[$pos]['value']);
}
0
1
2
3
4
5
6
7
8
9
「こんなことをして何がうれしいの？」って思いますよね。
線形リストは、一部のノードをリストから取り除いたり、挿入したりといった操作をやりやすいんです。
普通の配列でもできるのですが、挿入や削除をしようと思うと、大きいデータでは大量のコピーが発生します。
その点、線形リストならノードのつなぎ直しだけで済みます。
ノードのつなぎ替え
たとえば添数が3のノードを先頭につなぎ直してみましょう。
$nodes[2]['next'] = 4;
$nodes[3]['next'] = 0;
$top = 3;
この時点で、さきほどのループを使って順に出力してみると次のようになります。
3
0
1
2
4
5
6
7
8
9
ノードの除去
次は添数5のノードを除去してみますね。
$nodes[4]['next'] = 6;
これも同じように順に出力してみますね。
3
0
1
2
4
6
7
8
9
ノードの挿入
そして、さっき除去したノードを要素7の次に挿入してみましょう。
$nodes[7]['next'] = 5;
$nodes[5]['next'] = 8;
これも結果を見てみましょう。
3
0
1
2
4
6
7
5
8
9
線形リストはこんなデータ構造です。
Cで線形リストを作ってみよう
ここまではPHPで線形リストを作ってきましたが、ここからはCで作っていきます。
Cで線形リストを作るには、普通ノード用の構造体を作ります。
struct node
{
int value;
int next;
};これでもいいのですが、さきほどのPHPのコードを見ていただければわかるように、ノードのための配列にどうしてもしばられてしまいます。
もっといろんな形でノードを作れれば応用範囲が広がりますよね。
たとえばノードをmalloc関数で割り付けることができればメモリがある限りいくつでもノードをつなげることができますよね。
そのためにはメンバnextをint型ではなくポインタにすると便利です。
struct node
{
int value;
struct node *next;
};こんな風に構造体のメンバに同じ構造体型へのポインタを持たせることができます。
構造体は定義が完結していなくてもstruct タグだけでも不完全型として使えるんでしたね。
まずはPHPのときと同じように10要素の配列を作って、それを並べるところからはじめてみますね。
#include <stdio.h>
struct node
{
int value;
struct node *next;
};
struct node nodes[10];
int main(void)
{
// 線形リストを組み立てる。
for (int i = 0; i < 10; i++)
{
nodes[i].value = i;
nodes[i].next = &nodes[i + 1];
}
nodes[9].next = NULL;
struct node *top = &nodes[0];
// 先頭から順に出力する。
for (struct node *p = top; p != NULL; p = p->next)
{
printf("%d\n", p->value);
}
return 0;
}メンバnextをポインタにしましたので、番兵にはNULLを使っています。
この方がきっとわかりやすいと思います。
PHPで作った線形リストと同じようにすれば、ノードの並べ替え、除去、挿入ができます。
ぜひご自身で実際に試してみてくださいね。
線形リストはデータ構造としては本当に基本的なものですので、いろんなところで使われています。
この週末にもこの線形リストを実際に使った例を示せたらなと考えています（まだ確定ではないので、予定が変わったらごめんなさい）。
今回紹介した線形リストは、nextを使って1方向にだけつながっていますが、同じく自己参照ポインタのメンバpreviousを追加して双方向にすることもあります。
そんなに難しくないので、余力のある方はチャレンジしてみてください。
今回の解説は以上になります。
いきなり難度が上がったように感じられた方もいらっしゃるかもしれませんね。
でも、落ち着いて実際に手を動かしてみれば、きっと理解できると思います。
次回は型の境界調整数を求める方法を紹介したいと思います。
どうぞご期待ください！
