本記事は、ソフトバンクパブリッシングから発行されている「定本 Cプログラマのためのアルゴリズムとデータ構造 (SOFTBANK BOOKS)」を参考にPythonでアルゴリズムとデータ構造について学習していきます。
今回は、連結リストを前のリストのポインタも保持した双方向リスト（Doubly Linked List）について学んでいきます。
双方向リストとは
通常の連結リストでは、次のリストの要素にアクセスすることはできても、一つ前の要素にアクセスすることはできませんでした。
双方向リスト（Doubly Linked List）では、一つ前のリストの要素も加えることによって、逆順に辿ることが可能となります。
C言語の場合は、互いに同じアドレスを参照しあっていて、そのアドレスに記載されている内容を書き換えるので、コードを書く際にもすっきりと記述できますが、Pythonの場合では互いに同じオブジェクトを参照していていながらも、オブジェクト自体に変更が加えられない（参照先を変えるだけ）ので、少しコーディングが面倒になります。
Pythonで双方向リストを作ってみる
それでは、Pythonで双方向リストを実装してみます。
# doubly_linked_list.py
class Cell:
def __init__(self, value):
self.value = value
self.next = None
self.prev = None
class DoublyLinkedList:
def __init__(self):
self.head = None
def insert(self, value):
new = Cell(value)
tmp = self.head
if not tmp:
new.next = new
new.prev = new
self.head = new
return
while not tmp == self.head:
tmp = tmp.next
tmp.prev.next = new
new.prev = tmp.prev
new.next = tmp
tmp.prev = new
def delete(self, value):
tmp = self.head
if not tmp:
print("[*] List is empty.")
return
if tmp == tmp.next:
self.head = tmp = None
return
if tmp.value == value:
self.head = tmp.next
tmp = None
return
isfound = False
tmp = tmp.next
while not tmp == self.head:
if tmp.value == value:
isfound = True
break
tmp = tmp.next
if isfound:
tmp.prev.next = tmp.next
tmp.next.prev = tmp.prev
tmp = None
else:
print("[*] Data not found")
def show(self):
tmp = self.head
while tmp:
print(tmp.value)
tmp = tmp.next
if tmp == self.head:
return
else:
print('[*] List is empty.')
l = DoublyLinkedList()
print('insert 1, 2, 3...')
l.insert(1)
l.insert(2)
l.insert(3)
print('print data')
l.show()
print('delete 2...')
l.delete(2)
print('print data')
l.show()
動作確認
それでは上記で作成したスクリプトを実行してみます。
> python doubly_linked_list.py insert 1, 2, 3... print data 1 2 3 delete 2... print data 1 3
まず、1、2、3のデータを挿入し、その後データが挿入されているか確認します。
最後に真ん中にあたる2を削除して、きちんとデータの削除及びつなぎ合わせが出来ているか確認をしています。
参考書籍
定本 Cプログラマのためのアルゴリズムとデータ構造 (SOFTBANK BOOKS)
