連結リストの基本概念とノード定義

配列などのシーケンシャルなデータ構造では、要素の挿入や削除に伴うデータの移動コストが高くなる。この問題を解決するため、各要素をポインタで連結する連鎖構造（単方向連結リスト）が用いられる。

単方向連結リストには以下の特徴がある。

• 論理的に隣接する要素が物理的なメモリ上でも隣接している必要がない。
• ランダムアクセスが不可能であり、特定の要素を参照するには先頭から順に走査する必要がある。
• 各ノードは、データを保持する「データ域」と次のノードのアドレスを保持する「ポインタ域」で構成される。

ノードの構造体定義は以下の通りである。

typedef int ValueType;

typedef struct ListNode {
    ValueType value;
    struct ListNode* next;
} LinkedList;

リストの初期化と基本操作

空リストの生成

操作を簡略化するため、先頭に実データを持たないダミーヘッド（先頭ノード）を配置する。ダミーヘッドのポインタ域をNULLに設定することで空リストを表現する。

LinkedList* CreateList(void) {
    LinkedList* head = (LinkedList*)malloc(sizeof(LinkedList));
    if (!head) return NULL;
    head->value = 0;
    head->next = NULL;
    return head;
}

リストの走査

先頭ノードの次から順にポインタを辿り、データを出力する。

void PrintList(LinkedList* head) {
    if (!head) return;
    LinkedList* cur = head->next;
    while (cur) {
        printf("%d ", cur->value);
        cur = cur->next;
    }
    printf("\n");
}

メモリの解放

全ノードを走査し、確保したメモリを解放する。現在のノードを解放する前に次のノードのアドレスを一時変数へ保存しておく必要がある。

LinkedList* DestroyList(LinkedList* head) {
    if (!head) return NULL;
    LinkedList* cur = head;
    LinkedList* tmp;
    while (cur) {
        tmp = cur->next;
        free(cur);
        cur = tmp;
    }
    return NULL;
}

データの挿入

先頭への挿入

ダミーヘッドの直後に新しいノードを挿入する。

int InsertAtHead(LinkedList* head, ValueType val) {
    if (!head) return -1;
    LinkedList* newNode = (LinkedList*)malloc(sizeof(LinkedList));
    if (!newNode) return -1;
    newNode->value = val;
    newNode->next = head->next;
    head->next = newNode;
    return 0;
}

末尾への挿入

リストの終端まで走査し、最後のノードの後ろに新しいノードを追加する。

int InsertAtTail(LinkedList* head, ValueType val) {
    if (!head) return -1;
    LinkedList* cur = head;
    while (cur->next) {
        cur = cur->next;
    }
    LinkedList* newNode = (LinkedList*)malloc(sizeof(LinkedList));
    if (!newNode) return -1;
    newNode->value = val;
    newNode->next = NULL;
    cur->next = newNode;
    return 0;
}

任意の位置への挿入

指定されたインデックスの位置にノードを挿入する。指定位置の前のノードを見つけ、ポインタを繋ぎ変える。

int InsertAtIndex(LinkedList* head, ValueType val, int idx) {
    if (!head || idx < 0) return -1;
    LinkedList* cur = head;
    int pos = 0;
    while (cur->next && pos < idx) {
        cur = cur->next;
        pos++;
    }
    if (pos < idx) return -1;
    LinkedList* newNode = (LinkedList*)malloc(sizeof(LinkedList));
    if (!newNode) return -1;
    newNode->value = val;
    newNode->next = cur->next;
    cur->next = newNode;
    return 0;
}

データの削除

値を指定した削除

対象のデータを持つノードの前のノードを見つけ、ポインタを繋ぎ変えた上で対象ノードのメモリを解放する。

int RemoveByValue(LinkedList* head, ValueType val) {
    if (!head) return -1;
    LinkedList* cur = head;
    while (cur->next && cur->next->value != val) {
        cur = cur->next;
    }
    if (!cur->next) return -1;
    LinkedList* target = cur->next;
    cur->next = target->next;
    free(target);
    return 0;
}

インデックスを指定した削除

指定されたインデックスのノードを削除する。同様に、前のノードからポインタを操作する。

int RemoveAtIndex(LinkedList* head, int idx) {
    if (!head || idx < 0) return -1;
    LinkedList* cur = head;
    int pos = 0;
    while (cur->next && pos < idx) {
        cur = cur->next;
        pos++;
    }
    if (!cur->next || pos < idx) return -1;
    LinkedList* target = cur->next;
    cur->next = target->next;
    free(target);
    return 0;
}

データの探索

指定した値を持つノードのインデックスを先頭から線形探索で検索する。

int FindByValue(LinkedList* head, ValueType val) {
    if (!head) return -1;
    LinkedList* cur = head->next;
    int idx = 0;
    while (cur) {
        if (cur->value == val) return idx;
        cur = cur->next;
        idx++;
    }
    return -1;
}

応用操作

リストの反転

先頭ノード以降のノードを順に取り出し、ダミーヘッドの直前に挿入する操作を繰り返すことで反転させる。

int ReverseList(LinkedList* head) {
    if (!head || !head->next || !head->next->next) return 0;
    LinkedList* cur = head->next;
    LinkedList* nxt;
    head->next = NULL;
    while (cur) {
        nxt = cur->next;
        cur->next = head->next;
        head->next = cur;
        cur = nxt;
    }
    return 0;
}

隣接ノード和の最大値探索

連続する2つのノードのデータ値の和が最大となる最初のノードを探索する。

LinkedList* FindMaxAdjacentSum(LinkedList* head, ValueType* maxSum) {
    if (!head || !head->next || !head->next->next) return NULL;
    LinkedList* prev = head->next;
    LinkedList* curr = prev->next;
    LinkedList* result = prev;
    *maxSum = prev->value + curr->value;
    
    while (curr->next) {
        prev = prev->next;
        curr = curr->next;
        ValueType sum = prev->value + curr->value;
        if (sum > *maxSum) {
            *maxSum = sum;
            result = prev;
        }
    }
    return result;
}

ソート済みリストの結合

2つのソート済みリストを、ソート順を保ったまま1つのリストに統合する。

int MergeSortedLists(LinkedList* list1, LinkedList* list2) {
    if (!list1 || !list2) return -1;
    LinkedList* p = list1->next;
    LinkedList* q = list2->next;
    LinkedList* tail = list1;
    list1->next = NULL;
    list2->next = NULL;
    
    while (p && q) {
        if (p->value <= q->value) {
            tail->next = p;
            p = p->next;
        } else {
            tail->next = q;
            q = q->next;
        }
        tail = tail->next;
        tail->next = NULL;
    }
    if (p) tail->next = p;
    if (q) tail->next = q;
    return 0;
}

リストの並べ替え

選択ソートの考え方を用い、ノード内のデータ値を交換してリストをソートする。

int SortList(LinkedList* head) {
    if (!head || !head->next) return 0;
    for (LinkedList* i = head->next; i->next != NULL; i = i->next) {
        for (LinkedList* j = i->next; j != NULL; j = j->next) {
            if (i->value > j->value) {
                ValueType temp = i->value;
                i->value = j->value;
                j->value = temp;
            }
        }
    }
    return 0;
}