単連結リストの整列 #1 素朴な単連結リストを実装する

単連結リストをin-placeっぽい感じの方法でソートする。
まず、単連結リスト自体を実装することから始めよう。
素朴だがむき出しの、そして効率の悪い実装で実験的コードを書いてみる。

test_node.c

#include <stdio.h>
#include <stdlib.h>

typedef struct tag_node node_t;

struct tag_node {
    node_t *next;
    int val;
};

static node_t *node_new(int val)
{
    node_t *p = malloc(sizeof(node_t));
    if (p != NULL) {
        p->next = NULL;
        p->val = val;
    }
    return p;
}

static int node_append(node_t *first_node, int val)
{
    node_t *n, *p;
    if (first_node == NULL || (n = node_new(val)) == NULL) return 0;
    for (p = first_node; p->next != NULL; p = p->next) ;
    p->next = n;
    return 1;
}

static void node_print(node_t *first_node)
{
    node_t *p;
    for (p = first_node; p != NULL; p = p->next) {
        printf(p->next == NULL ? "%d\n" : "%d ", p->val);
    }
}

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);
    return 0;
}

ここではリストで管理するデータはint型の整数値としている。
一つ一つのデータはnode_t型のリスト要素に収められ、
各要素が自分の次の要素のアドレスを保持することで連結リストを構成する。
リストを使う側は最初の要素のアドレスだけを管理すればよい。

リストの使用者側が最初の要素のアドレスしか持たないため、
リストの一番最後の要素の次に新しい要素を追加するnode_append関数では、
呼ばれるたびに最初の要素からたどって最後の要素を探索している。
main関数ではエラー処理もリスト要素の解放も行ってないが、
とりあえずまあいいだろう。

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