PricingLoginStart free
C Academy · レッスン

挿入と削除

リストを変更します。

レッスン 2/413 ステップ

「挿入と削除」はCoddyKit上の無料C Academyレッスンです。 これはレッスン2/4です。 下記で完全なレッスンを無料で読むことができます。その後、ブラウザ内の組み込みコードエディタと24時間対応のAIチューターでハンズオン演習できます。 これはC Academy学習パスの一部であり、ウェブとCoddyKitアプリ全体で進捗が同期されます。 C Academyコースには全4レッスンが含まれています。

リストを変更する

連結リストの強みは、挿入と削除を低コストで行えることです。配列のように要素を移動するのではなく、ポインターをつなぎ替えます。

このレッスンでは、さまざまな位置へのノードの挿入と削除を扱います。

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

struct Node { int value; struct Node *next; };
struct Node *make(int v){struct Node*n=malloc(sizeof*n);n->value=v;n->next=NULL;return n;}

int main(void) {
    struct Node *head = make(2);
    printf("start: %d\n", head->value);
    free(head);
    return 0;
}

先頭に挿入する

先頭への挿入はO(1)で行えます。新しいノードを作成し、そのnextを現在のheadに向けてから、headを新しいノードに更新します。

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

struct Node { int value; struct Node *next; };
struct Node *make(int v){struct Node*n=malloc(sizeof*n);n->value=v;n->next=NULL;return n;}

int main(void) {
    struct Node *head = make(2);
    struct Node *fresh = make(1);
    fresh->next = head;
    head = fresh;
    printf("%d -> %d\n", head->value, head->next->value);
    return 0;
}

二重ポインターを渡す理由

関数の内部からheadを変更するには、そのアドレスであるstruct Node **を渡す必要があります。

そうしないと、関数はローカルコピーだけを変更するため、呼び出し元のheadは変わりません。

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

struct Node { int value; struct Node *next; };
struct Node *make(int v){struct Node*n=malloc(sizeof*n);n->value=v;n->next=NULL;return n;}

void push(struct Node **head, int v) {
    struct Node *n = make(v);
    n->next = *head;
    *head = n;
}

int main(void) {
    struct Node *head = NULL;
    push(&head, 5);
    push(&head, 4);
    printf("%d %d\n", head->value, head->next->value);
    return 0;
}

末尾に挿入する

末尾への追加では、最後のノードまでたどり、そのnextに新しいノードをつなぎます。

リストが空の場合は、新しいノードがheadになります。

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

struct Node { int value; struct Node *next; };
struct Node *make(int v){struct Node*n=malloc(sizeof*n);n->value=v;n->next=NULL;return n;}

void append(struct Node **head, int v) {
    struct Node *n = make(v);
    if (!*head) { *head = n; return; }
    struct Node *p = *head;
    while (p->next) p = p->next;
    p->next = n;
}

int main(void) {
    struct Node *head = NULL;
    append(&head, 1); append(&head, 2);
    printf("%d %d\n", head->value, head->next->value);
    return 0;
}

ノードの後ろに挿入する

途中に挿入するには、挿入位置の直前にあるノードを見つけ、そのノードと現在の後続ノードの間に新しいノードをつなぎます。

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

struct Node { int value; struct Node *next; };
struct Node *make(int v){struct Node*n=malloc(sizeof*n);n->value=v;n->next=NULL;return n;}

void insert_after(struct Node *node, int v) {
    struct Node *n = make(v);
    n->next = node->next;
    node->next = n;
}

int main(void) {
    struct Node *head = make(1);
    head->next = make(3);
    insert_after(head, 2);
    printf("%d %d %d\n", head->value, head->next->value, head->next->next->value);
    return 0;
}

操作の順序が重要

ノードをつなぎ込むときは、前のノードのnextを変更する前に、必ず新しいノードのnextを設定してください。

逆の順序にすると、リストの残りへの参照を失います。

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

struct Node { int value; struct Node *next; };
struct Node *make(int v){struct Node*n=malloc(sizeof*n);n->value=v;n->next=NULL;return n;}

int main(void) {
    struct Node *a = make(1), *c = make(3);
    a->next = c;
    struct Node *b = make(2);
    b->next = a->next;
    a->next = b;
    printf("%d %d %d\n", a->value, b->value, c->value);
    return 0;
}

最初のノードを削除する

headを削除するには、現在のheadを保存し、headをhead->nextに進めてから、古いheadを解放します。

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

struct Node { int value; struct Node *next; };
struct Node *make(int v){struct Node*n=malloc(sizeof*n);n->value=v;n->next=NULL;return n;}

void pop(struct Node **head) {
    if (!*head) return;
    struct Node *old = *head;
    *head = old->next;
    free(old);
}

int main(void) {
    struct Node *head = make(1);
    head->next = make(2);
    pop(&head);
    printf("new head: %d\n", head->value);
    free(head);
    return 0;
}

値で削除する

指定した値を持つノードを削除するには、前のノードを追跡し、prev->next = target->nextを設定して対象ノードを飛び越えます。

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

