単連結リストの整列 #3 リスト末尾付近をきちんと扱う

関数node_swapに与えた要素がリストの末尾近辺の場合のバグの修正は簡単である。

test_node.c

...snip
static void node_swap(node_t *current)
{
    node_t *p, *q;
    if (current == NULL || (p = current->next) == NULL || (q = p->next) == NULL) return;
    current->next = q;
    p->next = q->next;
    q->next = p;
}
...snip

currentがNULLであるか、リストの末尾要素かその一つ前の要素である場合は、
そもそも交換対象がないので単に何もせずに関数から抜ける。

test_node.c

...snip
static node_t *node_search_prev_node(node_t *next_node, node_t *base)
{
    while (base != NULL && base->next != next_node) base = base->next;
    return base;
}

int main(void)
{
    node_t *p;
    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);
    for (p = NULL; ; ) {
        node_swap(p);
        node_print(first_node);
        if (p == first_node) break;
        p = node_search_prev_node(p, first_node);
    }
    return 0;
}

このコードはnode_swapの引数に、
NULL、末尾要素、その一つ前の要素、さらにその一つ前の要素、……、先頭の要素、
と順番に与えた時のリストの状態を表示する。
関数node_search_prev_nodeは、先頭要素のアドレスがbaseのリストについて、
アドレスがnext_nodeである要素の一つ前の要素を探索してそのアドレスを返す。
next_nodeがリスト中に無かった時はNULLを返す。
next_nodeがbaseのときもその一つ前の要素は無いので返すのはNULLである。

$ ./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行目は元のリストの状態である。
2行目はNULLをnode_swapに与えた結果であり、
3行目、4行目が末尾要素、その一つ前の要素を与えた結果である。
三つの結果ともエラーなど起こさず、ちゃんと元の状態から変化しない。
それ以降は一つ前のリストの状態から指定要素の次と次の次の要素とが交換されていることが分かる。