Pythonでリンクリストを実装する連載の3回目です。
連載の第1回と第2回では、単一リンクリストについて詳しく学びました。
今回は、単連結リストの拡張である双連結リストについて説明します。
単リンクリストでは、リストの各ノードは、ノードの実際の値と、リンクリスト内の次のノードへの参照という2つの要素を持っています。
2重リンクリストでは、各ノードは、ノードの値、前のノードへの参照、次のノードへの参照という3つの構成要素を持つ。
双方向リンクリストの開始ノードでは、前のノードへの参照はnullである。
同様に、二重リンクリストの最後のノードでは、次のノードへの参照はnullである。
二重リンクリストの長所と短所
以下は、2重リンクリストの長所と短所です。
プロフェッショナル
- 単一リンクリストと異なり、2重リンクリストは両方向にトラバースと検索が可能です。次のノードへの参照は前方向の探索に役立ち、前のノードへの参照は後方向の 探索を可能にする。
- 2重連結リストでは、単連結リストとは異なり、前ノードまで走査してその参照を保存する必要がないため、挿入や削除といった基本的な操作が容易に行える。むしろ、2重連結リストでは、削除したいノードから先行するノードの参照を取り出すことができる。
短所
- 二重リンクリストの大きな欠点は、各ノードに対して1つ余分に参照を格納するために、より多くのメモリスペースが必要になることです。
- 挿入と削除の操作を実行するために、いくつかの追加ステップが必要です。
Pythonによるダブリーリンクリストの実装
このセクションでは、Pythonで非常に単純な2重リンクリストを作成する方法を紹介します。
この連載の第1回と第2回を読んでいれば、コードはかなりわかりやすいはずです。
いつものように、まずリストの単一ノードのためのクラスを作りましょう。
次のコードをファイルに追加してください。
class Node:
def __init__(self, data):
self.item = data
self.nref = None
self.pref = None
上のコードで、 item, nref, pref という3つのメンバ変数を持つ Node クラスを作成しているのがわかると思います。
item変数には、ノードの実際のデータが格納される。
nref には次のノードへの参照が格納され、pref には二重リンクリストの前のノードへの参照が格納されます。
次に、DoublyLinkedList クラスを作成する必要があります。
このクラスは、二重リンクリストに関連するさまざまな関数を含んでいます。
次のコードを追加してください。
class DoublyLinkedList:
def __init__(self):
self.start_node = None
この記事全体を通して、このクラスに関数を追加していきます。
二重リンクリストに項目を挿入する ##### 二重リンクリストに項目を挿入する
このセクションでは、2重リンクリストに項目を挿入するさまざまな方法について説明します。
空のリストに項目を挿入する ##### 空のリストに項目を挿入する
2重リンクリストに項目を挿入する最も簡単な方法は、空のリストに項目を挿入することです。
次のスクリプトは、2重リンクリストの先頭に要素を挿入する。
def insert_in_emptylist(self, data):
if self.start_node is None:
new_node = Node(data)
self.start_node = new_node
else:
print("list is not empty")
上のスクリプトでは、メソッド insert_in_emptylist() を定義しています。
このメソッドはまず、変数 self.start_node が None であるかどうかをチェックする。
もしこの変数が None ならば、リストは実際には空であることを意味します。
次に、新しいノードが作成され、その値は insert_in_emptylist() 関数の data パラメータとして渡された値で初期化されます。
最後に、変数 self.start_node の値が新しいノードに設定されます。
リストが空でない場合は、単にリストが空でない旨のメッセージが表示されます。
先ほど作成した DoublyLinkedList クラスに insert_in_emptylist() メソッドを追加してください。
開始時にアイテムを挿入する
2重リンクリストの先頭に項目を挿入するには、まずリストが空かどうかをチェックする必要があります。
リストが空の場合は、insert_in_emptylist()で定義されたロジックを使用して要素を挿入します。
空のリストでは、最初の要素は常に先頭にあるからです。
一方、リストが空でない場合は、3つの操作を行う必要があります。
- 新しいノードに対して、次のノードへの参照は
self.start_nodeに設定されます。 -
-
self.start_nodeに対して、前のノードへの参照が、新しく挿入されたノードに設定されます。
-
-
- 最後に、
self.start_nodeは新しく挿入されたノードになります。
- 最後に、
次のスクリプトは、2重リンクリストの先頭に項目を挿入します。
def insert_at_start(self, data):
if self.start_node is None:
new_node = Node(data)
self.start_node = new_node
print("node inserted")
return
new_node = Node(data)
new_node.nref = self.start_node
self.start_node.pref = new_node
self.start_node = new_node
先ほど作成した DoublyLinkedList クラスに insert_at_start() メソッドを追加してください。
末尾に項目を挿入する
二重リンクリストの末尾に要素を挿入する方法は、先頭の要素を挿入する方法と多少似ています。
まず、リストが空かどうかをチェックする必要があります。
もしリストが空なら、単純に insert_in_emptylist() メソッドを使って要素を挿入できます。
もしリストが既に何らかの要素を含んでいる場合は、次のノードへの参照が None になるまでリストを走査します。
次のノードの参照が None になった場合、現在のノードが最後のノードであることを意味します。
新しいノードの前の参照は最後のノードに設定され、最後のノードの次の参照は新しく挿入されたノードに設定されます。
最後のノードに項目を挿入するスクリプトは次のとおりである。
def insert_at_end(self, data):
if self.start_node is None:
new_node = Node(data)
self.start_node = new_node
return
n = self.start_node
while n.nref is not None:
n = n.nref
new_node = Node(data)
n.nref = new_node
new_node.pref = n
先ほど作成した DoublyLinkedList クラスに insert_at_end() メソッドを追加してください。
別のアイテムの後にアイテムを挿入する
項目の後ろに項目を挿入するには、まずリストが空であるかどうかを確認します。
リストが実際に空であれば、「リストは空です」というメッセージを表示するだけでよい。
そうでなければ、二重リンクリストのすべてのノードを順に見ていく。
新しいノードを挿入したいノードが見つからない場合は、その項目が見つからないというメッセージをユーザーに表示する。
一方、ノードが見つかった場合は、そのノードを選択し、4つの操作を行う。
-
- 新たに挿入するノードの前参照を、選択したノードに設定する。
-
- 新たに挿入されたノードの次参照を、選択されたノードの次参照に設定する。
-
- 選択されたノードが最後のノードでない場合，選択されたノードの次のノードの前参照を，新しく追加されたノードに設定する。
- 最後に、selectedノードの次の参照を、新しく挿入されたノードに設定する。
項目の後に項目を挿入するスクリプトは次のとおりです。
def insert_after_item(self, x, data):
if self.start_node is None:
print("List is empty")
return
else:
n = self.start_node
while n is not None:
if n.item == x:
break
n = n.nref
if n is None:
print("item not in the list")
else:
new_node = Node(data)
new_node.pref = n
new_node.nref = n.nref
if n.nref is not None:
n.nref.prev = new_node
n.nref = new_node
先ほど作成した DoublyLinkedList クラスに insert_after_item() メソッドを追加してください。
別のアイテムの前にアイテムを挿入する
ある項目を別の項目の前に挿入するには、まずリストが空かどうかを確認します。
リストが実際に空であれば、「リストは空です」というメッセージを表示するだけでよい。
そうでなければ、二重リンクリストのすべてのノードを順に見ていく。
新しいノードを挿入したいノードの前にあるノードが見つからない場合は、その項目が見つからないというメッセージをユーザーに表示する。
一方、ノードが見つかった場合は、そのノードを選択し、4つの操作を行う。
-
- 新たに挿入するノードの次参照を、選択されたノードに設定する。
-
- 新たに挿入されたノードの前参照を、選択されたノードの前参照に設定する。
-
- 選択されたノードの前のノードの次の参照を、新しく追加されたノードに設定する。
- 最後に、selected ノードの前参照を、新しく挿入されたノードに設定する。
二重リンクリストの項目を前に追加するスクリプトは以下の通りである。
def insert_before_item(self, x, data):
if self.start_node is None:
print("List is empty")
return
else:
n = self.start_node
while n is not None:
if n.item == x:
break
n = n.nref
if n is None:
print("item not in the list")
else:
new_node = Node(data)
new_node.nref = n
new_node.pref = n.pref
if n.pref is not None:
n.pref.nref = new_node
n.pref = new_node
先ほど作成した DoublyLinkedList クラスに insert_before_item() メソッドを追加してください。
二重リンクリストのトラバース
二重リンクリストの走査は単一リンクリストの走査と非常によく似ている。
スクリプトは以下の通りである。
def traverse_list(self):
if self.start_node is None:
print("List has no element")
return
else:
n = self.start_node
while n is not None:
print(n.item , " ")
n = n.nref
先ほど作成した DoublyLinkedList クラスに traverse_list() メソッドを追加してください。
ダブルリンクリストからの要素削除
挿入と同様に、ダブルリンクリストから要素を削除する方法も複数あります。
本節では、そのうちのいくつかを紹介します。
スタートから要素を削除する ##### スタートから要素を削除する
二重リンクリストの要素を削除する最も簡単な方法は、先頭から削除することです。
そのためには、開始ノードの値を次のノードに設定し、開始ノードの前の参照を None に設定すればよいのです。
しかし、その前に2つのチェックを行う必要があります。
まず、リストが空であるかどうかを確認する必要があります。
そして、リストに含まれる要素が1つだけかどうかを確認する必要があります。
もし、リストに要素が1つしかなければ、単純に開始ノードを None に設定すればよいのです。
次のスクリプトは、二重リンクリストの開始ノードから要素を削除するために使われます。
def delete_at_start(self):
if self.start_node is None:
print("The list has no element to delete")
return
if self.start_node.nref is None:
self.start_node = None
return
self.start_node = self.start_node.nref
self.start_prev = None;
先ほど作成した DoublyLinkedList クラスに delete_at_start() メソッドを追加してください。
終了時の要素削除
末尾の要素を削除するには、リストが空か、リストに1つの要素が含まれているかを再度確認します。
リストが1つの要素しか含まない場合は、開始ノードを None に設定するだけでよいでしょう。
リストが複数の要素を持つ場合は、最後のノードに到達するまでリストを繰り返し処理します。
最後のノードに到達したら、最後のノードより前のノードの次の参照を None に設定し、実際に最後のノードを削除します。
次のスクリプトは、末尾の要素を削除するために使用することができます。
def delete_at_end(self):
if self.start_node is None:
print("The list has no element to delete")
return
if self.start_node.nref is None:
self.start_node = None
return
n = self.start_node
while n.nref is not None:
n = n.nref
n.pref.nref = None
先ほど作成した DoublyLinkedList クラスに delete_at_end() メソッドを追加してください。
値で要素を削除する ##### 値で要素を削除する
値による要素の削除は、2重リンクリストの削除関数の中で最も厄介な関数です。
まず、この関数がどのように見えるかを見て、次に個々のコードの説明を見ましょう。
def delete_element_by_value(self, x):
if self.start_node is None:
print("The list has no element to delete")
return
if self.start_node.nref is None:
if self.start_node.item == x:
self.start_node = None
else:
print("Item not found")
return
if self.start_node.item == x:
self.start_node = self.start_node.nref
self.start_node.pref = None
return
n = self.start_node
while n.nref is not None:
if n.item == x:
break;
n = n.nref
if n.nref is not None:
n.pref.nref = n.nref
n.nref.pref = n.pref
else:
if n.item == x:
n.pref.nref = None
else:
print("Element not found")
上のスクリプトでは、ノードの値をパラメータとして受け取り、そのノードを削除する delete_element_by_value() 関数を作成しています。
関数の始めに、リストが空かどうかをチェックします。
リストが空の場合は、単にリストが空であることをユーザーに表示します。
このロジックは次のようなコードで実装されています。
if self.start_node is None:
print("The list has no element to delete")
return
次に、リストの要素がひとつかどうか、そしてその要素が実際に削除したい要素であるかどうかを調べます。
もし、削除したい要素しかなければ、self.start_node を None に設定します。
もし、削除したい項目が一つしかない場合は、削除する項目が見つからないというメッセージを表示します。
このロジックを実装したのが、次のコードです。
if self.start_node.nref is None:
if self.start_node.item == x:
self.start_node = None
else:
print("Item not found")
return
次に、リストには複数の項目があるが、削除する項目は最初の項目である場合を考えます。
この場合は、単純に delete_at_start() メソッドに記述したロジックを実行します。
次のコードは、複数のアイテムがある場合に、要素を先頭から削除するものです。
if self.start_node.item == x:
self.start_node = self.start_node.nref
self.start_node.pref = None
return
最後に、リストが複数の項目を含んでいて、削除する項目が最初の項目でない場合、最後の項目を除くリストのすべての要素を走査して、削除する値に一致するノードがあるかどうか調べます。
そのノードが見つかったら、以下の2つの処理を行う。
-
- 前ノードの次参照の値を削除するノードの次参照に設定する。
-
- 次のノードの前の値を、削除するノードの前の参照に設定する。
最後に、削除されるノードが最後のノードである場合、最後のノードより前のノードの次の参照は None に設定される。
以下のスクリプトは、このロジックを実装したものである。
n = self.start_node
while n.nref is not None:
if n.item == x:
break;
n = n.nref
if n.nref is not None:
n.pref.nref = n.nref
n.nref.pref = n.pref
else:
if n.item == x:
n.pref.nref = None
else:
print("Element not found")
先ほど作成した DoublyLinkedList クラスに delete_element_by_value() メソッドを追加してください。
二重リンクリストの反転
ダブルリンクリストを反転させるには、基本的に以下の操作を行う必要があります。
-
- 先頭のノードがリストの最後のノードになるため、先頭のノードの次の参照を none にする。
-
- 最後のノードが前のノードになるため、最後のノードの前参照は
Noneに設定されなければなりません。
- 最後のノードが前のノードになるため、最後のノードの前参照は
-
- 元のリストのノード（最初と最後のノードを除く）の次の参照は、前の参照と入れ替わります。
二重リンクリストを反転させるスクリプトは以下の通りである。
def reverse_linked_list(self):
if self.start_node is None:
print("The list has no element to delete")
return
p = self.start_node
q = p.nref
p.nref = None
p.pref = q
while q is not None:
q.pref = q.nref
q.nref = p
p = q
q = q.pref
self.start_node = p
先ほど作成した DoublyLinkedList クラスに reverse_linked_list() メソッドを追加してください。
二重リンクリスト関数のテスト
この節では、これまでの節で作成したダブリンクリスト関数をテストします。
まず、DoublyLinkedList クラスのオブジェクトを作成しよう。
以下のスクリプトを実行しなさい。
new_linked_list = DoublyLinkedList()
挿入関数のテスト
まず、挿入関数をテストしてみましょう。
まず、空リストに要素を追加してみます。
以下のスクリプトを実行してください。
new_linked_list.insert_in_emptylist(50)
ここで、リストを走査すると、以下のように50が唯一の要素として表示されるはずです。
new_linked_list.traverse_list()
出力。
50
では、冒頭にいくつかの要素を追加してみよう。
次のスクリプトを実行してください。
new_linked_list.insert_at_start(10)
new_linked_list.insert_at_start(5)
new_linked_list.insert_at_start(18)
これで、リストをたどると、次のような要素がリストに入っているはずです。
18
5
10
50
最後に要素を追加するには、次のスクリプトを実行する。
new_linked_list.insert_at_end(29)
new_linked_list.insert_at_end(39)
new_linked_list.insert_at_end(49)
ここで、2重リンクリストを走査すると、次のような要素が見えるはずである。
18
5
10
50
29
39
49
50の後に要素を挿入してみよう。
new_linked_list.insert_after_item(50, 65)
これで、リストは次のようになるはずだ。
18
5
10
50
65
29
39
49
最後に、アイテム29の前に要素を追加してみましょう。
new_linked_list.insert_before_item(29, 100)
この時点のリストには、次のような要素が含まれているはずです。
18
5
10
50
65
100
29
39
49
削除関数のテスト
それでは、前節で挿入した項目を削除する関数をテストしてみましょう。
まず、最初から要素を削除してみましょう。
new_linked_list.delete_at_start()
アイテム18が削除され、リストは以下のようになります。
5
10
50
65
100
29
39
49
同様に、次のスクリプトは2重リンクリストの末尾から要素を削除します。
new_linked_list.delete_at_end()
このリストを走査すると、次のような項目が返されます。
5
10
50
65
100
29
39
最後に、以下のように delete_element_by_value() 関数を使用して、値によって要素を削除することもできます。
new_linked_list.delete_element_by_value(65)
今リストを走査すると、アイテム65がリストから削除されることがわかります。
逆機能のテスト
最後に、reverse_linked_list()関数を使って、リストを逆引きしてみましょう。
以下のスクリプトを実行してください。
new_linked_list.reverse_linked_list()
これで、リストをトラバースすると、反転したリンクリストが表示されます。
39
29
100
50
10
5
結論
二重リンクリストは、特に挿入や削除の操作を多く行わなければならない場合に非常に便利です。
前ノードと次ノードへのリンクにより、前ノードと次ノードを追跡することなく、新しい要素の挿入と削除を非常に簡単に行うことができます。
この記事では、Pythonで2重リンクリストを実装する方法について見ました。
また、2重連結リストに対して挿入と削除の操作を行うさまざまな方法についても見てきました。
最後に、2重リンクリストを反転させる方法を学びました。