はじめに
この記事について
「C言語の基礎を学ぼう」をテーマに、自身の知識 + α をアドベントカレンダーにまとめます。
25日間でC言語をマスターしよう - Qiita Advent Calendar 2025 - Qiita
こんな方を対象としています
-
コンピュータがプログラムをどのように動かしているか知りたい／知らない方
-
プログラミングをしてみたい方
-
C言語初心者の方
キーワード
- リスト
説明
リスト
通常、複数のデータを扱う場合は配列を利用します。
しかし、配列は固定長であるため、要素数がわからない場合の利用には適していません。
可変長の複数のデータを扱う仕組みに リスト があります。
リストは1つのデータを、1つの ノード (node) で管理します。
ノードは下記2つの要素で構成されます。
- データ本体
- 次のノードを指すポインタ
次のノードを追加できるため、可変長を実現できます。
ただし、配列のように連続したメモリ領域ではないため、アクセス時には先頭ノードから辿る必要があり、配列と比較すると低速です。
まとめると下記のようになります。
| 配列 | リスト |
|---|---|
| 固定長 | 可変長 |
| ランダムアクセスが高速 （インデックス指定可能） |
ランダムアクセスが低速 （先頭から辿る必要がある） |
このリストは次のノードのみを指しており、単方向リストと呼ばれることもあります。
さて、次の 練習 でリストを実装します。
練習
1. リストを実装しよう
ノードを追加する list_add() とリストのデータを一覧表示する list_print() 、すべてのノードを削除する list_delete_all() を実装しよう。
int main(void) {
Node *list = NULL;
list_add(&list, 1); // リストを書き換えたいので参照渡し
list_add(&list, 3);
list_add(&list, 9);
list_print(list);
list_delete_all(&list); // すべてfreeした後listをNULLにしたい
return 0;
}
1 3 9
ポイント
ノードは構造体で定義します。
リスト本体はノード先頭を指すポインタとし、初期値は NULL とします。
ノード作成時は malloc() でメモリを確保します。
最後 list_delete_all() で free() を実行します。
解答例
#include <stdio.h>
#include <stdlib.h>
typedef struct Node {
// データ本体
int data;
// 次のNodeを指す
// （typedef解析前なのでstructが必要）
struct Node *next;
} Node;
int list_add(Node **top_p, int add_data);
void list_print(Node *top);
void list_delete_all(Node **top_p);
int main(void) {
Node *list = NULL;
list_add(&list, 1);
list_add(&list, 3);
list_add(&list, 9);
list_print(list);
list_delete_all(&list);
return 0;
}
int list_add(Node **top_p, int add_data) {
Node *last = NULL;
// 新規ノードを作成
Node *new_node = (Node *)malloc(sizeof(Node));
if (new_node == NULL) return 1; // メモリ確保失敗
new_node->data = add_data;
new_node->next = NULL; // 次のノードはない
// リストが空かどうか判定
if (*top_p == NULL) {
// 新しいノードが先頭ノードになる
*top_p = new_node;
return 0;
}
// リストが空でない場合、末尾のノードを探す
last = *top_p;
while (last->next != NULL) {
last = last->next; // 次のノードへ移動
}
// 末尾ノードに新しいノードを繋げる
last->next = new_node;
return 0;
}
void list_print(Node *top) {
if (top == NULL) return;
printf("%d ", top->data);
if (top->next != NULL) {
list_print(top->next); // 次のノードがあれば再帰
}
}
void list_delete_all(Node **top_p) {
Node *current = *top_p;
Node *next_node;
while (current != NULL) {
next_node = current->next; // 解放前に次のノードのアドレスを記憶
free(current);
current = next_node;
}
*top_p = NULL;
}
1 3 9
余裕があれば他にも delete() や filter() などを実装してみましょう。
おわりに
Javaなどの他言語では気軽にリストを使うことができますが、今回は1から作成してみました。
配列とリスト、それぞれのデータ構造を理解した上で、適切な実装ができるとより良いですね。
参考文献
↓↓↓ はじめてプログラミングを学んだときに読んだ本です ↓↓↓
詳細（プログラミング入門 C言語）｜プログラミング｜情報｜実教出版