[C言語] 単方向リスト

singlylinkedlist.c

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

/* ノード */
typedef struct Node_tag {
    int data;
    struct Node_tag *next;
} Node;

/* 単方向リスト */
typedef struct {
    Node *head;
} List;

/* リストの初期化 */
void init_list(List *list)
{
    list->head = NULL;
}

/* ノードの生成 */
Node *create_node(int num)
{
    Node *new_node;
    
    if ((new_node = malloc(sizeof(Node))) == NULL) {
        perror("malloc");
        exit(1);
    }
    
    new_node->data = num;
    new_node->next = NULL;

    return new_node;
}

/* ノードをリストの先頭に挿入する */
void insert_front(List *list, Node *node)
{
    node->next = list->head;
    list->head = node;   
}

/* ノードの追加 (ノードを生成して先頭に挿入) */
void add(List *list, int num)
{
    insert_front(list, create_node(num));
}

/* リストの構築
   i 番目に追加するノードに d[i] を格納 */
void create_list(List *list, const int d[], size_t length_of_d)
{
    for (size_t i = 0; i < length_of_d; i++) {
        add(list, d[i]);
    }  
}

/* 全ノードのデータを表示 */
void show_list(const List *list, const char *list_name)
{
    printf("\n[List: %s]\n", list_name);
    printf("head = %p\n", list->head);  /* 先頭のノードのアドレス */
    for (Node *p = list->head; p != NULL; p = p->next) {
        puts("\t|\n\tV");  /* 下矢印 */
        printf("[Node: %p]\n", p, p->data, p->next);  /* ノードのアドレス */
        printf("data = %d\n", p->data);  /* ノードのデータ */
        printf("next = %p\n", p->next);  /* 次のノードのアドレス */
    }
    putchar('\n');
}

/* 先頭のノードを削除 */
void remove_front(List *list)
{
    if (list->head != NULL) {
        Node *temp = list->head->next;
        free(list->head);
        list->head = temp;  
    }
}

/* 全ノード削除 */
void clear_list(List *list)
{
    while (list->head != NULL) {
        remove_front(list);
    }
}

/* ノードの探索 (線形探索) */
Node *search(const List *list, int key)
{
    for (Node *p = list->head; p != NULL; p = p->next) {
        if (p->data == key) { 
            return p; 
        }
    }

    return NULL;
}

int main(void)
{
    List list1;
    int d[] = {1, 2, 3, 4, 5};
    size_t length_of_d = sizeof(d) / sizeof(d[0]);  /* 配列 d の要素数 */
    int key; 
    Node *p;
    
    init_list(&list1);   /* 初期化 */
    create_list(&list1, d, length_of_d);  /* リストの構築 */
    show_list(&list1, "list1");   /* 各ノードのデータを表示 */
    
    /* 探索 (見つかる例) */
    key = 3;
    if ((p = search(&list1, key)) == NULL) {
        printf("%d not found. ", key);
    } else {
        printf("%d found. ", p->data);
    }
     
    clear_list(&list1);  /* 終了処理 (malloc で確保した領域の解放) */
    
    return 0;
}