Linked lists · リンクドリスト
This page needs a recent browser (with SharedArrayBuffer support). Please update Chrome, Edge, Firefox or Safari to the latest version. · このページには最新のブラウザ（SharedArrayBuffer対応）が必要です。Chrome、Edge、Firefox、Safariを最新バージョンに更新してください。
English
Nodes joined by links
- A linked list is a chain of nodes.
- Each node holds a piece of data and a link to the next node.
- The last node links to
None, which marks the end.
日本語
リンクで結合されたノード
- 連結リスト はノードの連鎖です。
- 各ノードはデータの一部と、次のノードへのリンクを持ちます。
- 最後のノードは
Noneにリンクしており、これが終端を示します。
English
A node is a small record
- We can store one node in a dictionary:
{"data": ..., "next": ...}. "data"holds the value;"next"holds the next node (orNone).- The first node is called the head of the list.
日本語
ノードは小さなレコード
- 辞書に1つのノードを格納できます:
{"data": ..., "next": ...}。 "data"は値を保持し、"next"は次のノード（またはNone）を保持します。- 最初のノードはリストのヘッドと呼ばれます。
second = {"data": "b", "next": None}
first = {"data": "a", "next": second}
print(first["data"])
print(first["next"]["data"])
English
Walk the list
- Start at the head and follow each
"next"link. - Stop when you reach
None. - This visiting of every node is called traversal.
日本語
リストを辿る
- ヘッドから始め、各
"next"リンクをたどります。 Noneに到達したら停止します。- 全ノードを訪問することをトラバーサルと呼びます。
head = {"data": 1, "next": {"data": 2, "next": None}}
node = head
while node is not None:
print(node["data"])
node = node["next"]
English
Why a linked list?
- You can insert or remove a node by changing links — no shifting of items.
- An array would have to move every item after the change.
- But a linked list has no index: to reach item 5 you must walk from the head.
日本語
なぜ連結リストなのか
- リンクの変更によってノードを挿入または削除できます——アイテムの移動は不要です。
- 配列の場合、変更後にすべてのアイテムを動かす必要があります。
- しかし、連結リストにはインデックスがありません。5番目の要素に到達するには、先頭から順にたどる必要があります。
English
In Cambridge pseudocode
- The exam stores nodes in an array;
Nextis the index of the next node, andNULLmarks the end.
日本語
Cambridge擬似コードにおける表現
- 試験用データ構造ではノードを配列に格納します；
Nextは次のノードのインデックスであり、NULLが終端を示します。
TYPE Node
DECLARE Data : INTEGER
DECLARE Next : INTEGER // index of the next node, or NULL
ENDTYPE
current ← head
WHILE current <> NULL
OUTPUT list[current].Data
current ← list[current].Next
ENDWHILE
English
Common mistakes
- Never lose the
headpointer, or the whole list is unreachable. - The last node points to
None.
日本語
よくあるミス
headポインタを失ってはいけません。そうするとリスト全体にアクセスできなくなります。- 最終ノードは
Noneを指します。
English
Now you try
- A node is a dict
{"data": ..., "next": ...}. Follow"next"to walk the chain. - Press Check answer to test your code.
日本語
あなたも試してみよう
- ノードは辞書
{"data": ..., "next": ...}です。チェーンをたどるには"next"に従います。 - 回答を確認 を押してコードを試してください。
Explore · 探索
Nodes linked by pointers · ポインタでノードが接続されている
Each node points to the next; you insert/delete by re-linking. · 各ノードは次のノードを指し、insert/deleteは再連結によって行う。
Build a linked list 1 → 2 → 3 using dictionaries. Make the three nodes, link each to the next, and point head at the first one. The last node's "next" must be None. · 辞書を使ってリンクドリスト 1 → 2 → 3 を構築する。3つのノードを作り、それぞれを次のノードにリンクし、head を最初のノードに指す。最後のノードの "next" は None でなければならない。
Click Run to see the output here. · 実行ボタンをクリックして出力を確認してください。
Walk the linked list starting at head and add up every node's "data". Store the total in total (the answer is 60). · head からリンクドリストをトレースし、各ノードの "data" を合計する。合計を total に格納する（答えは60）。
Click Run to see the output here. · 実行ボタンをクリックして出力を確認してください。
Write length(head) that returns how many nodes are in the linked list. An empty list (head is None) has length 0. · length(head) を記述し、リンクドリストに含まれるノードの数を返回する。空のリスト（head が None ）は長さ 0 である。
Click Run to see the output here. · 実行ボタンをクリックして出力を確認してください。