Linked lists · リンクドリスト
Nodes joined by pointers
- A linked list is a chain of small structs called nodes, scattered around the heap.
- Each node holds a value and a pointer to the next node. Follow the pointers to walk the list.
- Unlike an array, a list can grow one node at a time without moving the others.
ポインタで接続されたノード
- リンクドリストとは、ヒープ上に散在するノードと呼ばれる小さな構造体の連鎖です。
- 各ノードは値と次のノードへのポインタを持ちます。ポインタをたどることでリストを移動できます。
- 配列と異なり、リストは他の要素を動かすことなく一度に1つのノードを追加できます。
A self-referential struct
- A node is a struct that contains a pointer to its own type:
struct Node { int data; struct Node *next; };—datais the value,nextpoints to the following node.- This is given for you as
Nodein each starter. The last node'snextisNULL.
自己参照構造体
- ノードは自身の型へのポインタを含む構造体です：
struct Node { int data; struct Node *next; };—dataは値であり、nextは次のノードを指します。- これらは各スタートアップで
Nodeとして与えられます。最終ノードのnextはNULLです。
head and the NULL end
- A single pointer, the head, points to the first node. From there you reach the rest.
- The very last node points to
NULL, which marks the end of the list. - An empty list is just
head == NULL— there are no nodes at all.
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;
}
Adding a node at the front
- To add to the front, make a new node, point its
nextat the old head, and return the new node as the new head. - This is fast — it does not touch any other node.
- Because the head changes, the function returns the new head, and the caller saves it.
先頭にノードを追加する
- 先頭に追加するには、新しいノードを作成し、その
nextを古い head に向け、新しいノードを新しい head として返します。 - これは高速です。他のノードには触れません。
- head が変化するため、関数は新しい head を 返し、呼び出し側がそれを保存します。
Common mistakes
- Never lose the
headpointer, or the whole list is unreachable. - Free every node; the last node points to
NULL.
よくあるミス
headポインタを失ってはいけません。そうするとリスト全体にアクセスできなくなります。- 全ノードを解放します。最終ノードは
NULLを指しています。
Now you try
- Walk a list with a
curpointer andcur = cur->next, stopping atNULL. - New nodes come from
malloc(sizeof(Node)); the checker frees the list. Do not write amain.
あなたも試してみよう
curポインタとcur = cur->nextを使ってリストを移動し、NULLで停止します。- 新しいノードは
malloc(sizeof(Node))から取得します。チェックツールがリストを解放するため、mainを記述しないでください。
Nodes and pointers · ノードとポインタ
Each node points to the next; insert/delete by re-linking. · 各ノードは次のノードを指し、挿入・削除はリンクの書き換えによって行う。
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 not write a main. · int length(const Node *head)を完成させて、リスト内のノード数を数える（空リストなら0）。->nextで walked NULLになるまで進める。Node型は与えられている。mainは書かない。
Click Run to see the output here. · 実行ボタンをクリックして出力を確認してください。
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 not write a main. · int sum_list(const Node *head)を完成させて、各ノードのdataの合計を返す（空リストなら0）。Node型は与えられている。mainは書かない。
Click Run to see the output here. · 実行ボタンをクリックして出力を確認してください。
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 not write a main. · Node *push_front(Node *head, int value)を完成させて、新しいノード（malloc付き）を作り、そのnextを古いheadに指して新しいヘッドとして返す。チェッカーはリストをfreeする。mainは書かない。
Click Run to see the output here. · 実行ボタンをクリックして出力を確認してください。