C言語で単方向リストの実装

f:id:fa11enprince:20200617071712j:plain
2020-08-05

C言語で単方向リストを書いてみました。

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

typedef struct int_list_ {
    int value;
    struct int_list_* next;
} int_list;

// --- 外部関数 ---
// リスト初期化関数
int_list* int_list_init();
// リスト破棄関数
void int_list_destroy(int_list* list);
// リスト表示関数
void int_list_dump(int_list* list);
// リスト追加関数(末尾)
int int_list_push_back(int_list* list, int value);
// リスト追加関数(任意の位置)
int int_list_push(int_list* list, int value, int pos);
// リスト削除関数(任意の位置)
int int_list_delete(int_list* list, int pos);

// --- 内部関数 ---
// リスト追加関数(内部関数)
static int int_list_add_node(int_list* cur, int value, int_list *next);
// リスト追加関数(内部関数)
static void int_list_delete_node(int_list* list, int_list* cur);

int main()
{
    int_list* list = int_list_init();
    int rc = 0;
    rc = int_list_push_back(list, 10);
    rc = int_list_push_back(list, 11);
    int_list_dump(list);  // 10, 11
    rc = int_list_push(list, 12, 1);
    rc = int_list_push(list, 13, 0);
    int_list_dump(list);  // 13, 10, 12, 11
    rc = int_list_delete(list, 0);
    rc = int_list_delete(list, 1);
    int_list_dump(list);  // 12, 11
    int_list_destroy(list);
    return 0;
}


int_list* int_list_init() {
    // ダミーノードを作成
    int_list* list = NULL;
    list = (int_list*)malloc(1 * sizeof(int_list));
    list->value = 0;
    list->next = NULL;
    return list;
}

void int_list_destroy(int_list* list) {
    for (list = list->next; list != NULL; list = list->next) {
        int_list_delete_node(list, list->next);
    }
}

void int_list_dump(int_list* list)
{
    printf("DUMP LIST _______ \n");
    // 先頭ノードを飛ばす
    for (list = list->next; list != NULL; list = list->next)
    {
        printf("%d\n", list->value);
    }
}

int int_list_push_back(int_list* list, int value)
{
    // 最後尾までポインタをずらす
    for(; list->next != NULL; list = list->next);
    // リストを１つ増やす。
    return int_list_add_node(list, value, NULL);
}

int int_list_push(int_list* list, int value, int pos)
{
    int cnt = 0;

    if (pos < 0) { return -1; }
    // 指定分ポインタをずらす(ポジションは0相対) 
    for (cnt = 0 ; cnt < pos  && list != NULL; cnt++)
    {
        list = list->next;
    }
    // リストを１つ増やす。
    return int_list_add_node(list, value, list->next);
}

int int_list_delete(int_list* list, int pos)
{
    int_list* cur = NULL;
    int cnt = 0;

    if (pos < 0) { return -1; }
    // 指定分の１つ前までポインタをずらす(ポジションは0相対)
    for(cnt = 0 ; cnt < (pos - 1) && list != NULL; cnt++)
    {
        list = list->next;
    }
    // 次のポインタをセット(これが削除対象)
    cur = list->next;
    int_list_delete_node(list, cur);
}

static int int_list_add_node(int_list* cur, int value, int_list* next)
{
    int_list* added = NULL;
    
    added = (int_list*)malloc(1 * sizeof(int_list));
    if (added == NULL) {
        return -1;
    }
    added->value = value;
    added->next = NULL;
    cur->next = added;
    if (next != NULL) {
        added->next = next;
    }
    return 0;
}

static void int_list_delete_node(int_list* list, int_list* cur)
{
    // 現在位置の１つ前のリストを消すリストの次のノードで更新
    list->next = cur->next;
    // 現在位置のリストを解放
    free(cur);
}