第6章：データ構造の理論と連結リストの実装
6.1 データ構造の歴史と理論的基盤
6.1.1 データ構造の誕生 - 計算機科学の夜明け
コンピュータプログラミングの初期、データは単純な配列や変数として扱われていた。しかし、より複雑な問題を解決するために、データの組織化方法を体系的に研究する必要が生じた。
LISP と動的データ構造の革命（1958年）
John McCarthyが開発したLISPは、データ構造の歴史において革命的だった。LISPの名前自体が「List Processing」の略であり、連結リストはその核心にあった。
; LISPにおけるリスト表現
(1 2 3 4 5)
; 内部的にはコンスセルの連鎖
; (1 . (2 . (3 . (4 . (5 . NIL)))))
; car（最初の要素）とcdr（残り）
(car '(1 2 3)) ; => 1
(cdr '(1 2 3)) ; => (2 3)
LISPのコンスセル（cons cell）は、現代の連結リストノードの直接の祖先：
リスト (1 2 3) の内部表現：
なぜ連結リストが必要だったのか
- 動的サイズ: 実行時にサイズが変化するデータを扱う
- 効率的な挿入・削除: 要素の移動なしに操作可能
- メモリの効率的使用: 必要な分だけ確保
- 再帰的処理との親和性: 関数型言語の本質
6.1.2 抽象データ型（ADT）の理論
Barbara Liskovが1970年代に形式化した抽象データ型（Abstract Data Type）の概念は、データ構造を理解する上で根本的に重要。
ADTの定義
抽象データ型は以下で構成される：
- 値の集合（ドメイン）
- 操作の集合
- 公理（操作の振る舞いを定義する規則）
リストADTの形式的定義：
Domain: List<T> = Empty | Cons(T, List<T>)
Operations:
- new() → List<T>
- add_front(List<T>, T) → List<T>
- head(List<T>) → T
- tail(List<T>) → List<T>
- is_empty(List<T>) → Boolean
- size(List<T>) → Integer
Axioms:
- head(Cons(x, xs)) = x
- tail(Cons(x, xs)) = xs
- is_empty(Empty) = true
- is_empty(Cons(x, xs)) = false
- size(Empty) = 0
- size(Cons(x, xs)) = 1 + size(xs)
ADTと実装の分離
抽象データ型の美点は、インターフェースと実装を分離すること：
/* 抽象インターフェース（ユーザーが見る） */
typedef struct s_list t_list;
t_list *ft_lstnew(void *content);
void ft_lstadd_front(t_list **lst, t_list *new);
int ft_lstsize(t_list *lst);
/* ... */
/* 実装詳細（内部に隠蔽可能） */
struct s_list {
void *content;
struct s_list *next;
};
/*
* ユーザーは内部構造を知らなくても使用可能
* 実装を変更しても、インターフェースが同じなら影響なし
*/
情報隠蔽の原則
David Parnasが1972年に提唱した情報隠蔽（Information Hiding）は、ADTの実装に不可欠：
/* 不透明なポインタを使った情報隠蔽 */
/* list.h - 公開ヘッダ */
typedef struct s_list_impl *t_list_handle; /* 不透明型 */
t_list_handle list_create(void);
void list_destroy(t_list_handle list);
int list_add(t_list_handle list, void *item);
void *list_get(t_list_handle list, int index);
/* list.c - 実装ファイル */
struct s_list_impl {
void **items;
size_t size;
size_t capacity;
/* 実装詳細は外部から見えない */
};
6.1.3 計算量理論の基礎
アルゴリズムとデータ構造を評価するには、計算量理論の理解が不可欠。
Big-O記法の起源
Big-O記法は、1894年にドイツの数学者Paul Bachmannが導入し、Edmund Landauが普及させた。本来は数論の記法だったが、Donald Knuthがコンピュータ科学に適用した。
Big-O の形式的定義：
f(n) = O(g(n)) ⟺ ∃c > 0, n₀ > 0 such that
∀n ≥ n₀: f(n) ≤ c · g(n)
つまり、十分大きなnに対して、f(n)はg(n)の定数倍以下で抑えられる
計算量のクラス
一般的な計算量クラス（増加順）：
O(1) - 定数時間（配列のインデックスアクセス）
O(log n) - 対数時間（二分探索）
O(n) - 線形時間（配列の走査）
O(n log n) - 準線形時間（効率的なソート）
O(n²) - 二乗時間（単純なソート）
O(2ⁿ) - 指数時間（総当たり）
O(n!) - 階乗時間（順列の列挙）
n = 1,000,000 での概算:
| 計算量 | 操作数（概算） |
|:-------|:---------------|
| O(1) | 1 |
| O(log n) | 20 |
| O(n) | 1,000,000 |
| O(n log n) | 20,000,000 |
| O(n²) | 1,000,000,000,000 |
| O(2ⁿ) | 宇宙の寿命より長い |
漸近解析の実践
/*
* 計算量解析の例
*/
/* O(1) - 定数時間 */
void *get_first(t_list *lst)
{
if (!lst) /* 1 操作 */
return NULL; /* 1 操作 */
return lst->content; /* 1 操作 */
/* 合計: 3操作 → O(1) */
}
/* O(n) - 線形時間 */
int ft_lstsize(t_list *lst)
{
int count = 0; /* 1 操作 */
while (lst) /* n 回のループ */
{
count++; /* n 操作 */
lst = lst->next; /* n 操作 */
}
return count; /* 1 操作 */
/* 合計: 2n + 2 操作 → O(n) */
}
/* O(n²) - 二乗時間（悪い例） */
void bad_add_all_to_back(t_list **lst, t_list *items)
{
while (items)
{
/* ft_lstadd_back は O(n)（毎回リスト末尾を探索） */
ft_lstadd_back(lst, ft_lstnew(items->content));
items = items->next;
}
/* n 回 × O(n) = O(n²) */
}
/* O(n) - 線形時間（良い例） */
void good_add_all_to_back(t_list **lst, t_list *items)
{
t_list *tail = ft_lstlast(*lst); /* 1回だけ O(n) */
while (items) /* n 回のループ */
{
t_list *new = ft_lstnew(items->content);
if (!*lst)
{
*lst = new;
tail = new;
}
else
{
tail->next = new; /* O(1) */
tail = new;
}
items = items->next;
}
/* O(n) + n × O(1) = O(n) */
}
償却計算量（Amortized Analysis）
単一操作のコストだけでなく、操作のシーケンス全体のコストを考える：
/*
* 動的配列の償却解析
*
* 挿入時に容量が足りなければ2倍に拡張
*/
typedef struct s_dynamic_array {
void **items;
size_t size;
size_t capacity;
} t_dynamic_array;
void array_push(t_dynamic_array *arr, void *item)
{
/* 容量が足りない場合、拡張（O(n)） */
if (arr->size >= arr->capacity) {
arr->capacity *= 2;
arr->items = realloc(arr->items,
arr->capacity * sizeof(void *));
/* n 要素をコピー */
}
arr->items[arr->size++] = item; /* O(1) */
}
/*
* 最悪ケース: O(n) （拡張時）
* 平均ケース: O(1) （拡張なし）
*
* 償却解析：
* n 回の挿入で、拡張は log₂(n) 回発生
* 各拡張でコピーされる合計: 1 + 2 + 4 + ... + n ≈ 2n
* n 回の挿入 + 2n 回のコピー = 3n 操作
*
* 1回あたりの償却コスト: 3n / n = O(1)
*/
6.1.4 配列と連結リストの比較
メモリレイアウトの違い
配列のメモリレイアウト：
*連続したメモリ領域 (ランダムアクセス O(1))*
連結リストのメモリレイアウト：
*任意のアドレスに散在 (シーケンシャルアクセス O(n))*
操作別の計算量比較
┌────────────────────┬───────────┬──────────────┐
│ 操作 │ 配列 │ 連結リスト │
├────────────────────┼───────────┼──────────────┤
│ インデックスアクセス│ O(1) │ O(n) │
│ 先頭への挿入 │ O(n) │ O(1) │
│ 末尾への挿入 │ O(1)* │ O(n)† │
│ 中間への挿入 │ O(n) │ O(1)‡ │
│ 先頭の削除 │ O(n) │ O(1) │
│ 末尾の削除 │ O(1) │ O(n) │
│ 中間の削除 │ O(n) │ O(1)‡ │
│ 検索 │ O(n) │ O(n) │
│ メモリ使用量 │ n×size │ n×(size+ptr) │
└────────────────────┴───────────┴──────────────┘
* 動的配列で償却O(1)
† 末尾ポインタを保持すればO(1)
‡ 挿入・削除位置が既知の場合
キャッシュ効率の考慮
/*
* 現代のCPUでは、メモリアクセスパターンが重要
*
* 配列：優れたキャッシュ局所性
* - 連続アクセスでプリフェッチが効く
* - キャッシュラインを効率的に使用
*
* 連結リスト：キャッシュ効率が低い
* - ノードがメモリ上に散在
* - ポインタ追跡でキャッシュミスが発生
*/
/* ベンチマーク例 */
void benchmark_sequential_access(void)
{
int array[1000000];
t_list *list = create_list_with_n_elements(1000000);
/* 配列の走査：非常に高速（キャッシュフレンドリー） */
clock_t start = clock();
long sum = 0;
for (int i = 0; i < 1000000; i++)
sum += array[i];
clock_t array_time = clock() - start;
/* リストの走査：配列より遅い（ポインタ追跡） */
start = clock();
sum = 0;
t_list *curr = list;
while (curr) {
sum += *(int *)curr->content;
curr = curr->next;
}
clock_t list_time = clock() - start;
/* 典型的な結果：リストは配列の5-10倍遅い */
}
6.2 ポインタと参照の理論
6.2.1 間接参照の数学的モデル
ポインタは、メモリアドレスという「名前」から「値」への関数として理解できる。
ポインタの理論的モデル：
Memory: Address → Value
Pointer: Variable → Address
Dereference: *p = Memory(Pointer(p))
間接参照のレベル
/*
* ポインタのポインタ（ダブルポインタ）
*
* ft_lstadd_front が **lst を取る理由の理解
*/
void explain_double_pointer(void)
{
int x = 42;
int *p = &x; /* p は x のアドレスを保持 */
int **pp = &p; /* pp は p のアドレスを保持 */
printf("x = %d\n", x); /* 42 */
printf("*p = %d\n", *p); /* 42 */
printf("**pp = %d\n", **pp); /* 42 */
}
/*
* メモリレイアウト：
*
* */
6.2.2 なぜダブルポインタが必要か
/*
* シングルポインタでの問題点
*/
/* 動作しない実装 */
void broken_add_front(t_list *lst, t_list *new)
{
new->next = lst;
lst = new; /* ローカル変数を変更するだけ！ */
/* 呼び出し元の変数は変更されない */
}
void demonstrate_broken(void)
{
t_list *head = NULL;
t_list *node = ft_lstnew("Hello");
broken_add_front(head, node);
printf("head = %p\n", head); /* まだ NULL */
}
/*
* 関数呼び出しのメカニズム：
*
* 呼び出し前：
* head: NULL (アドレス 0x1000)
*
* broken_add_front 内：
* lst: NULL (アドレス 0x2000) ← headのコピー
*
* lst = new で変更されるのは 0x2000 番地
* 0x1000 番地（元のhead）は変更されない
*/
/* 正しい実装 */
void ft_lstadd_front(t_list **lst, t_list *new)
{
if (!lst || !new)
return;
new->next = *lst; /* 現在の先頭を保存 */
*lst = new; /* 先頭を更新（呼び出し元のheadを変更） */
}
void demonstrate_correct(void)
{
t_list *head = NULL;
t_list *node = ft_lstnew("Hello");
ft_lstadd_front(&head, node);
printf("head = %p\n", head); /* nodeのアドレス */
}
/*
* 呼び出し前：
* head: NULL (アドレス 0x1000)
*
* ft_lstadd_front 内：
* lst: 0x1000 (アドレス 0x2000) ← headのアドレス
*
* *lst = new で変更されるのは 0x1000 番地
* 呼び出し元の head が直接変更される
*/
ダブルポインタが必要な操作
/*
* ポインタ自体を変更する必要がある操作：
* - 先頭への追加（headポインタの変更）
* - 先頭の削除（headポインタの変更）
* - リスト全体の削除（headをNULLに）
*/
/* 先頭の削除 */
void *lst_pop_front(t_list **lst)
{
if (!lst || !*lst)
return NULL;
t_list *first = *lst;
void *content = first->content;
*lst = first->next; /* headを更新 */
free(first);
return content;
}
/* リストの反転 */
void lst_reverse(t_list **lst)
{
t_list *prev = NULL;
t_list *current = *lst;
t_list *next;
while (current)
{
next = current->next;
current->next = prev;
prev = current;
current = next;
}
*lst = prev; /* headを新しい先頭に更新 */
}
6.2.3 自己参照構造体の理論
構造体が自身へのポインタをメンバとして持つことで、再帰的なデータ構造が可能になる。
/*
* 自己参照構造体の宣言
*
* 重要：型名は完全な定義の前に使用できない
* しかし、ポインタは不完全な型でも宣言可能
*/
/* 正しい宣言 */
typedef struct s_list
{
void *content;
struct s_list *next; /* struct s_list は既知 */
} t_list;
/* コンパイルエラーになる例 */
/*
typedef struct s_list
{
void *content;
t_list *next; // エラー！ t_list はまだ未定義
} t_list;
*/
/* 前方宣言を使う方法 */
typedef struct s_list t_list;
struct s_list
{
void *content;
t_list *next; /* OK：t_list は前方宣言済み */
};
相互参照構造体
/*
* 相互に参照し合う構造体
*/
/* 前方宣言 */
typedef struct s_parent t_parent;
typedef struct s_child t_child;
struct s_parent
{
char *name;
t_child *first_child;
};
struct s_child
{
char *name;
t_parent *parent;
t_child *sibling;
};
/*
* 木構造やグラフなど、複雑なデータ構造に必要
*/
6.3 再帰的データ構造と再帰的処理
6.3.1 再帰の数学的基礎
再帰は数学的帰納法と密接に関連している。
帰納的定義（Inductive Definition）
自然数の帰納的定義：
Base case: 0 は自然数
Inductive case: n が自然数なら、succ(n) も自然数
リストの帰納的定義：
Base case: Empty は List
Inductive case: x が要素、xs が List なら、Cons(x, xs) も List
これらの定義は、再帰的操作の構造を自然に導く
再帰的処理の構造
/*
* 再帰的定義に対応した再帰的関数
*/
/* リストの長さ（再帰版） */
int list_length(t_list *lst)
{
/* Base case: 空リストの長さは0 */
if (!lst)
return 0;
/* Inductive case: 先頭 + 残りの長さ */
return 1 + list_length(lst->next);
}
/*
* 証明：この関数が正しいことの帰納法による証明
*
* Base case: lst == NULL のとき、0を返す ✓
*
* Inductive step:
* 仮定：list_length(lst->next) が残りの長さを正しく返す
* ならば：1 + list_length(lst->next) は全体の長さを正しく返す ✓
*/
6.3.2 末尾再帰最適化
/*
* 通常の再帰：スタックを消費
*/
int list_sum(t_list *lst)
{
if (!lst)
return 0;
return *(int *)lst->content + list_sum(lst->next);
/* ↑ この位置で加算が必要なため、フレームを保持 */
}
/*
* 呼び出しスタック（リスト [1, 2, 3] の場合）：
*
* list_sum([1,2,3])
* → 1 + list_sum([2,3])
* → 2 + list_sum([3])
* → 3 + list_sum([])
* → 0
* ← 3 + 0 = 3
* ← 2 + 3 = 5
* ← 1 + 5 = 6
*
* 3つのスタックフレームが同時に存在
*/
/*
* 末尾再帰：スタック消費なし（最適化可能）
*/
static int list_sum_helper(t_list *lst, int accumulator)
{
if (!lst)
return accumulator;
/* 末尾位置での再帰呼び出し */
return list_sum_helper(lst->next,
accumulator + *(int *)lst->content);
}
int list_sum_tail(t_list *lst)
{
return list_sum_helper(lst, 0);
}
/*
* 末尾呼び出し最適化（TCO）：
*
* コンパイラは末尾再帰をループに変換可能
*
* list_sum_helper([1,2,3], 0)
* → list_sum_helper([2,3], 1)
* → list_sum_helper([3], 3)
* → list_sum_helper([], 6)
* → 6
*
* 各呼び出しで前のフレームは不要なため、
* スタックフレームを再利用できる
*/
/*
* 注意：C言語ではTCO が保証されない
* -O2 以上の最適化で有効になる場合が多い
* 確実を期すなら明示的にループを使用
*/
6.3.3 再帰から反復への変換
/*
* 再帰と反復は等価（チューリング完全）
* 任意の再帰は反復に変換可能
*/
/* 再帰版：リストの探索 */
t_list *list_find_recursive(t_list *lst, void *target,
int (*cmp)(void *, void *))
{
if (!lst)
return NULL;
if (cmp(lst->content, target) == 0)
return lst;
return list_find_recursive(lst->next, target, cmp);
}
/* 反復版：同じ処理 */
t_list *list_find_iterative(t_list *lst, void *target,
int (*cmp)(void *, void *))
{
while (lst)
{
if (cmp(lst->content, target) == 0)
return lst;
lst = lst->next;
}
return NULL;
}
/*
* より複雑な再帰の変換：
* 明示的なスタックを使用
*/
/* 再帰版：木の走査 */
typedef struct s_tree {
void *value;
struct s_tree *left;
struct s_tree *right;
} t_tree;
void tree_preorder_recursive(t_tree *node, void (*f)(void *))
{
if (!node)
return;
f(node->value);
tree_preorder_recursive(node->left, f);
tree_preorder_recursive(node->right, f);
}
/* 反復版：明示的スタック */
void tree_preorder_iterative(t_tree *root, void (*f)(void *))
{
if (!root)
return;
/* スタックとして連結リストを使用 */
t_list *stack = NULL;
ft_lstadd_front(&stack, ft_lstnew(root));
while (stack)
{
/* pop */
t_tree *node = (t_tree *)stack->content;
t_list *old = stack;
stack = stack->next;
free(old);
f(node->value);
/* 右を先にpush（左を先に処理するため） */
if (node->right)
ft_lstadd_front(&stack, ft_lstnew(node->right));
if (node->left)
ft_lstadd_front(&stack, ft_lstnew(node->left));
}
}
6.4 連結リストの変種
6.4.1 双方向連結リスト
/*
* 双方向連結リスト：前後両方向に移動可能
*/
typedef struct s_dlist {
void *content;
struct s_dlist *next;
struct s_dlist *prev;
} t_dlist;
/*
* 構造：
*
* NULL ← [A] ⟷ [B] ⟷ [C] ⟷ [D] → NULL
*
* 利点：
* - 逆方向の走査が可能
* - 任意のノードから両隣にアクセス可能
* - 末尾からの削除が O(1)
*
* 欠点：
* - 各ノードで追加のポインタ（メモリ消費）
* - 挿入・削除でより多くのポインタ操作
*/
/* 双方向リストへの挿入 */
void dlist_insert_after(t_dlist *node, t_dlist *new)
{
if (!node || !new)
return;
new->prev = node;
new->next = node->next;
if (node->next)
node->next->prev = new;
node->next = new;
}
/* 双方向リストからの削除 */
void dlist_remove(t_dlist *node)
{
if (!node)
return;
if (node->prev)
node->prev->next = node->next;
if (node->next)
node->next->prev = node->prev;
/* node 自体は解放しない（呼び出し側の責任） */
}
6.4.2 循環連結リスト
/*
* 循環連結リスト：最後のノードが最初のノードを指す
*/
/*
* 構造：
*
* *
* 用途：
* - ラウンドロビンスケジューリング
* - 循環バッファ
* - 無限ループ処理
*/
/* 循環リストの作成 */
void make_circular(t_list *lst)
{
if (!lst)
return;
t_list *last = ft_lstlast(lst);
last->next = lst;
}
/* 循環リストの走査 */
void circular_list_iter(t_list *start, void (*f)(void *), int max_iter)
{
t_list *current = start;
int count = 0;
if (!start)
return;
do {
f(current->content);
current = current->next;
count++;
} while (current != start && count < max_iter);
}
/* 循環リストのサイズ（循環を考慮） */
int circular_list_size(t_list *start)
{
t_list *current;
int count;
if (!start)
return 0;
current = start;
count = 0;
do {
count++;
current = current->next;
} while (current != start);
return count;
}
6.4.3 センチネルノード
/*
* センチネル（番兵）ノード：境界条件を単純化
*/
typedef struct s_sentinel_list {
t_list sentinel; /* ダミーノード（実データなし） */
} t_sentinel_list;
/*
* 構造：
*
* *Sentinelは常に存在*
*
* 利点：
* - head == NULL のチェックが不要
* - 先頭への挿入・削除が特殊ケースにならない
*/
t_sentinel_list *sentinel_list_new(void)
{
t_sentinel_list *list = malloc(sizeof(t_sentinel_list));
if (!list)
return NULL;
list->sentinel.content = NULL;
list->sentinel.next = NULL;
return list;
}
/* センチネルを使った挿入（先頭/中間が同じコード） */
void sentinel_insert_after(t_list *node, void *content)
{
t_list *new = ft_lstnew(content);
if (!new)
return;
new->next = node->next;
node->next = new;
}
void sentinel_add_front(t_sentinel_list *list, void *content)
{
/* センチネルの直後に挿入 */
sentinel_insert_after(&list->sentinel, content);
}
/* 最初の実データノードを取得 */
t_list *sentinel_get_first(t_sentinel_list *list)
{
return list->sentinel.next;
}
6.5 libft連結リスト関数の実装
6.5.1 ft_lstnew - 新しいノードの作成
/*
* ft_lstnew - 新しいリストノードを作成
*
* @content: ノードに格納するデータ
* @return: 新しいノード、失敗時NULL
*
* 設計上の決定：
* - contentのコピーではなく、ポインタを保存
* - 所有権は呼び出し元が管理
*/
t_list *ft_lstnew(void *content)
{
t_list *new_node;
new_node = (t_list *)malloc(sizeof(t_list));
if (!new_node)
return (NULL);
new_node->content = content;
new_node->next = NULL;
return (new_node);
}
/*
* メモリレイアウト：
*
* malloc で確保された領域：
* ┌─────────────────────────────┐
* │ content: (contentのアドレス)│
* │ next: NULL │
* └─────────────────────────────┘
*
* content が指すデータは別のメモリ領域
*/
6.5.2 ft_lstadd_front - リストの先頭に追加
/*
* ft_lstadd_front - リストの先頭に新しいノードを追加
*
* @lst: リストのヘッドポインタへのポインタ
* @new: 追加するノード
*
* ダブルポインタの理由：headポインタ自体を変更するため
*/
void ft_lstadd_front(t_list **lst, t_list *new)
{
if (!lst || !new)
return;
new->next = *lst;
*lst = new;
}
/*
* 操作の可視化：
*
* 呼び出し前：
*
実行後：
*
* 計算量: O(1)
*/
6.5.3 ft_lstsize - リストのサイズを取得
/*
* ft_lstsize - リスト内のノード数を返す
*
* @lst: リストの先頭ノード
* @return: ノード数
*/
int ft_lstsize(t_list *lst)
{
int count;
count = 0;
while (lst)
{
count++;
lst = lst->next;
}
return (count);
}
/*
* 計算量: O(n) - 全ノードを走査
*
* 注意：頻繁にサイズが必要な場合、
* ラッパー構造体でサイズをキャッシュすることを検討
*/
6.5.4 ft_lstlast - 最後のノードを取得
/*
* ft_lstlast - リストの最後のノードを返す
*
* @lst: リストの先頭ノード
* @return: 最後のノード、空リストならNULL
*/
t_list *ft_lstlast(t_list *lst)
{
if (!lst)
return (NULL);
while (lst->next)
lst = lst->next;
return (lst);
}
/*
* 計算量: O(n) - 最後まで走査
*
* 末尾への追加を頻繁に行う場合、
* 末尾ポインタを保持する構造を検討
*/
6.5.5 ft_lstadd_back - リストの末尾に追加
/*
* ft_lstadd_back - リストの末尾に新しいノードを追加
*
* @lst: リストのヘッドポインタへのポインタ
* @new: 追加するノード
*/
void ft_lstadd_back(t_list **lst, t_list *new)
{
t_list *last;
if (!lst || !new)
return;
if (!*lst)
{
*lst = new;
return;
}
last = ft_lstlast(*lst);
last->next = new;
}
/*
* 計算量: O(n) - ft_lstlastの呼び出し
*
* 操作の可視化：
空リストの場合：
既存リストの場合：
*/
6.5.6 ft_lstdelone - 単一ノードの削除
/*
* ft_lstdelone - 単一ノードを削除
*
* @lst: 削除するノード
* @del: contentを解放する関数
*
* 注意：nextは解放しない（呼び出し側がリンクを管理）
*/
void ft_lstdelone(t_list *lst, void (*del)(void *))
{
if (!lst)
return;
if (del && lst->content)
del(lst->content);
free(lst);
}
/*
* 典型的な削除関数：
*/
/* 単純なfree */
void del_free(void *content)
{
free(content);
}
/* 何もしない（静的データや外部管理データ用） */
void del_nothing(void *content)
{
(void)content;
}
/* 構造体の深い解放 */
typedef struct s_user {
char *name;
char *email;
} t_user;
void del_user(void *content)
{
t_user *user = (t_user *)content;
if (user)
{
free(user->name);
free(user->email);
free(user);
}
}
6.5.7 ft_lstclear - リスト全体の削除
/*
* ft_lstclear - リスト全体を削除
*
* @lst: リストのヘッドポインタへのポインタ
* @del: contentを解放する関数
*
* すべてのノードを削除し、*lstをNULLに設定
*/
void ft_lstclear(t_list **lst, void (*del)(void *))
{
t_list *current;
t_list *next;
if (!lst || !*lst)
return;
current = *lst;
while (current)
{
next = current->next;
ft_lstdelone(current, del);
current = next;
}
*lst = NULL;
}
/*
* 重要なパターン：
*
* current = *lst;
* while (current)
* {
* next = current->next; // 次を保存してから
* // currentを解放 // 解放
* current = next; // 次に移動
* }
*
* nextを先に保存しないと、解放後に
* current->next にアクセスできない
*/
6.5.8 ft_lstiter - リストの反復処理
/*
* ft_lstiter - リストの各要素に関数を適用
*
* @lst: リストの先頭
* @f: 各contentに適用する関数
*
* リスト構造は変更しない
*/
void ft_lstiter(t_list *lst, void (*f)(void *))
{
if (!f)
return;
while (lst)
{
f(lst->content);
lst = lst->next;
}
}
/*
* 使用例：
*/
void print_string(void *content)
{
printf("%s\n", (char *)content);
}
void print_int(void *content)
{
printf("%d\n", *(int *)content);
}
void double_int(void *content)
{
int *num = (int *)content;
*num *= 2; /* contentを変更 */
}
void example_lstiter(void)
{
t_list *list = NULL;
int nums[] = {1, 2, 3, 4, 5};
/* リストを作成 */
for (int i = 0; i < 5; i++)
ft_lstadd_back(&list, ft_lstnew(&nums[i]));
printf("Before:\n");
ft_lstiter(list, print_int); /* 1 2 3 4 5 */
ft_lstiter(list, double_int); /* 各要素を2倍 */
printf("After:\n");
ft_lstiter(list, print_int); /* 2 4 6 8 10 */
ft_lstclear(&list, NULL);
}
6.5.9 ft_lstmap - リストの変換
/*
* ft_lstmap - 各要素に関数を適用した新しいリストを作成
*
* @lst: 元のリスト
* @f: 各contentに適用する変換関数
* @del: エラー時にcontentを解放する関数
* @return: 新しいリスト、エラー時NULL
*
* 関数型プログラミングの「map」操作に相当
*/
t_list *ft_lstmap(t_list *lst, void *(*f)(void *), void (*del)(void *))
{
t_list *new_list;
t_list *new_node;
void *new_content;
if (!f || !del)
return (NULL);
new_list = NULL;
while (lst)
{
/* 変換関数を適用 */
new_content = f(lst->content);
if (!new_content)
{
ft_lstclear(&new_list, del);
return (NULL);
}
/* 新しいノードを作成 */
new_node = ft_lstnew(new_content);
if (!new_node)
{
del(new_content);
ft_lstclear(&new_list, del);
return (NULL);
}
ft_lstadd_back(&new_list, new_node);
lst = lst->next;
}
return (new_list);
}
/*
* 使用例：
*/
void *string_to_upper(void *content)
{
char *str = (char *)content;
char *upper = ft_strdup(str);
if (!upper)
return NULL;
for (int i = 0; upper[i]; i++)
upper[i] = ft_toupper(upper[i]);
return upper;
}
void example_lstmap(void)
{
t_list *original = NULL;
t_list *uppercase;
/* 元のリスト作成 */
ft_lstadd_back(&original, ft_lstnew(ft_strdup("hello")));
ft_lstadd_back(&original, ft_lstnew(ft_strdup("world")));
/* 大文字に変換した新リスト作成 */
uppercase = ft_lstmap(original, string_to_upper, free);
/* 結果を出力 */
ft_lstiter(uppercase, print_string); /* HELLO WORLD */
/* クリーンアップ */
ft_lstclear(&original, free);
ft_lstclear(&uppercase, free);
}
6.6 高度な連結リスト操作
6.6.1 リストの反転
/*
* リストの反転（インプレース）
*
* 計算量: O(n) 時間, O(1) 空間
*/
t_list *ft_lstrev(t_list *lst)
{
t_list *prev;
t_list *current;
t_list *next;
prev = NULL;
current = lst;
while (current)
{
next = current->next; /* 次を保存 */
current->next = prev; /* 向きを反転 */
prev = current; /* prevを進める */
current = next; /* currentを進める */
}
return (prev);
}
/*
* 操作の可視化：
*
* 初期状態：
* prev=NULL current=[1]→[2]→[3]→NULL
*
* ステップ1：
* NULL←[1] current=[2]→[3]→NULL
* ↑prev
*
* ステップ2：
* NULL←[1]←[2] current=[3]→NULL
* ↑prev
*
* ステップ3：
* NULL←[1]←[2]←[3] current=NULL
* ↑prev
*
* 結果：prev が新しい先頭
*/
6.6.2 マージソート
/*
* 連結リストのマージソート
*
* 計算量: O(n log n) 時間, O(log n) 空間（再帰スタック）
*/
/* リストを2つに分割 */
static t_list *split_list(t_list *head)
{
t_list *slow;
t_list *fast;
t_list *mid;
slow = head;
fast = head->next;
/* fast が末尾に到達したとき、slowは中間 */
while (fast && fast->next)
{
slow = slow->next;
fast = fast->next->next;
}
mid = slow->next;
slow->next = NULL; /* 前半を切断 */
return (mid);
}
/* 2つのソート済みリストをマージ */
static t_list *merge_sorted(t_list *a, t_list *b,
int (*cmp)(void *, void *))
{
t_list dummy;
t_list *tail;
dummy.next = NULL;
tail = &dummy;
while (a && b)
{
if (cmp(a->content, b->content) <= 0)
{
tail->next = a;
a = a->next;
}
else
{
tail->next = b;
b = b->next;
}
tail = tail->next;
}
/* 残りを連結 */
tail->next = a ? a : b;
return (dummy.next);
}
/* マージソート本体 */
t_list *ft_lstsort(t_list *lst, int (*cmp)(void *, void *))
{
t_list *second_half;
/* ベースケース：0または1要素 */
if (!lst || !lst->next)
return (lst);
/* 分割 */
second_half = split_list(lst);
/* 再帰的にソート */
lst = ft_lstsort(lst, cmp);
second_half = ft_lstsort(second_half, cmp);
/* マージ */
return (merge_sorted(lst, second_half, cmp));
}
/*
* 比較関数の例
*/
int cmp_int(void *a, void *b)
{
return (*(int *)a - *(int *)b);
}
int cmp_string(void *a, void *b)
{
return (ft_strcmp((char *)a, (char *)b));
}
6.6.3 循環検出（フロイドのアルゴリズム）
/*
* フロイドの循環検出アルゴリズム（亀とウサギ）
*
* 計算量: O(n) 時間, O(1) 空間
*/
int ft_lsthas_cycle(t_list *lst)
{
t_list *slow;
t_list *fast;
slow = lst;
fast = lst;
while (fast && fast->next)
{
slow = slow->next; /* 1歩進む */
fast = fast->next->next; /* 2歩進む */
if (slow == fast)
return (1); /* 循環を検出 */
}
return (0); /* 循環なし */
}
/*
* なぜこれが機能するか：
*
* 循環がある場合：
* - fastはslowより早く循環に入る
* - 循環内で、fastはslowに1歩ずつ近づく
* - 最終的に同じノードで出会う
*
* 循環がない場合：
* - fastは末尾（NULL）に到達してループ終了
*/
/* 循環の開始点を見つける */
t_list *ft_lstfind_cycle_start(t_list *lst)
{
t_list *slow;
t_list *fast;
slow = lst;
fast = lst;
/* 循環を検出 */
while (fast && fast->next)
{
slow = slow->next;
fast = fast->next->next;
if (slow == fast)
break;
}
if (!fast || !fast->next)
return (NULL); /* 循環なし */
/* slowを先頭に戻し、両方を1歩ずつ進める */
slow = lst;
while (slow != fast)
{
slow = slow->next;
fast = fast->next;
}
return (slow); /* 循環の開始点 */
}
/*
* なぜこれが機能するか（数学的証明）：
*
* 設定：
* - リストの先頭から循環開始点までの距離 = m
* - 循環の長さ = n
* - 出会った点から循環開始点までの距離（逆向き）= k
*
* 出会った時点：
* - slowの移動距離 = m + k
* - fastの移動距離 = m + k + p*n （p周回）
* - fastはslowの2倍移動：2(m + k) = m + k + p*n
* - よって：m + k = p*n
* - よって：m = p*n - k = (p-1)*n + (n-k)
*
* これは「m歩進むと循環開始点に到達」を意味する
* 出会った点からn-k歩進んでも循環開始点に到達
* 両者を同時に1歩ずつ進めると、循環開始点で出会う
*/
6.7 メモリ管理のベストプラクティス
6.7.1 所有権モデル
/*
* 所有権の3つのパターン
*/
/* パターン1：リストがcontentを所有 */
typedef struct s_owning_list {
t_list *head;
void (*destructor)(void *);
} t_owning_list;
void owning_list_add(t_owning_list *list, void *content)
{
t_list *node = ft_lstnew(content);
ft_lstadd_front(&list->head, node);
/* list がcontentの所有権を取得 */
}
void owning_list_clear(t_owning_list *list)
{
ft_lstclear(&list->head, list->destructor);
/* すべてのcontentを解放 */
}
/* パターン2：リストはcontentを借用 */
typedef struct s_borrowing_list {
t_list *head;
} t_borrowing_list;
void borrowing_list_add(t_borrowing_list *list, void *content)
{
t_list *node = ft_lstnew(content);
ft_lstadd_front(&list->head, node);
/* contentの所有権は呼び出し元に残る */
}
void borrowing_list_clear(t_borrowing_list *list)
{
ft_lstclear(&list->head, NULL); /* ノードのみ解放 */
/* contentは解放しない */
}
/* パターン3：リストがcontentをコピー */
typedef struct s_copying_list {
t_list *head;
void *(*copy)(void *);
void (*destructor)(void *);
} t_copying_list;
void copying_list_add(t_copying_list *list, void *content)
{
void *copy = list->copy(content);
t_list *node = ft_lstnew(copy);
ft_lstadd_front(&list->head, node);
/* listが所有する独立したコピー */
}
6.7.2 安全なイテレータパターン
/*
* イテレータ：リストの走査を抽象化
*/
typedef struct s_list_iterator {
t_list *current;
t_list *next; /* 削除を安全にするため */
} t_list_iterator;
t_list_iterator list_iter_begin(t_list *list)
{
t_list_iterator iter;
iter.current = list;
iter.next = list ? list->next : NULL;
return iter;
}
int list_iter_has_next(t_list_iterator *iter)
{
return iter->current != NULL;
}
void *list_iter_next(t_list_iterator *iter)
{
void *content;
if (!iter->current)
return NULL;
content = iter->current->content;
iter->current = iter->next;
iter->next = iter->current ? iter->current->next : NULL;
return content;
}
/* 安全なイテレーション（削除も可能） */
void safe_iteration_example(t_list **list, int (*should_remove)(void *))
{
t_list *prev = NULL;
t_list_iterator iter = list_iter_begin(*list);
while (list_iter_has_next(&iter))
{
t_list *current = iter.current;
void *content = list_iter_next(&iter);
if (should_remove(content))
{
if (prev)
prev->next = current->next;
else
*list = current->next;
ft_lstdelone(current, free);
}
else
{
prev = current;
}
}
}
6.8 パフォーマンス最適化
6.8.1 メモリプールの活用
/*
* ノード用のメモリプール
*
* 頻繁な小さなmallocを避けて性能向上
*/
#define POOL_BLOCK_SIZE 64
typedef struct s_node_pool {
t_list *free_list;
void *blocks; /* 割り当てたブロックのリスト */
size_t total_nodes;
} t_node_pool;
t_node_pool *node_pool_create(void)
{
t_node_pool *pool = malloc(sizeof(t_node_pool));
if (!pool)
return NULL;
pool->free_list = NULL;
pool->blocks = NULL;
pool->total_nodes = 0;
return pool;
}
/* 新しいブロックを割り当て */
static int pool_grow(t_node_pool *pool)
{
/* ノードのブロックを割り当て */
t_list *block = malloc(sizeof(t_list) * POOL_BLOCK_SIZE);
if (!block)
return -1;
/* フリーリストに追加 */
for (size_t i = 0; i < POOL_BLOCK_SIZE; i++)
{
block[i].next = pool->free_list;
pool->free_list = &block[i];
}
pool->total_nodes += POOL_BLOCK_SIZE;
return 0;
}
t_list *pool_alloc_node(t_node_pool *pool, void *content)
{
t_list *node;
if (!pool->free_list)
{
if (pool_grow(pool) < 0)
return NULL;
}
node = pool->free_list;
pool->free_list = node->next;
node->content = content;
node->next = NULL;
return node;
}
void pool_free_node(t_node_pool *pool, t_list *node)
{
node->next = pool->free_list;
pool->free_list = node;
}
6.8.2 キャッシュ効率の改善
/*
* 「展開」連結リスト（Unrolled Linked List）
*
* 各ノードに複数の要素を格納してキャッシュ効率を改善
*/
#define UNROLLED_BLOCK_SIZE 16
typedef struct s_unrolled_node {
void *items[UNROLLED_BLOCK_SIZE];
int count;
struct s_unrolled_node *next;
} t_unrolled_node;
typedef struct s_unrolled_list {
t_unrolled_node *head;
t_unrolled_node *tail;
size_t size;
} t_unrolled_list;
/*
* 通常の連結リスト vs 展開連結リスト
*
* 通常：
* [ptr|next] → [ptr|next] → [ptr|next] → ...
* キャッシュミスが多い
*
* 展開：
* [item1|item2|...|item16|next] → [item1|item2|...|item16|next]
* 連続アクセスでキャッシュを有効活用
*/
void unrolled_add(t_unrolled_list *list, void *item)
{
t_unrolled_node *node;
if (!list->tail || list->tail->count >= UNROLLED_BLOCK_SIZE)
{
/* 新しいノードが必要 */
node = malloc(sizeof(t_unrolled_node));
node->count = 0;
node->next = NULL;
if (!list->head)
list->head = node;
else
list->tail->next = node;
list->tail = node;
}
list->tail->items[list->tail->count++] = item;
list->size++;
}
6.9 本章のまとめ
6.9.1 学習した内容の総括
この章では、連結リストの実装を通じて以下の重要概念を学んだ：
1. データ構造の理論的基盤
- 抽象データ型（ADT）の概念
- 計算量理論とBig-O記法
- 配列と連結リストのトレードオフ
2. ポインタと参照の理論
- 間接参照のレベル
- ダブルポインタの必要性
- 自己参照構造体
3. 再帰的データ構造と処理
- 帰納的定義と再帰的関数
- 末尾再帰最適化
- 再帰から反復への変換
4. 連結リストの変種
- 双方向連結リスト
- 循環連結リスト
- センチネルノード
5. 高度なアルゴリズム
- リストの反転
- マージソート
- 循環検出（フロイドのアルゴリズム）
6.9.2 実装チェックリスト
libft連結リスト関数の実装時に確認すべき項目：
□ ft_lstnew: contentをそのまま保存（コピーしない）
□ ft_lstadd_front: ダブルポインタで headを更新
□ ft_lstsize: 全ノードを走査してカウント
□ ft_lstlast: NULL チェックを忘れずに
□ ft_lstadd_back: 空リストの特殊ケースを処理
□ ft_lstdelone: del(content) の後に free(node)
□ ft_lstclear: nextを保存してから現在ノードを削除
□ ft_lstiter: fのNULLチェック
□ ft_lstmap: 部分的な失敗時のクリーンアップ
6.9.3 次のステップ
連結リストをマスターしたら：
- 42の次のプロジェクト
- 実務での応用
連結リストは、すべてのデータ構造の基礎となる。この章で学んだ概念は、より複雑な構造（木、グラフ、ハッシュテーブル）を理解する上で不可欠な基盤となる。