このページには最新のブラウザ(SharedArrayBuffer対応)が必要です。Chrome、Edge、Firefox、Safariを最新バージョンに更新してください。
リンクで結合されたノード
- 連結リスト はノードの連鎖です。
- 各ノードはデータの一部と、次のノードへのリンクを持ちます。
- 最後のノードは
Noneにリンクしており、これが終端を示します。
ノードは小さなレコード
- 辞書に1つのノードを格納できます:
{"data": ..., "next": ...}。 "data"は値を保持し、"next"は次のノード(またはNone)を保持します。- 最初のノードはリストのヘッドと呼ばれます。
English
second = {"data": "b", "next": None}
first = {"data": "a", "next": second}
print(first["data"])
print(first["next"]["data"])
リストを辿る
- ヘッドから始め、各
"next"リンクをたどります。 Noneに到達したら停止します。- 全ノードを訪問することをトラバーサルと呼びます。
English
head = {"data": 1, "next": {"data": 2, "next": None}}
node = head
while node is not None:
print(node["data"])
node = node["next"]
なぜ連結リストなのか
- リンクの変更によってノードを挿入または削除できます——アイテムの移動は不要です。
- 配列の場合、変更後にすべてのアイテムを動かす必要があります。
- しかし、連結リストにはインデックスがありません。5番目の要素に到達するには、先頭から順にたどる必要があります。
Cambridge擬似コードにおける表現
- 試験用データ構造ではノードを配列に格納します;
NextIndexは次のノードのインデックスであり、NULLが終端を示します。
TYPE Node
DECLARE Data : INTEGER
DECLARE NextIndex : INTEGER // index of the next node, or NULL
ENDTYPE
current ← head
WHILE current <> NULL
OUTPUT list[current].Data
current ← list[current].NextIndex
ENDWHILE
よくあるミス
headポインタを失ってはいけません。そうするとリスト全体にアクセスできなくなります。- 最終ノードは
Noneを指します。
あなたも試してみよう
- ノードは辞書
{"data": ..., "next": ...}です。チェーンをたどるには"next"に従います。 - 回答を確認 を押してコードを試してください。
探索
ポインタでノードが接続されている
各ノードは次のノードを指し、insert/deleteは再連結によって行う。
難易度 4/5 · 280 コイン + 今日初回達成時の小ボーナス
辞書を使ってリンクドリスト 1 → 2 → 3 を構築する。3つのノードを作り、それぞれを次のノードにリンクし、head を最初のノードに指す。最後のノードの "next" は None でなければならない。
実行ボタンをクリックして出力を確認してください。
難易度 4/5 · 280 コイン + 今日初回達成時の小ボーナス
head からリンクドリストをトレースし、各ノードの "data" を合計する。合計を total に格納する(答えは60)。
実行ボタンをクリックして出力を確認してください。
難易度 4/5 · 280 コイン + 今日初回達成時の小ボーナス
length(head) を記述し、リンクドリストに含まれるノードの数を返回する。空のリスト(head が None )は長さ 0 である。
実行ボタンをクリックして出力を確認してください。