2重リンクリストは、リストを格納するためのデータ構造です。
これはリンクリストと非常によく似ていますが、いくつかの追加機能があります。
この記事では、2重連結リストとは何かを説明し、pythonで実装して、その出力を見ていきます。
この記事もチェック：Pythonで連結リスト(リンクリスト)をクラスで実装する方法
Pre-Requisite (事前要件) リンクリスト
二重リンクリストに移る前に、リンクリストとは何かについて説明する必要があります。
リンクリストとは、その名前が示すように、リスト項目が他のリスト項目と特定の方法でリンクされているリストのことです。
正確なリンクのされ方は、リンクリストの種類によって異なります。
最も一般的なリンクリストは「単一リンクリスト」または単に「リンクリスト」で、この場合、各項目はリスト内の次の項目とリンクしています。
つまり、10番目の項目にアクセスするためには、まず9番目の項目にアクセスする必要があるのです。
そして、10番目の項目にアクセスすると、10番目の項目が持っているリンクを通じて11番目の項目にアクセスできるようになるのです。
リンクリストの各項目はノードと呼ばれる。
単一リンクリストでは、各ノードは2つの部分を持っています。
最初の部分にはノードのデータが格納され、2番目の部分には次のノードへのリンクが格納される。
次に、2重リンクリストについて見てみましょう。
ダブルリンクリストとは？
二重連結リストもノードがリンクで結ばれているリストですが、この場合、各ノードは前の項目だけでなく次の項目にもリンクしています。
つまり、10番目のノードにアクセスしたら、9番目のノード、11番目のノードにアクセスでき、特定のノードにアクセスするためには、その前のノードか後のノードのどちらかにアクセスする必要があるのです。
その方法は、各ノードが3つの部分を持っているということです。
最初の部分は格納される実際のデータ、2番目の部分はリスト内の前のノードへのリンク、3番目の部分はリスト内の次のノードへのリンクです。
リンクが2つあることのメリットは、追加や削除などの操作が、単一リンクリストよりもはるかに簡単で高速に行えることだ。
二重リンクリストをイメージすると、次のような感じです。
class Node:
def __init__(self, data = None):
self.data = data
self.next = None
self.previous = None
|
上の例では、リンクリストの中に4つのアイテム/ノードがあることがわかります。
各ノードは何らかのデータまたは内容を持ち、各ノードはリストの次のノードと前のノードを指し示し/リンクしています。
最初のノードの前のリンクと最後のノードの次のリンクは何も指していないので、（pythonの場合）Noneを格納します。
始めに、リストの先頭はリストの最初のノードを指し、リストの末尾はリストの最後のノードを指します。
つまり、最初と最後のノードは、それらを通して直接アクセスできるのです。
他のノードに行くには、headかtailを経由して、それぞれ次のノード、前のノードにアクセスし、目的のノードに到達することになる。
この記事もチェック：Pythonのリストの最初と最後の要素を取得する方法を解説する
Pythonで二重リンクリストを実装する
2重リンクリストの作成は非常に簡単です。
ノード用のクラスと、最初のクラスで作成されたノードを使用してリンクリストを作成するクラスの、2つのクラスを作成する必要があります。
1. クラス ノード
ノード・クラスの場合、クラスには3つのメンバーしかありません。
データを格納するためのもの、次のノードを格納するためのもの、そして前のノードを格納するためのものです。
クラス定義は次のようになります。
class DLL:
def __init__(self):
self.head = None
self.tail = None
self.count = 0
def __repr__(self):
string = ""
if(self.head == None):
string += "Doubly Linked List Empty"
return string
string += f"Doubly Linked List: start = self.head.next
while(start != None):
string += f" -> {start.data}"
start = start.next
return string
def append(self, data):
if self.head == None:
self.head = Node(data)
self.tail = self.head
self.count += 1
return
self.tail.next = Node(data)
self.tail.next.previous = self.tail
self.tail = self.tail.next
self.count += 1
def insert(self, data, index):
if (index > self.count) | (index < 0):
raise ValueError(f"Index out of range: {index}, size: {self.count}")
if(index == self.count):
self.append(data)
return
if(index == 0):
self.head.previous = Node(data)
self.head.previous.next = self.head
self.head = self.head.previous
self.count += 1
return
start = self.head
for _ in range(index):
start = start.next
start.previous.next = Node(data)
start.previous.next.previous = start.previous
start.previous.next.next = start
start.previous = start.previous.next
self.count += 1
return
def remove(self, index):
if (index >= self.count) | (index < 0):
raise ValueError(f"Index out of range: {index}, size: {self.count}")
if index == 0:
self.head = self.head.next
self.head.previous = None
self.count -= 1
return
if index == (self.count - 1):
self.tail = self.tail.previous
self.tail.next = None
self.count -= 1
return
start = self.head
for i in range(index):
start = start.next
start.previous.next, start.next.previous = start.next, start.previous
self.count -= 1
return
def index(self, data):
start = self.head
for i in range(self.count):
if(start.data == data):
return i
start = start.next
return None
def size(self):
return self.count
def display(self):
print(self)
|
ここで、最初はノードは他のノードを指さないし、どのように作られたかによってデータを持つことも持たないこともある。
2. クラス ダブリーリンクリスト
このクラスはノードクラスよりもはるかに多くのものを含んでいます。
先頭ノード、末尾ノード、リスト内のアイテム数、そして新しいノードの挿入、既存のノードの削除、既存のノードの検索、リストの表示など必要なメソッドが含まれます。
クラスは次のようなものになります。
上記のクラスは多くのメンバを持つが，一つ一つ説明していこう．
3. 3. __init__ メソッド
コンストラクタでは、3つの変数を宣言しています。
headとtailはNoneで初期化されます。
つまり、リストには最初から変数が存在しないので、countも0` で初期化されます。
4. 4. __repr__ メソッド
このメソッドはリンクリストを表示するための文字列を返します。
つまり、リストが空の場合はそれを表示し、リストが空でない場合は各ノードのデータを1つずつ表示します。
5. 5. append と insert メソッド
この実装では、指定した位置にノードを追加したり挿入したりすることができます。
追加する場合は、リストが空であるかどうかをチェックします。
空であれば、 head と tail が新しいノードを指すようにします。
そうでない場合は、最後のノードの next が新しいノードを指すようにし、次に新しいノードの previous が最後のノードを指すようにし、最後に tail が新しいノードを指すようにします。
指定された位置に挿入する場合、その位置が末尾であれば、単にノードを追加し、そうでなければ、その位置が先頭であれば、最初のノードの previous ポイントを新しいノードに、次に新しいノードの next ポイントを最初のノードに、そして最後に head ポイントを新しいノードに作成します。
もし指定された位置が真ん中であれば、まずその位置に到達し、その位置より前のノードの next を新しいノードに向け、次に新しいノードの previous をその位置より前のノードに向け、次に新しいノードの next をその位置のノードに向け、最後にその位置のノードの previous を新しいノードに向けます。
また、与えられたインデックスが有効かどうかをチェックし、有効でない場合は ValueError を発生させます。
また、挿入が成功するたびに count をインクリメントします。
6. remove` メソッド
アイテムを削除するには、そのアイテムをどこから削除するかを指定する必要があります。
指定したインデックスが範囲外の場合は、 ValueError を発生させます。
インデックスが 0 の場合、最初のアイテムを削除します。
そのためには、head が 2 番目のノードを指すようにします。
もし head が NULL の場合は、リストが空になったことを意味します。
そうでない場合は、新しい head の previous ストアを None にする必要があります。
同様に、インデックスがリストのサイズよりも 1 つ小さい場合は、最後のアイテムを削除する必要があることを意味します。
したがって、 tail を 2 番目のノードを指すようにし、新しい tail の next ストアを None にします。
インデックスが中間のどこかにある場合は、まずその位置に到達し、その位置より前のノードの next をその位置より後のノードを指すようにし、最後にその位置より後のノードの previous をその位置より前のノードを指すようにします。
removalでは、リストからノードをアクセス不能にするだけで、実際のメモリからの削除処理はPythonのガベージコレクションモジュールに任されています。
7. index,size,display` メソッドです。
indexメソッドは、リスト内の項目を検索するために使用します。
リストサイズに基づいてリスト全体を調べ、ターゲットが見つかればインデックスを返します。
見つからなかった場合は、None`を返します。
sizeメソッドは、リストに含まれる項目の数を格納するクラスのcount` メンバの値を返します。
そして、display メソッドはオブジェクトを表示し、__repr__ メソッドを呼び出して、返された文字列を画面に結果を出力すると、以下の様になります。
出力
このクラスに対して複数のステートメントを実行した結果、以下のような出力が得られました。
まとめ
この記事では、二重リンクリストについて学習し、Pythonで実装しました。
まず、単一リンクリストの動作を理解し、次に二重リンクリストがどのように異なるかを議論しました。
Pythonでデータ構造のコードを書き、それぞれのメソッドがどのように動作しているかを議論し、最後にコードの出力を確認しました。
次回のチュートリアルでお会いしましょう。