Pythonのリンクリストは、C/C++時代から人気を保ち続けている興味深い抽象データ型の1つです。
今回は、Pythonでリンクリストをゼロから実装する方法を学びます。
リンクリストとは
リンクリストは、各要素が独立したオブジェクトである線形データ構造です。
リンクリストの要素は、配列とは異なり、メモリ内に一緒に格納されません。
リンクリストの各要素は、その次の要素を指しています。
ここでいうポイントとは、各要素に次の要素のアドレスが格納されていることを意味します。
リンクリストを巡回する際には、このポインターを利用して、あるノードから次のノードへジャンプします。
各リンクリストには、考慮しなければならない要素が2つあります。
- ノード – ノードクラスを作成することにより、ノードを処理します。
- ノード間の接続 – Pythonの変数とリストでこれを処理します。
Pythonでリンクリストを作るには？
Pythonでリンクリストを作成する手順を説明します。
Node クラスの作成
独自のリンクリストを作成するには、ノードクラスを定義する必要があります。
ノード・クラスを定義する前に、そのクラスがどのようなフィールドを持つべきかを考える必要があります。
リンクリストのノードは2つのものを格納することになっています。
- データ
- 次のノードのアドレス
この2つのフィールドを持つノード・クラスを定義してみましょう。
class Node(object):
def __init__(self, data=None, next_node=None):
self.data = data
self.next_node = next_node
|
Linked-List クラスの作成
リンクリストを作成するために、空のノードを初期化するクラスをもうひとつ作ってみましょう。
class LinkedList(object):
def __init__(self, head=None):
self.head = head
|
このクラスには、いくつかの重要な関数が用意されています。
それぞれのクラスの目的と定義を確認しましょう。
1. リストを表示する関数
リンクリストを印刷する関数を書いてみましょう。
リンクリストを印刷するには、リスト全体を走査して、各ノードのデータを印刷し続ける必要があります。
def printList(self):
temp = self.head
while (temp):
print (temp.data, " -> ", end = '')
temp = temp.next_node
print("")
|
2. リストの大きさを取得する
リンクリストのサイズを返す関数を書いてみましょう。
サイズを計算するためには、リスト全体を走査し、カウンターを保持する必要があります。
def size(self):
current = self.head
count = 0
while current:
count += 1
current = current.next_node
return count
|
この関数はリンクリストのサイズを返します。
3. 新しいノードを先頭に挿入する
新しいノードを先頭に挿入する関数を書いてみましょう。
def insert_at_head(self, data): new_node = Node(data)
new_node.next_node = self.head
self.head = new_node
|
これはデータを持つ新しいノードを作り、それをheadの前に追加します。
そして、リンクリストの先頭をこの新しいノードに向ける。
4. 次のノードの取得
次のノードを取得するための関数を以下に示す。
def get_next_node (self,node):
return node.next_node.data
|
新しいリンクドリストを作成する
上記で作成したクラスを使って、main関数を書き、リンクリストを作成しましょう。
llist = LinkedList()
|
このコードでは、llist オブジェクトを空のノードで初期化しています。
1. ノードの追加
このノードにデータを追加してみましょう。
llist.head = Node(1)
|
リンクリストのための他のノードをいくつか作成します。
s = Node(2)t = Node(3) |
2. ノード間のリンクの作成
個々のノード間のリンクを作成することは、リンクリストを作成する上で最も重要な部分です。
リンクの作成には、.NET Frameworkを使用します。
llist.head.next_node = s
s.next_node = t
|
3. リストのノードを印刷する
リストが正常に作成されたかどうかを確認するために、print機能を使用することができます。
llist.printList() |
結果を出力すると、以下の様になります。
1 -> 2 -> 3 |
4. リストの大きさを出力する
リストの大きさを出力するには、上で書いた size 関数を呼び出します。
print(llist.size())
|
結果は以下の通りです。
3 |
5. 新しいノードを挿入する
上の関数を使って、リンクリストの先頭にデータを挿入してみましょう。
llist.insert_at_head(5)
|
リストを印刷して検証してみましょう。
llist.printList() |
結果は以下の通りです。
5 -> 1 -> 2 -> 3 |
6. 次のノードを取得する
次のノードを取得します。
print(llist.get_next_node(s))
|
結果を出力すると、以下の様になります。
3 |
Pythonによるリンクリストの完全な実装
完全な実装は以下の通りです。
class Node(object):
def __init__(self, data=None, next_node=None):
self.data = data
self.next_node = next_node
class LinkedList(object):
def __init__(self, head=None):
self.head = head
def size(self):
current = self.head
count = 0
while current:
count += 1
current = current.next_node
return count
def printList(self):
temp = self.head
while (temp):
print (temp.data, " -> ", end = '')
temp = temp.next_node
print("")
def insert_at_head(self, data):
new_node = Node(data)
new_node.next_node = self.head
self.head = new_node
def get_next_node (self,node):
return node.next_node.data
if __name__=='__main__':
llist = LinkedList()
llist.head = Node(1)
s = Node(2)
t = Node(3)
llist.head.next_node = s;
s.next_node = t
llist.printList()
print(s.data)
print(llist.size())
print(llist.get_next_node(s))
llist.insert_at_head(5)
llist.printList()
|
まとめ
この記事では、Pythonでのリンクリストの実装を取り上げました。
私たちはゼロから独自のリンクリストを作成し、リストを表示し、リストのサイズを取得し、先頭に挿入を行うためのいくつかの追加関数を書きました。