トークンの鎖の途中に1つ足す
連結リストとは、各要素が次の要素へのリンクを持ち、鎖のようにつながった並びです。途中への挿入や削除を、後ろの要素をずらさずにできるようになります。
コンパイラの字句解析器は、fare、*、2 のようなトークンを順に作ります。途中に1つ足すとき、配列なら後ろを全部ずらしますが、鎖なら2か所のつなぎ替えで済みます。
このレッスンのゴール
メモ
連結リストを作って、順にたどり、リンクをつなぎ替えることができる。
重要な言葉
| ことば | いみ | れい |
|---|---|---|
| ノード | 値と、次のノードへのリンクを持つ、鎖の1つの輪 | |
| リンク | あるノードから次のノードを指す参照 | node.next |
| 先頭 | 鎖の最初のノード。ヘッドとも言う | |
| None | リンクの先がないこと。鎖の終わりを表す | |
| たどる | 先頭から、リンクを順に追って全部を見ること |
学生が入力するセルは、このプレビューでは空白です。
ノードは値と次へのリンクを持つ
連結リストの要素は、メモリのあちこちに置かれます。隣り合う必要はありません。
代わりに、各ノードが「次のノードはここ」という手がかりを持ちます。先頭が分かれば、リンクを順に追って全部に届きます。最後のノードのリンクは None です。
ノードを作ってたどるコード
class Node:
def __init__(self, value):
self.value = value # このノードが持つ値
self.next = None # 次のノード。まだなければ None
head = Node("fare")
head.next = Node("*")
head.next.next = Node("2")
node = head
while node is not None:
print(node.value)
node = node.next
# ループの前に head.next.next.next = Node("+") を足して、もう一度実行しましょう。
3つ先のノードの値を読む
python3 -c "c = ['300', None]; b = ['+', c]; a = ['fare', b]; print(a[1][1][0])"ここでは表示のみで、実行されません。無料アカウントを作成すると、実行ボタンで自分のラボのターミナルに入力できます。
挿入と削除は、リンクのつなぎ替え
aとbの間に新しいノードxを入れるには、2行です。まずxの next をbにつなぎ、次にaの next をxにつなぎます。
順番を逆にすると、bへの道が消えます。削除は、前のノードの next を、消すノードの次につなぐだけです。ずらす要素はありません。
例: fare と 2 の間に * を入れる
| 手順 | コード | 鎖の様子 |
|---|---|---|
| 0 | （入れる前） | fare → 2 |
| 1 | star.next = a.next | * → 2、fare → 2 |
| 2 | a.next = star | fare → * → 2 |
学生が入力するセルは、このプレビューでは空白です。
つなぎ替えで挿入するコード
class Node:
def __init__(self, value):
self.value = value
self.next = None
a = Node("fare")
b = Node("2")
a.next = b
# a と b の間に "*" を入れます。つなぎ替えは2行です。
star = Node("*")
star.next = a.next # 先に、新しいノードを後ろにつなぎます。
a.next = star # そのあとで、前のノードを新しいノードにつなぎます。
node = a
while node is not None:
print(node.value)
node = node.next
# "*" を取り除くには、a.next = star.next と書きます。試しましょう。
削除は、つなぎ替えで済む
python3 -c "c = ['300', None]; b = ['+', c]; a = ['fare', b]; a[1] = c; print(a)"ここでは表示のみで、実行されません。無料アカウントを作成すると、実行ボタンで自分のラボのターミナルに入力できます。
よくある間違い
注意
連結リストは、配列よりいつも速いと思いがちです。つなぎ替えが速いのは、場所のノードを手に持っているときだけです。3番目や1000番目を探すには、リンクを何回もたどります。配列なら、計算1回で届きます。
リンクの向きを変えて逆順にする
鎖を逆にするには、ノードを1つずつ見て、next を前のノードに向け直します。
書き換える前に、次のノードを別に覚えておきます。そうしないと、鎖の先を見失います。最後に、一番後ろだったノードが、新しい先頭になります。
例: a → b → c を逆にする
| 繰り返し | node | previous | 書き換えたあとの鎖 |
|---|---|---|---|
| 始める前 | a | None | a → b → c |
| 1回目 | b | a | a → None、b → c |
| 2回目 | c | b | b → a、c は元のまま |
| 3回目 | None | c | c → b → a |
学生が入力するセルは、このプレビューでは空白です。
3つのノードを逆にするコード
class Node:
def __init__(self, value):
self.value = value
self.next = None
a = Node("fare")
a.next = Node("*")
a.next.next = Node("2")
previous = None
node = a
while node is not None:
following = node.next # 書き換える前に、次を覚えます。
node.next = previous # リンクを逆向きにします。
previous = node
node = following
# 逆にした鎖の先頭は previous です。
node = previous
while node is not None:
print(node.value)
node = node.next