一覧CS-05-2 · 配列・リスト・キュー

単方向リストと双方向リスト

ノード間の参照を変更し、挿入・削除で必要になるリンクの更新を学びます。

説明

連結リストでは、一つの要素をノードと呼び、値と次のノードへの参照を持たせます。要素の順序はメモリ上の隣接ではなく参照で決まります。先頭から参照をたどれば、途中のノードを別の場所に置いても順に値を取得できます。

ここではノード名A・B・Cと辞書を使って参照を表します。単方向リストにノードを挿入して外し、次に前後両方の参照を持つ双方向リストを操作します。リンクの片側だけを直した場合に起こる不整合も調べます。

1値と次の参照

AからCを経由してBへ進むリストを作ります。辞書に書いた順序ではなくnextの値が順序を決めます。Noneは末尾です。

nodes = {'A': {'value': 10, 'next': 'C'}, 'B': {'value': 30, 'next': None}, 'C': {'value': 20, 'next': 'B'}}値と次ノードの対応; head = 'A'先頭ノード; nodesノード一覧

Aの次はC、Cの次はBです。値の順序は10・20・30となります。ノード名は参照先を識別するための名前で、値そのものではありません。

2参照を二回たどる

添字2に相当する3番目のノードへ進みます。配列のように先頭位置へ固定の幅を足すのではなく、次の参照を一つずつ取得します。

second = nodes[head]['next']2番目の参照; third = nodes[second]['next']3番目の参照; (head, second, third), nodes[third]['value']経路と値

経路はA・C・B、3番目の値は30です。先頭しか分からない単方向リストでは、奥の要素に到達するまで参照をたどる必要があります。

3挿入ノードを準備

AとCの間へ値15のXを挿入します。先にXの次をCに設定します。Aの次を先に変えると、元の参照Cを別に保存しておく必要があります。

nodes['X'] = {'value': 15, 'next': nodes['A']['next']}Xの次を元のCへ; nodes['A'], nodes['X']AとXの参照

まだAの次はCです。Xは存在しますが先頭からの経路には入りません。ノードを作ることと、リストへ接続することは別の操作です。

4先行ノードを接続

Aの次をXへ変更します。Xの次はCのままなので、A・X・C・Bという経路になります。

nodes['A']['next'] = 'X'AからXへ接続; [(key, nodes[key]['next']) for key in ['A', 'X', 'C', 'B']]接続された経路

他のノードの値を移動せず、参照の更新で挿入できました。ただし挿入位置Aを探す費用は別にかかります。位置が既に分かっている場合のリンク更新は一定回数で済みます。

5ノードを経路から外す

Xを削除するには、前のAをXの次であるCへ直接つなぎます。単方向なので、Xだけから前のAを取得することはできません。

nodes['A']['next'] = nodes['X']['next']Xを飛び越して接続; removed = nodes.pop('X')ノード一覧から削除; removed, nodes['A']削除ノードとA

Aの次はCに戻りました。ここでは辞書からXも削除しています。実際のメモリ解放方法は言語や実装によりますが、経路から外すための参照更新は共通です。

6前後両方の参照

双方向リストではprevとnextを持ちます。A・B・Cの3ノードを作り、Bの前後がAとCであることを表示します。

links = {'A': [None, 'B'], 'B': ['A', 'C'], 'C': ['B', None]}前・次の対応; links全ノードの参照

各リストは[前, 次]です。Aの前とCの次はNoneです。Bを外すときには、Aの次とCの前の両方を変更する必要があります。

7片側だけ更新した状態

Aの次だけCへ変えます。Cの前がAを指しているか調べると、逆向きの参照がまだ古いことが分かります。

links['A'][1] = 'C'順方向だけ更新; links参照一覧, links[links['A'][1]][0] == 'A'次へ進んで前へ戻る

判定はFalseです。Aから次へ進むとCですが、Cから前へ戻るとBになります。この状態では往復で同じノードへ戻れません。

8逆方向も更新する

Cの前をAへ直し、Bを取り除きます。残った全ノードについて、次のノードのprevが自分を指すか検査します。

links['C'][0] = 'A'逆方向を修正; del links['B']Bを削除; links残った参照, all(pair[1] is None or links[pair[1]][0] == key for key, pair in links.items())全ての順方向リンクを検査

AとCだけになり、整合性の判定はTrueです。双方向リストは戻る操作ができますが、挿入・削除時に両方向を保つ必要があります。

まとめ

連結リストの順序は、ノード間の参照で決まります。

挿入・削除には先行ノードの参照更新が必要です。リンク更新の費用と位置を探す費用は別に考えます。

双方向リストでは前後の参照をそろえ、片側だけ更新した状態を残さないようにします。

操作履歴と解説を振り返れます。

Python 3

1
nodes = {'A': {'value': 10, 'next': 'C'}, 'B': {'value': 30, 'next': None}, 'C': {'value': 20, 'next': 'B'}}; head = 'A'; nodes
{'A': {'value': 10, 'next': 'C'}, 'B': {'value': 30, 'next': None}, 'C': {'value': 20, 'next': 'B'}}
2
second = nodes[head]['next']; third = nodes[second]['next']; (head, second, third), nodes[third]['value']
(('A', 'C', 'B'), 30)
3
nodes['X'] = {'value': 15, 'next': nodes['A']['next']}; nodes['A'], nodes['X']
({'value': 10, 'next': 'C'}, {'value': 15, 'next': 'C'})
4
nodes['A']['next'] = 'X'; [(key, nodes[key]['next']) for key in ['A', 'X', 'C', 'B']]
[('A', 'X'), ('X', 'C'), ('C', 'B'), ('B', None)]
5
nodes['A']['next'] = nodes['X']['next']; removed = nodes.pop('X'); removed, nodes['A']
({'value': 15, 'next': 'C'}, {'value': 10, 'next': 'C'})
6
links = {'A': [None, 'B'], 'B': ['A', 'C'], 'C': ['B', None]}; links
{'A': [None, 'B'], 'B': ['A', 'C'], 'C': ['B', None]}
7
links['A'][1] = 'C'; links, links[links['A'][1]][0] == 'A'
({'A': [None, 'C'], 'B': ['A', 'C'], 'C': ['B', None]}, False)
8
links['C'][0] = 'A'; del links['B']; links, all(pair[1] is None or links[pair[1]][0] == key for key, pair in links.items())
({'A': [None, 'C'], 'C': ['A', None]}, True)

演習完了