以下を参考にしています。
Data-Structures-using-Python/Linked Lists/DoublyLinkedList.py
双方向リスト
片方向リストは後方向へのリンクだけでしたが、双方向リスト（Doubly-Linked List）は、前方向、後方向、双方へのリンクを持っています。
メリット
- 前のノードのアドレス情報なしでノードの削除が行える。
デメリット
- 片方向リストと比較するとポインタが増えてしまうので、容量が増える。
- リストの操作の際に、ポインタの操作が増えるので、時間がかかる。
双方向リスト（doubly-linked list）は、より洗練された連結リスト。各ノードには2つのリンクがあり、1つが次のノード（前方リンク）、もう1つが後ろのノード（後方リンク）を指す。リストの先頭のノードには後ろのノードがないので、後方リンクにはヌル値を格納するか、空のリストを指す。リストの最後尾のノードには次のノードがないので、前方リンクにはヌル値を格納するか、空のリストを指す。
出典: フリー百科事典『ウィキペディア（Wikipedia）』
class Node():
# ノードは前方向、後方向へのリンクを持つ。
def __init__(self, data, next = None, previous = None):
self.data = data
self.next = next
self.previous = previous
# データを設定する。
def set_data(self, data):
self.data = data
# データを取得する。
def get_data(self):
return self.data
# 次のノードを設定する。
def set_next(self, next):
self.next = next
# 次のノードを取得する。
def get_next(self):
return self.next
# 前のノードを設定する。
def set_previous(self, previous):
self.previous = previous
# 前のノードを取得する。
def get_previous(self):
return self.previous
class DoublyLinkedList():
def __init__(self):
self.head = None
self.tail = None
双方向リストのデータ参照
データの出力
片方向リストと変わりません。
- ノードの持つリンクを辿る。
- 参照したノードのデータを表示する。
- 次のリンクがNullであれば終了する。
# データの出力
def print_doubly_linked_list(self):
temp = self.head
while(temp is not None):
print(temp.data, end=' ')
temp = temp.get_next()
双方向リストのデータ挿入
先頭に挿入
- 新しいノードの右のポインタを現在の先頭のノードを指すように、左のポインタはNullに設定する。
# 先頭に挿入する
def insert_at_start(self, data):
new_node = Node(data)
if self.head is None:
self.head = new_node
self.tail = new_node
else:
new_node.set_previous(None)
new_node.set_next(self.head)
self.head.set_previous(new_node)
self.head = new_node
最後に挿入
- 新しいノードの右のポインタをNullに、左のポインタを現在の最後のノードを指すようにする。
# 最後に挿入する
def insert_at_end(self, data):
if self.head is None:
self.head = Node(data)
self.tail = self.head
else:
temp = self.head
while temp.get_next() is not None:
temp = temp.get_next()
temp.set_next(Node(data, None, temp))
self.tail = temp.get_next()
間に挿入
- 挿入する位置まで移動する。
- 新しいノードの右のポインタを挿入箇所のノードの次のノードに、左のポインタを挿入箇所のノードにする。
- 挿入箇所のノードの右のポインタを新しいノードに、挿入箇所ノードの次ノードの左のポインタを新しいノードに設定する。
# ある場所のノードを取得する。
def get_node(self, position):
temp = self.head
if temp is None:
return None
i = 0
while i < position and temp.get_next() is not None:
temp = temp.get_next()
if temp is None:
break
i += 1
return temp
# 間にノードを挿入する。
def insert_position(self, position, data):
temp = self.head
if self.head is None or position == 0:
self.insert_at_start(data)
elif position > 0:
temp = self.get_node(position)
if temp is None or temp.get_next() is None:
self.insert_at_end(data)
else:
new_node = Node(data)
new_node.set_next(temp.get_next())
new_node.set_previous(temp)
temp.get_next().set_previous(new_node)
temp.set_next(new_node)
双方向リストのデータ削除
先頭を削除
def delete(self, data):
temp = self.head
if temp.get_next() is not None:
# 先頭を削除する
if temp.data == data:
temp.get_next().set_previous(None)
self.head = temp.get_next()
temp.set_next(None)
return
else:
while temp.get_next() is not None:
if temp.get_data() == data:
break
temp = temp.get_next()
if temp.next:
# 間の要素を削除する
temp.previous.next = temp.next
temp.next.previous = temp.previous
temp.next = None
temp.previous = None
else:
# 最後を削除する
temp.previous.next = None
temp.previous = None
return
if temp is None:
return
双方向リストのコード
class Node():
# ノードは前方向、後方向へのリンクを持つ。
def __init__(self, data, next = None, previous = None):
self.data = data
self.next = next
self.previous = previous
# データを設定する。
def set_data(self, data):
self.data = data
# データを取得する。
def get_data(self):
return self.data
# 次のノードを設定する。
def set_next(self, next):
self.next = next
# 次のノードを取得する。
def get_next(self):
return self.next
# 前のノードを設定する。
def set_previous(self, previous):
self.previous = previous
# 前のノードを取得する。
def get_previous(self):
return self.previous
class DoublyLinkedList():
def __init__(self):
self.head = None
self.tail = None
# データの出力
def print_doubly_linked_list(self):
temp = self.head
while(temp is not None):
print(temp.data, end=' ')
temp = temp.get_next()
# 先頭に挿入する
def insert_at_start(self, data):
new_node = Node(data)
if self.head is None:
self.head = new_node
self.tail = new_node
else:
new_node.set_previous(None)
new_node.set_next(self.head)
self.head.set_previous(new_node)
self.head = new_node
# 最後に挿入する
def insert_at_end(self, data):
if self.head is None:
self.head = Node(data)
self.tail = self.head
else:
temp = self.head
while temp.get_next() is not None:
temp = temp.get_next()
temp.set_next(Node(data, None, temp))
self.tail = temp.get_next()
# ある場所のノードを取得する。
def get_node(self, position):
temp = self.head
if temp is None:
return None
i = 0
while i < position and temp.get_next() is not None:
temp = temp.get_next()
if temp is None:
break
i += 1
return temp
# 間にノードを挿入する。
def insert_position(self, position, data):
temp = self.head
if self.head is None or position == 0:
self.insert_at_start(data)
elif position > 0:
temp = self.get_node(position)
if temp is None or temp.get_next() is None:
self.insert_at_end(data)
else:
new_node = Node(data)
new_node.set_next(temp.get_next())
new_node.set_previous(temp)
temp.get_next().set_previous(new_node)
temp.set_next(new_node)
def delete(self, data):
temp = self.head
if temp.get_next() is not None:
# 先頭を削除する
if temp.data == data:
temp.get_next().set_previous(None)
self.head = temp.get_next()
temp.set_next(None)
return
else:
while temp.get_next() is not None:
if temp.get_data() == data:
break
temp = temp.get_next()
if temp.next:
# 間の要素を削除する
temp.previous.next = temp.next
temp.next.previous = temp.previous
temp.next = None
temp.previous = None
else:
# 最後を削除する
temp.previous.next = None
temp.previous = None
return
if temp is None:
return
if __name__ == '__main__':
doubly_linked_list = DoublyLinkedList()
doubly_linked_list.insert_at_start(1)
doubly_linked_list.insert_at_start(2)
doubly_linked_list.insert_at_end(3)
doubly_linked_list.insert_at_start(4)
doubly_linked_list.print_doubly_linked_list()
print()
print(doubly_linked_list.get_node(3).get_data())
doubly_linked_list.insert_position(3, 5)
doubly_linked_list.print_doubly_linked_list()
print()
doubly_linked_list.delete(2)
doubly_linked_list.print_doubly_linked_list()