単方向連結リスト
ノードとポインターです。
「単方向連結リスト」はCoddyKit上の無料C Academyレッスンです。 これはレッスン1/4です。 下記で完全なレッスンを無料で読むことができます。その後、ブラウザ内の組み込みコードエディタと24時間対応のAIチューターでハンズオン演習できます。 これはC Academy学習パスの一部であり、ウェブとCoddyKitアプリ全体で進捗が同期されます。 C Academyコースには全4レッスンが含まれています。
連結リストとは
連結リストは、ノードと呼ばれる小さな構造体が連なったものです。各ノードには値と、次のノードへのポインターが格納されます。
配列とは異なり、要素はメモリ上で連続している必要がなく、リストの拡張や縮小も簡単です。
#include <stdio.h>
struct Node {
int value;
struct Node *next;
};
int main(void) {
printf("A node holds a value and a next pointer\n");
return 0;
}ノードを定義する
ノードの struct にはデータと、次のノードを指す struct Node *next が含まれます。
ポインター型が同じ struct を参照することで、ノード同士を連結できます。
#include <stdio.h>
struct Node {
int value;
struct Node *next;
};
int main(void) {
struct Node n;
n.value = 42;
n.next = NULL;
printf("value=%d, next is NULL: %d\n", n.value, n.next == NULL);
return 0;
}先頭ポインター
リストは、最初のノードを指す単一のポインターで識別します。これを先頭（head）と呼びます。
空のリストは、先頭が NULL になっているだけです。
#include <stdio.h>
struct Node { int value; struct Node *next; };
int main(void) {
struct Node *head = NULL;
printf("List is empty: %d\n", head == NULL);
return 0;
}ノードを確保する
ノードは通常、作成した関数が終了しても存在し続けるように、malloc でヒープ上に作成します。
必ず戻り値をチェックし、後でノードを解放することも忘れないでください。
#include <stdio.h>
#include <stdlib.h>
struct Node { int value; struct Node *next; };
int main(void) {
struct Node *n = malloc(sizeof(struct Node));
n->value = 7;
n->next = NULL;
printf("%d\n", n->value);
free(n);
return 0;
}アロー演算子
構造体へのポインターがある場合は、-> を使ってメンバーにアクセスします。n->value は (*n).value と同じ意味です。
連結リストでは、アロー演算子を何度も使うことになります。
#include <stdio.h>
#include <stdlib.h>
struct Node { int value; struct Node *next; };
int main(void) {
struct Node *n = malloc(sizeof(struct Node));
n->value = 99;
printf("%d\n", n->value);
free(n);
return 0;
}2つのノードを連結する
ノードを接続するには、1つ目のノードの next が2つ目のノードを指すように設定します。最後のノードの next は終端を示すために NULL のままにします。
#include <stdio.h>
#include <stdlib.h>
struct Node { int value; struct Node *next; };
int main(void) {
struct Node *a = malloc(sizeof(struct Node));
struct Node *b = malloc(sizeof(struct Node));
a->value = 1; a->next = b;
b->value = 2; b->next = NULL;
printf("%d -> %d\n", a->value, a->next->value);
free(a); free(b);
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(struct Node));
n->value = v;
n->next = NULL;
return n;
}
int main(void) {
struct Node *n = make(5);
printf("%d\n", n->value);
free(n);
return 0;
}小さなリストを作る
ヘルパーを使い、next ポインターをつないで 1 -> 2 -> 3 の3ノードのリストを作ります。
#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);
head->next->next = make(3);
printf("%d %d %d\n", head->value, head->next->value, head->next->next->value);
return 0;
}リストを出力する
すべての値を出力するには、先頭から始め、NULL に到達するまで 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 *head = make(1);
head->next = make(2);
for (struct Node *p = head; p; p = p->next)
printf("%d ", p->value);
printf("\n");
return 0;
}配列と連結リストの比較
配列はインデックスによるアクセスが高速ですが、サイズが固定です。連結リストは要素の挿入や削除が簡単ですが、アクセスは遅くなります（要素に到達するまでたどる必要があるためです）。
プログラムでどの操作が中心になるかに応じて選択してください。
#include <stdio.h>
int main(void) {
printf("Array: O(1) index, costly resize\n");
printf("List: O(n) index, cheap insert/delete\n");
return 0;
}リスト全体を解放する
mallocで確保したすべてのノードを解放する必要があります。リストをたどる際は、各ノードを解放する前に次のポインターを保存してください。そうしないと、チェーンの残りにアクセスできなくなります。
#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 *p = head;
while (p) {
struct Node *nxt = p->next;
free(p);
p = nxt;
}
printf("freed all nodes\n");
return 0;
}クイックチェック
連結リストの構造についての理解度を確認しましょう。
まとめ
単方向連結リストの基本を学びました。
- ノードは値と
nextポインターを保持し、headは最初のノードを指します。 mallocでノードを確保し、->でメンバーにアクセスします。- 最後のノードの
nextはNULLです。ポインターをたどって走査します。 - すべてのノードを必ずfreeし、解放する前に
nextを保存します。
よくある質問
「単方向連結リスト」レッスンは無料ですか？
はい。「単方向連結リスト」の完全なテキストはこのウェブで無料で読めます。インタラクティブに演習し（組み込みコードエディタと24時間対応のAIチューター）、C Academyコースの残りをアンロックするには、CoddyKit PROにアップグレードしてください。 C Academyコースには全4レッスンが含まれています。
「単方向連結リスト」で何を学びますか？
ノードとポインターです。 ブラウザで直接実行するハンズオンコードでC Academyを演習し、24時間対応のAIチューターがレッスンを進める中での質問に答えます。
C Academyを始めるのに経験は必要ですか？
事前経験は必要ありません。CoddyKitのC Academyは初級者から上級者向けに構成されているため、ここから始めるか最初から始めて、自分のペースで進むことができます。 これはレッスン1/4です。
「単方向連結リスト」レッスンにはどのくらい時間がかかりますか？
ほとんどのCoddyKitレッスンは約5～10分かかります。各レッスンはコンパクトでインタラクティブなので、着実に進歩し、ウェブとアプリ全体で正確に前回の場所から再開できます。
このC Academyレッスンでコードを書いて実行できますか？
はい。すべてのC Academyレッスンに組み込みコードエディタが含まれているため、ブラウザでリアルコードを書いて実行し、即座のAIフィードバックを取得できます。ローカル設定は不要です。