単連結リストの整列 #4 リストの先頭もきちんと扱う

C

次に、関数node_swapが先頭要素とその次の要素とを交換できないという仕様を何とかしたい。
node_swapのこの制限の理由は既述のように交換したい二つの要素の一つ手前の要素が交換に必要だからである。
このことをもう少し詳細に考察してみる。

交換したい二要素の一つ前の要素が必要というのは、
一つ前の要素が持つ次の要素へのアドレス情報を書き換える必要があるということである。

node_swapに渡すcurrentが要素Aを指している場合、要素Bと要素Cを入れ替えることになるが、
その結果、要素Aの持つ次要素のアドレスは要素Bのアドレスから要素Cのものに書き替わっていなければならない。
もし要素Aと要素Bを入れ替えたい場合は、
要素Aのアドレスを次要素のそれとして持つ要素のアドレスをcurrentとしてnode_swapに与える必要がある。
ところがリストの先頭要素Aのアドレスが書かれているfirst_nodeはnode_t*型であってもnode_t型のメンバーではない。
したがって、currentは要素Aを指すことはできてもfirst_nodeを指すことはできない。

node_t*型のfirst_nodeをnode_t型の要素と同列で扱う方法はいろいろ考えられるが、
ここでは、first_nodeの内容をメンバーに含むダミー要素を作成する方法をとってみる。
これによりcurrentがダミー要素を指せるので、
ダミー要素の次の要素である真の先頭要素とその次の要素との交換が可能になる。

この方針に沿って変更を施してみる。

test_node.c
...snip
static void node_print(node_t *first_node)
{
    node_t *p;
    for (p = first_node->next; p != NULL; p = p->next) {
        printf(p->next == NULL ? "%d\n" : "%d ", p->val);
    }
}
...snip
int main(void)
{
...snip
    node_t *first_node = node_new(0);
    for (i = 0; i < sizeof(data) / sizeof(data[0]); i++) {
        node_append(first_node, data[i]);
    }
...snip
}

やってみると変更すべき箇所は非常に少ない。
リストの内容を表示する関数node_printの中のfor文の初期化式を変更し、
最初に内容を見る要素をfirst_nodeからfirst_node->nextにした。
また、使用者側であるmain関数のテストデータのリストを用意する所を、
ダミーデータ0を与えてダミー要素node_new(0)を作成し、
そのダミー要素の後にデータの入った要素を追加していくように変えただけである。
したがって、node_swap等の本質的なコードはそのままになっている。
ただ、コード内のfirst_nodeというネーミングは意味的にふさわしくない。
上図で示しているように、first_nodeは真の先頭要素Aを指しているのではなく、
そのAを指しているダミー要素を指しているので、不適切な名前と言われても仕方がない。
コードの変更量が最小になる代償としては割に合わないのかもしれないが実験的コードだしまあいいか。

$ ./test_node
9 8 7 6 5 4 3 2 1
9 8 7 6 5 4 3 2 1
9 8 7 6 5 4 3 2 1
9 8 7 6 5 4 3 2 1
9 8 7 6 5 4 3 1 2
9 8 7 6 5 4 1 3 2
9 8 7 6 5 1 4 3 2
9 8 7 6 1 5 4 3 2
9 8 7 1 6 5 4 3 2
9 8 1 7 6 5 4 3 2
9 1 8 7 6 5 4 3 2
1 9 8 7 6 5 4 3 2

実行してみると先頭要素とその次の要素の交換まできちんと処理されている。