C・C++の単方向連結リスト
このレッスンでは、CとC++で単方向連結リストを作り、たどり、解放します。
はじめに
単方向連結リスト（singly linked list）はノード（node）の並びで、各ノードは値と次のノードを指すポインタを持っています。配列と違い、ノードはメモリ上で連続している必要がないので、ほかの要素を動かさずに新しい要素を追加できます。
大切なポイント
- 操作を書く前に、データ構造で常に成り立つべき条件（不変条件、invariant）を決めましょう。
- 空のとき、満杯のとき、メモリ確保に失敗したときもきちんと処理しましょう。
- 各操作の計算量とメモリ管理を、あわせて評価しましょう。
動きで理解する
先頭や末尾にノードを追加し、ノードをクリックすると削除できます。再生を押すと、headからNULLまでnextポインタをたどります。
CとC++のコード例
C
main.c
#include <stdio.h>
#include <stdlib.h>
typedef struct Node {
int value;
struct Node *next;
} Node;
int main(void) {
Node *head = NULL;
for (int value = 3; value >= 1; --value) {
Node *node = malloc(sizeof *node);
if (!node) return 1;
*node = (Node){value, head};
head = node;
}
while (head) {
Node *next = head->next;
printf("%d ", head->value);
free(head);
head = next;
}
puts("");
return 0;
}
1 2 3C++
main.cpp
#include <iostream>
#include <memory>
struct Node {
int value;
std::unique_ptr<Node> next;
};
int main() {
std::unique_ptr<Node> head;
for (int value = 3; value >= 1; --value) {
head = std::make_unique<Node>(Node{value, std::move(head)});
}
for (Node *node = head.get(); node; node = node->next.get()) {
std::cout << node->value << ' ';
}
std::cout << '\n';
}
1 2 3CとC++の比較
Cのバージョンでは各ノードをmallocで確保し、使い終わったらリスト全体をたどって各ノードにfreeを呼ぶ必要があります。C++のバージョンではノードがstd::unique_ptrでつながっているので、先頭のノードが破棄されると、その後ろの鎖もすべて自動で解放されます。
C
データ（struct）と操作は分かれていて、メモリは手作業で確保・解放します。
C++
クラスとコンテナが、データの正しさを守り、リソースを自分で管理します。
発展問題
両方のバージョンを実行し、コードを書き換えて、それぞれの言語がもたらす安全性の違いを観察しましょう。
- 空の状態と、容量の上限に達したときのテストを追加しましょう。
- メモリを解放する処理を書き、メモリリークがないか確認しましょう。
- 標準ライブラリの対応するコンテナと計算量を比べましょう。
チャレンジで練習する
このレッスンの内容を使って実際の問題を解きましょう。各チャレンジはブラウザで動き、すぐにテストされ、AI のレビューも受けられます。
すべてのチャレンジ