シングルリンクリストとは

シングルリンクリスト（Singly Linked List）は、データをノードとして格納し、各ノードが次のノードへのポインタを持つ線形データ構造です。配列や順序リスト（シーケンシャルリスト）と異なり、データの挿入・削除が柔軟で、必要に応じて動的にメモリを確保できます。

シングルリンクリストの構造

シングルリンクリストは、各ノードが2つの部分から成ります：

• データ部： 実際のデータを格納
• ポインタ部： 次のノードへの参照（アドレス）を保持

リストの末尾のノードは、NULLを指して終了します。

ノード構造体の定義

#pragma once

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

typedef int SLLDataType;

typedef struct SLLNode {
    SLLDataType data;
    struct SLLNode* next;
} Node;

基本操作の実装

ノードの作成

新しいノードを動的に確保し、初期値を設定します。

static Node* createNode(SLLDataType value) {
    Node* newNode = (Node*)malloc(sizeof(Node));
    if (!newNode) {
        exit(EXIT_FAILURE);
    }
    newNode->data = value;
    newNode->next = NULL;
    return newNode;
}

先頭への挿入（ヘッドインサート）

void pushFront(Node** head, SLLDataType value) {
    assert(head);
    Node* newNode = createNode(value);
    newNode->next = *head;
    *head = newNode;
}

末尾への挿入（テールインサート）

void pushBack(Node** head, SLLDataType value) {
    assert(head);
    Node* newNode = createNode(value);

    if (*head == NULL) {
        *head = newNode;
        return;
    }

    Node* current = *head;
    while (current->next != NULL) {
        current = current->next;
    }
    current->next = newNode;
}

先頭からの削除（ヘッドリムーブ）

void popFront(Node** head) {
    assert(head && *head);
    Node* temp = *head;
    *head = (*head)->next;
    free(temp);
}

末尾からの削除（テールリムーブ）

void popBack(Node** head) {
    assert(head && *head);
    if ((*head)->next == NULL) {
        free(*head);
        *head = NULL;
        return;
    }

    Node* current = *head;
    while (current->next->next != NULL) {
        current = current->next;
    }
    free(current->next);
    current->next = NULL;
}

リストの表示

void printList(const Node* head) {
    const Node* current = head;
    while (current) {
        printf("%d -> ", current->data);
        current = current->next;
    }
    printf("NULL\n");
}

指定位置への挿入

void insertAfter(Node* prevNode, SLLDataType value) {
    assert(prevNode);
    Node* newNode = createNode(value);
    newNode->next = prevNode->next;
    prevNode->next = newNode;
}

指定位置の削除

void erase(Node** head, Node* target) {
    assert(head && *head && target);
    if (*head == target) {
        *head = target->next;
        free(target);
        return;
    }

    Node* current = *head;
    while (current->next != target) {
        current = current->next;
    }
    current->next = target->next;
    free(target);
}

リストの破棄

void destroyList(Node** head) {
    assert(head);
    Node* current = *head;
    while (current) {
        Node* next = current->next;
        free(current);
        current = next;
    }
    *head = NULL;
}

シングルリンクリストの利点と欠点

• 利点： データの挿入・削除が柔軟で高速
• 欠点： ランダムアクセス不可、末尾の操作に時間がかかる

テストコード

int main() {
    Node* head = NULL;

    pushBack(&head, 10);
    pushBack(&head, 20);
    pushFront(&head, 5);
    printList(head);  // 出力: 5 -> 10 -> 20 -> NULL

    popBack(&head);
    printList(head);  // 出力: 5 -> 10 -> NULL

    insertAfter(head, 7);
    printList(head);  // 出力: 5 -> 7 -> 10 -> NULL

    erase(&head, head->next);
    printList(head);  // 出力: 5 -> 10 -> NULL

    destroyList(&head);
    return 0;
}