struct Node { int value; struct Node *next; };
struct Node *make(int v){struct Node*n=malloc(sizeof*n);n->value=v;n->next=NULL;return n;}

void del(struct Node **head, int v) {
    struct Node *cur = *head, *prev = NULL;
    while (cur && cur->value != v) { prev = cur; cur = cur->next; }
    if (!cur) return;
    if (prev) prev->next = cur->next; else *head = cur->next;
    free(cur);
}

int main(void) {
    struct Node *head = make(1);
    head->next = make(2);
    head->next->next = make(3);
    del(&head, 2);
    printf("%d %d\n", head->value, head->next->value);
    return 0;
}

headの場合を処理する

対象がheadの場合、削除には特別な処理が必要です。前のノードがないため、headポインターを直接更新します。

上で示したように、二重ポインターを使うとこの処理を簡潔に書けます。

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

struct Node { int value; struct Node *next; };
struct Node *make(int v){struct Node*n=malloc(sizeof*n);n->value=v;n->next=NULL;return n;}

int main(void) {
    struct Node *head = make(1);
    head->next = make(2);
    struct Node *old = head;
    head = head->next;
    free(old);
    printf("head now %d\n", head->value);
    free(head);
    return 0;
}

メモリリークを防ぐ

リストから削除するすべてのノードをfreeする必要があります。ノードを解放せずに取り外すと、そのノードが占めていたメモリがリークします。

同様に、まだリストにつながっているノードを決して解放しないでください。ダングリングポインターが発生します。

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

struct Node { int value; struct Node *next; };
struct Node *make(int v){struct Node*n=malloc(sizeof*n);n->value=v;n->next=NULL;return n;}

int main(void) {
    struct Node *n = make(7);
    free(n);
    printf("node freed, no leak\n");
    return 0;
}

順序を保った挿入（任意）

ソート順で挿入するのはよくある応用です。値が収まる位置を見つけるまでたどり、そこで新しいノードをつなぎ込みます。

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

struct Node { int value; struct Node *next; };
struct Node *make(int v){struct Node*n=malloc(sizeof*n);n->value=v;n->next=NULL;return n;}

void insert_sorted(struct Node **head, int v) {
    struct Node *n = make(v);
    if (!*head || (*head)->value >= v) { n->next = *head; *head = n; return; }
    struct Node *p = *head;
    while (p->next && p->next->value < v) p = p->next;
    n->next = p->next; p->next = n;
}

int main(void) {
    struct Node *head = NULL;
    insert_sorted(&head, 3);
    insert_sorted(&head, 1);
    insert_sorted(&head, 2);
    for (struct Node *p = head; p; p = p->next) printf("%d ", p->value);
    printf("\n");
    return 0;
}

クイックチェック

リストの変更についての理解度を確認しましょう。

対話的なレッスンで答える

まとめ

ノードの挿入と削除の方法を学びました。

  • 先頭への挿入はO(1)ですが、末尾への追加や順序を保った挿入には走査が必要です。
  • headが変わる可能性がある場合は、二重ポインターを使います。
  • ノードをつなぎ込むときは注意してください。再接続する前に新しいノードのnextを設定します。
  • 削除では前のノードを追跡し、削除したノードを必ずfreeします。
無料で開始

AI チューターと学ぶ C — 無料

ブラウザでリアルコードを書いて実行し、24/7 の AI チューターから瞬時にサポートを受け、ウェブまたはアプリで続きから学習できます。

コース
39
レッスン
144
無料で学習を始めるコース全体を表示

よくある質問

「挿入と削除」レッスンは無料ですか？

はい。「挿入と削除」の完全なテキストはこのウェブで無料で読めます。インタラクティブに演習し（組み込みコードエディタと24時間対応のAIチューター）、C Academyコースの残りをアンロックするには、CoddyKit PROにアップグレードしてください。 C Academyコースには全4レッスンが含まれています。

「挿入と削除」で何を学びますか？

リストを変更します。 ブラウザで直接実行するハンズオンコードでC Academyを演習し、24時間対応のAIチューターがレッスンを進める中での質問に答えます。

C Academyを始めるのに経験は必要ですか？

事前経験は必要ありません。CoddyKitのC Academyは初級者から上級者向けに構成されているため、ここから始めるか最初から始めて、自分のペースで進むことができます。 これはレッスン2/4です。

「挿入と削除」レッスンにはどのくらい時間がかかりますか？

ほとんどのCoddyKitレッスンは約5～10分かかります。各レッスンはコンパクトでインタラクティブなので、着実に進歩し、ウェブとアプリ全体で正確に前回の場所から再開できます。

このC Academyレッスンでコードを書いて実行できますか？

はい。すべてのC Academyレッスンに組み込みコードエディタが含まれているため、ブラウザでリアルコードを書いて実行し、即座のAIフィードバックを取得できます。ローカル設定は不要です。

このコースのすべてのレッスン

  1. 単方向連結リスト
  2. 挿入と削除
  3. 走査と検索
  4. 双方向連結リスト
← C Academyに戻る