ポインタで接続されたノード
- リンクドリストとは、ヒープ上に散在するノードと呼ばれる小さな構造体の連鎖です。
- 各ノードは値と次のノードへのポインタを持ちます。ポインタをたどることでリストを移動できます。
- 配列と異なり、リストは他の要素を動かすことなく一度に1つのノードを追加できます。
自己参照構造体
- ノードは自身の型へのポインタを含む構造体です:
struct Node { int data; struct Node *next; };—dataは値であり、nextは次のノードを指します。- これらは各スタートアップで
Nodeとして与えられます。最終ノードのnextはNULLです。
head と NULL の終端
- 単一のポインタである head は最初のノードを指しており、そこから残りのノードにアクセスできます。
- 最終ノードは
NULLを指し、これがリストの終端を示します。 - 空のリストは単に
head == NULLであり、ノードは一切存在しません。
#include <stdio.h>
typedef struct Node { int data; struct Node *next; } Node;
int main(void) {
// A tiny list on the stack: 10 -> 20 -> 30 -> NULL
Node n3 = {30, NULL};
Node n2 = {20, &n3};
Node n1 = {10, &n2};
const Node *head = &n1;
// Walk it: follow ->next until NULL, counting nodes
int count = 0;
const Node *cur = head; // start at the head
while (cur != NULL) { // stop at the NULL end
count++;
cur = cur->next; // step to the next node
}
printf("length = %d\n", count); // length = 3
return 0;
}
先頭にノードを追加する
- 先頭に追加するには、新しいノードを作成し、その
nextを古い head に向け、新しいノードを新しい head として返します。 - これは高速です。他のノードには触れません。
- head が変化するため、関数は新しい head を 返し、呼び出し側がそれを保存します。
よくあるミス
headポインタを失ってはいけません。そうするとリスト全体にアクセスできなくなります。- 全ノードを解放します。最終ノードは
NULLを指しています。
あなたも試してみよう
curポインタとcur = cur->nextを使ってリストを移動し、NULLで停止します。- 新しいノードは
malloc(sizeof(Node))から取得します。チェックツールがリストを解放するため、mainを記述しないでください。
Nodes and pointers
Each node points to the next; insert/delete by re-linking.
難易度 5/5 · 400 コイン + 今日初回達成時の小ボーナス
Complete int length(const Node *head) so it counts the nodes in the list (0 for an empty list). Walk with ->next until NULL. The Node type is given. Do ~ではない write a main.
実行ボタンをクリックして出力を確認してください。
難易度 5/5 · 400 コイン + 今日初回達成時の小ボーナス
Complete int sum_list(const Node *head) so it returns the total of every node's data (0 for an empty list). The Node type is given. Do ~ではない write a main.
実行ボタンをクリックして出力を確認してください。
難易度 5/5 · 400 コイン + 今日初回達成時の小ボーナス
Complete Node *push_front(Node *head, int value) so it makes a new node (with malloc), points its next at the old head, and returns it as the new head. The checker frees the list. Do ~ではない write a main.
実行ボタンをクリックして出力を確認してください。