C言語で学ぶデータ構造。連結リスト・スタック・キューの実装と可視化。
| 構造 | 特徴 | 用途例 |
|---|---|---|
| 連結リスト | 要素同士をポインタで繋ぐ。挿入・削除が高速 | 順序付きデータの頻繁な追加・削除 |
| スタック | 後入れ先出し（LIFO） | 関数の呼び出し管理、Undo機能 |
| キュー | 先入れ先出し（FIFO） | 印刷待ち行列、タスク処理順 |
typedef struct Node { int data; // 格納するデータ struct Node *next; // 次のノードへのポインタ } Node;
// ① ノードの生成 Node* createNode(int val) { Node *n = malloc(sizeof(Node)); n->data = val; n->next = NULL; return n; } // ② 先頭に挿入（O(1)で速い！） void pushFront(Node **head, int val) { Node *n = createNode(val); n->next = *head; // 新ノードの次を旧先頭に *head = n; // 先頭ポインタを更新 } // ③ 全要素の表示 void printList(Node *head) { for (Node *p = head; p != NULL; p = p->next) printf("%d → ", p->data); printf("NULL\n"); } // ④ メモリの解放（忘れるとリーク！） void freeList(Node *head) { while (head) { Node *tmp = head->next; free(head); head = tmp; } }
// push: 先頭に追加 void push(Node **top, int val) { Node *n = createNode(val); n->next = *top; *top = n; } // pop: 先頭を取り出す int pop(Node **top) { if (*top == NULL) return -1; Node *tmp = *top; int val = tmp->data; *top = tmp->next; free(tmp); return val; }
// enqueue: 末尾に追加 void enqueue(Node **head, Node **tail, int val) { Node *n = createNode(val); if (*tail) (*tail)->next = n; else *head = n; *tail = n; } // dequeue: 先頭を取り出す int dequeue(Node **head, Node **tail) { if (!*head) return -1; Node *tmp = *head; int val = tmp->data; *head = tmp->next; if (!*head) *tail = NULL; free(tmp); return val; }
| 操作 | 配列 | 連結リスト | スタック | キュー |
|---|---|---|---|---|
| 先頭に挿入 | O(n) | O(1) | — | — |
| 末尾に追加 | O(1) | O(1)* | O(1) | O(1) |
| ランダムアクセス | O(1) | O(n) | — | — |
| 途中に挿入 | O(n) | O(1)† | — | — |
この講座の理解度をチェックしましょう！
連結リストはポインタを付け替えるだけで挿入・削除ができます。配列は要素をずらす必要があり非効率です。
スタックは最後に入れたデータを最初に取り出す LIFO（Last In, First Out）構造です。
キューは最初に入れたデータを最初に取り出す FIFO（First In, First Out）構造です。行列と同じイメージです。