データ構造のひとつである連結リストの概要と、「双方向の連結リスト」をPythonで実装してみました。
Androidアプリを作成しました。
感情用のメモ帳です。
連結リストとは
連結リスト（Linked List）は、データと、データ同士のつながりの情報――ポインタを持つデータ構造です。
データとポインタを合わせたものをノードと呼びます。
連結リストはPythonにおけるリスト（配列）とは違います。
配列はデータがメモリ上に一列に並んでいますが、連結リストはメモリ上に順に並んでいるわけではありません。
メリットは、データの追加・削除を行う場合、高速で実行することができます。
（配列は、末尾以外に対してデータの追加や削除を行うと、変更した位置から順にデータをずらす必要がありコストがかかる。連結リストの場合、ポインタの書き換えだけで良い）
デメリットは、配列のようにインデックスを使ったデータへのアクセスができません。
（配列の500,001番目にアクセスするには「a[500000]」のようにして高速に取得できるが、連結リストは先頭からスタートしたとしてポインタを順に500,001個たどっていく必要がある）
連結リストの種類
連結リストは、繋がり方によって3種類に分けることができます。
- 単方向リスト
- 双方向リスト
- 循環リスト
単方向リストは、一方通行で、次のデータへのポインタを持っています。
双方向リストは、前のデータへのポインタ、次のデータのポインタを持ちます。
上記2つのように、データに先頭と末尾があるものを線形リストと呼ぶこともあります。
循環リストは、データの先頭と末尾がつながっている状態です。
双方向リストの実装
連結リストを自分なりに実装してみました。
class DoubleLinkedList():
class Node():
def __init__(self, data, previous=None, next=None):
self.data = data
self.previous = previous
self.next = next
def __init__(self):
self._head = self.Node('DUMMY-HEAD')
self._tail = self.Node('DUMMY-TAIL', previous=self._head)
self._head.next = self._tail
self.length = 0
def _search(self, data):
target = self._head.next
while True:
if target == self._tail:
return None
if target.data == data:
return target
target = target.next
# データを末尾に連結
def add(self, data):
node = self.Node(data, previous=self._tail.previous, next=self._tail)
self._tail.previous.next = node
self._tail.previous = node
self.length += 1
def remove(self, data):
target = self._search(data)
if target is None:
raise ValueError('削除対象が見つかりませんでした')
target.previous.next = target.next
target.next.previous = target.previous
del target
self.length -= 1
# data_iの後にdataを追加
def insert(self, deta_i, data):
target = self._search(deta_i)
if target is None:
raise ValueError('挿入元のデータが見つかりませんでした')
node = self.Node(data, previous=target, next=target.next)
target.next.previous = node
target.next = node
self.length += 1
def print_reverse(self):
node = self._tail.previous
while node != self._head:
print(node.data)
node = node.previous
def pophead(self):
target = self._head.next
if target == self._tail:
return None
self._head.next = target.next
target.next.previous = self._head
data = target.data
self.length -= 1
del target
return data
def poptail(self):
target = self._tail.previous
if target == self._head:
return None
self._tail.previous = target.previous
target.previous.next = self._tail
data = target.data
self.length -= 1
del target
return data
@property
def list(self):
node_data = []
node = self._head.next
while node != self._tail:
node_data.append(node.data)
node = node.next
return node_data
def __iter__(self):
node_data = self.list
return iter(node_data)
苦戦した箇所をいくつか書き残しておこうと思います。
初期化
DoubleLinkedListクラスは、内部クラス――Nodeを定義しています。
Nodeクラスは、データと、そのデータの前側のポインタ「previous」、次のポインタ「next」を持ちます。
DoubleLinkedListの初期化時には、先頭ノードでかつダミーの「_head」、末尾のデータで同じくダミーの「_tail」が作成されます。
def __init__(self):
self._head = self.Node('DUMMY-HEAD')
self._tail = self.Node('DUMMY-TAIL', previous=self._head)
self._head.next = self._tail
self.length = 0
headとtailには最初具体的なデータを入れていたのですが、書き換えや削除時に処理が面倒になったため、先頭と末尾を指す目印として使用することにしました。
実際には「_head.next」が実用的なデータを持つ先頭ノード、「_tail.previous」が末尾のノードになりますが、初期化段階では具体的なデータが存在しないため、_head.nextは_tailを指し、_tail.previousは_headを指します。
addメソッド
最初に定義したのがこのメソッドです。
# データを末尾に連結
def add(self, data):
node = self.Node(data, previous=self._tail.previous, next=self._tail)
self._tail.previous.next = node
self._tail.previous = node
self.length += 1
メソッド内の1行目で「node」変数を定義し、Nodeクラスのインスタンスを作っています。
最初にデータを追加することを想定して説明すると、「previous=self._tail.previous」は、「previous=self._head」のことです。
2行目も同様に「self._tail.previous.next=node」はつまり「self._head.next」を「node」に設定します。
ここで1行目の設定を「previous=self._head」、2行目を「self.head.next=node」と書いてしまうと、1個目にデータを追加した場合には上手くいきますが、2個目以降のデータの追加時にはリンクが上手くいかなくなってしまうため、「self._tail」を基準とした書き方になっています。
図にすると次のようになります。
実行
「_search」メソッドはデータ削除の「remove」と対象データの後に追加する「insert」メソッド内で使用するもので、対象のデータが見つかったらそのnodeを返すようにしています。
メソッドの実装はドットでつなげていく書き方がややこしかった為、実際に電子メモで図を書きながら作っていきました。
では実行して動作するか確認してみたいと思います。
$ python3
Python 3.10.0 (default, Oct 12 2021, 16:02:08) [GCC 9.3.0] on linux
Type "help", "copyright", "credits" or "license" for more information.
>>> from linkedlist import DoubleLinkedList
>>> linked = DoubleLinkedList()
>>> linked.add('a')
>>> linked.add('b')
>>> linked.add('c')
>>> linked.list
['a', 'b', 'c']
>>> linked.print_reverse()
c
b
a
>>> linked.pophead()
'a'
>>> linked.poptail()
'c'
>>> linked.remove('b')
>>> linked.list
[]
>>> linked.add('January')
>>> linked.add('March')
>>> linked.insert('January', 'February')
>>> linked.insert('March', 'April')
>>> linked.length
4
>>> for i in linked:
... print(i)
...
January
February
March
April
>>> linked.remove('一月')
Traceback (most recent call last):
File "<stdin>", line 1, in <module>
File "/home/fujino/linkedlist.py", line 34, in remove
raise ValueError('削除対象が見つかりませんでした')
ValueError: 削除対象が見つかりませんでした
>>> linked.insert('May', 'June')
Traceback (most recent call last):
File "<stdin>", line 1, in <module>
File "/home/fujino/linkedlist.py", line 44, in insert
raise ValueError('挿入元のデータが見つかりませんでした')
ValueError: 挿入元のデータが見つかりませんでした
ひと通り動作しています。
他にもメソッドとして、先頭からデータを追加、インデックスで挿入、findメソッドなど、考えつくものはいくつかありましたが、切りがなさそうなので、ここで止めておきました。
実装していて思ったのですが、確かにデータの追加や削除は速いかもしれませんが、特定の箇所にデータの挿入や削除を行う場合、データの頭や末尾から検索していく必要があり、データ数が膨大ならそれなりのコストがかかりそうです。
このページが少しでもお役に立てたのなら幸いです。