Gobble up pudding

プログラミングの記事がメインのブログです。

MENU

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

スポンサードリンク

f:id:fa11enprince:20200617071712j:plain

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);
    // リストを1つ増やす。
    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;
    }
    // リストを1つ増やす。
    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; }
    // 指定分の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)
{
    // 現在位置の1つ前のリストを消すリストの次のノードで更新
    list->next = cur->next;
    // 現在位置のリストを解放
    free(cur);
}

こんなの作んなくてもC++ならSTLが!!
とか思うのですが、やはり蛇口をひねるとなぜか水が出るではいけないところもあると思うんです。
ところで片方向ではなく単方向リストのほうが多数派ですね。