単連結リストの整列 #2 リスト要素の交換、でも不完全

リストの要素を整列するためには要素の並びを変更できなければならない。
隣り合う要素の順序を入れ替えられれば、
その処理の組み合わせで任意の要素間の交換が可能となる。
そこで、ある要素とその次の要素の順序を入れ替える関数を書いてみる。

test_node.c

...snip
static void node_swap(node_t *current)
{
    node_t *p = current->next;
    node_t *q = p->next;
    current->next = q;
    p->next = q->next;
    q->next = p;
}
...snip

関数node_swapはポインタcurrentが指している要素の次の要素とさらにその次の要素とを交換する。
currentが指している要素と次の要素とを交換するのではない。
次の図の上のようなリストをnode_swapに渡すと下のようなリストになる。

なぜ、currentが指している要素と次の要素との交換ではないのかというと、
図を見れば分かるように、交換前に順序が先であった要素のもう一つ前の要素が持つ次の要素のアドレスも、
交換のためには変更する必要があるからである。
もし、currentが指している要素と次の要素とを交換する場合にcurrentしか与えられなければ、
単連結リストであるがゆえにcurrentの一つ前の要素のアドレスを知ることはできない。

このnode_swap関数の実装は不完全である。
引数で指定する要素の次の要素と次の次の要素との交換しかできないため、
一つ前の要素というものが無いリストの先頭の要素と二番目の要素との交換ができないのが一つ。
もう一つは、currentがリストの末尾やその一つ前の要素であった場合、何が起きるか分からないことである。
それ以外の場合は特に問題なく動作するはずである。

test_node.c

...snip
int main(void)
{
    size_t i;
    int data[] = {9, 8, 7, 6, 5, 4, 3, 2, 1};
    node_t *first_node = node_new(data[0]);
    for (i = 1; i < sizeof(data) / sizeof(data[0]); i++) {
        node_append(first_node, data[i]);
    }
    node_print(first_node);
    node_swap(first_node);       /* swap 2nd node for 3rd */
    node_print(first_node);
    node_swap(first_node->next); /* swap 3rd node for 4th */
    node_print(first_node);
    node_swap(first_node);       /* swap 2nd node for 3rd */
    node_print(first_node);
    return 0;
}

のようなコードを実行すると、

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

のように最終的にリストの二番目と四番目の要素が交換される。