Pythonでリストを実装します。
以下を参照しています。
Data-Structures-using-Python/Linked Lists/SinglyLinkedList.py
連結リスト（linked list）
連結リストは、データが順番を持ち並んだデータ構造を実現します。
連結リストでデータを格納する領域をノードと言います。このノードに、次のノードを指し示すポインタを持たせることで、順序付けられたデータ構造を実現します。
連結リスト（れんけつリスト、英語: Linked list）は、最も基本的なデータ構造の1つであり、他のデータ構造の実装に使われる。リンクリスト、リンクトリストとも表記される。
一連のノードが、任意のデータフィールド群を持ち、1つか2つの参照（リンク）により次（および前）のノードを指している。連結リストの主な利点は、リスト上のノードを様々な順番で検索可能な点である。連結リストは自己参照型のデータ型であり、同じデータ型の別のノードへのリンク（またはポインタ）を含んでいる。連結リストは場所が分かっていれば、ノードの挿入や削除を定数時間で行うことができる（場所を探すのにかかる時間はリスト上の順番の条件などにも依存するし、後述する片方向リストなのか双方向リストなのかにも依存する）。連結リストにはいくつかの種類があり、片方向リスト、双方向リスト、線形リスト、循環リストなどがある。
出典: フリー百科事典『ウィキペディア（Wikipedia）』
リストの基本的な機能
- データの参照
- データの挿入
- データの削除
片方向リスト（singly-linked list）
連結リストの中で最も単純な構造を持ちます。
片方向リスト（singly-linked list）は、最も単純な連結リストであり、ノード毎に1つのリンクを持つ。このリンクはリスト上の次のノードを指し、リストの最後尾ならNull値を格納するか、空のリストを指す。
出典: フリー百科事典『ウィキペディア（Wikipedia）』
class Node():
# それぞれのノードはデータと次のノードへのリンクを持つ。
def __init__(self, data, next = None):
self.data = data
self.next = next
# データを設定する。
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
class LinkedList():
# リストの先頭
def __init__(self):
self.head = None
self.length = 0
def list_length(self):
temp = self.head
count = 0
while temp is not None:
count += 1
temp = temp.get_next()
return count
片方向リストのデータの参照
データの出力
- ノードの持つリンクを辿る。
- 参照したノードのデータを表示する。
- 次のリンクがNullであれば終了する。
# データの出力
def print_linked_list(self):
temp = self.head
while temp:
print(temp.data, end=' ')
temp = temp.next
データの検索
# データの検索
def search(self, node, data):
if node is None:
return False
if node.data == data:
return True
return self.search(node.get_next(), data)
片方向リストのデータの挿入
- ノードを先頭に挿入する。
- ノードを最後に挿入する。
- ノードを間に挿入する。
先頭に挿入
- 現在の先頭のノードを新しいノードの次のノードに設定して、新しいノードを先頭にする。
# 先頭にノードを挿入する。
def insert_at_start(self, data):
length = self.list_length()
new_node = Node(data)
if self.head == None:
self.head = new_node
else:
new_node.set_next(self.head)
self.head = new_node
self.length = length + 1
最後に挿入
- 最後まで移動し、新しいノードを設定する。
# 最後にノードを挿入する。
def insert_at_end(self, data):
length = self.list_length()
new_node = Node(data)
temp = self.head
# 最後のノードまで移動する。
while temp.get_next() is not None:
temp = temp.get_next()
temp.next = new_node
self.length = length + 1
間に挿入
- ノードを挿入する前の位置に移動して、現在位置とする。
- 新しいノードの次のノードとして、現在位置の次のノードを設定する。
- 新しいノードを現在位置の次に設定する。
# ある場所にノードを挿入する。
def insert_position(self, position, data):
if position < 0 or position > self.length:
raise ValueError
else:
if position == 0:
self.insert_at_start(data)
else:
if position == self.length:
self.insert_at_end(data)
else:
length = self.list_length()
new_node = Node(data)
count = 0
temp = self.head
while count < position -1:
count += 1
temp = temp.get_next()
new_node.set_next(temp.get_next())
temp.set_next(new_node)
self.length = length + 1
片方向リストのデータの削除
- 先頭のノードが削除するノードであれば削除し、次のノードを先頭にする。
- 間から最後のノードを削除する場合は、最初から検索し、前のデータのリンクを、次の次のデータにする。
# データに基づきノードを削除する。
def delete(self, data):
length = self.list_length()
temp = self.head
# 削除するノードが先頭の場合
if (temp.next is not None):
if(temp.data == data):
self.head = temp.get_next()
temp = None
self.length = length - 1
return
else:
# ノードを検索する。
while temp.next is not None:
if temp.data == data:
break
# 現在のノードを一つ前のノードとして保存し、次に進む。
prev = temp
temp = temp.get_next()
# ノードが見つからなかった場合。
if temp is None:
return
self.length = length - 1
prev.next = temp.get_next()
return
片方向リストのコード
class Node():
# それぞれのノードはデータと次のノードへのリンクを持つ。
def __init__(self, data, next = None):
self.data = data
self.next = next
# データを設定する。
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
class LinkedList():
# リストの先頭
def __init__(self):
self.head = None
self.length = 0
def list_length(self):
temp = self.head
count = 0
while temp is not None:
count += 1
temp = temp.get_next()
return count
# データの出力
def print_linked_list(self):
temp = self.head
while temp:
print(temp.data, end=' ')
temp = temp.next
# 先頭にノードを挿入する。
def insert_at_start(self, data):
length = self.list_length()
new_node = Node(data)
if self.head == None:
self.head = new_node
else:
new_node.set_next(self.head)
self.head = new_node
self.length = length + 1
# 最後にノードを挿入する。
def insert_at_end(self, data):
length = self.list_length()
new_node = Node(data)
temp = self.head
# 最後のノードまで移動する。
while temp.get_next() is not None:
temp = temp.get_next()
temp.next = new_node
self.length = length + 1
# ある場所にノードを挿入する。
def insert_position(self, position, data):
if position < 0 or position > self.length:
raise ValueError
else:
if position == 0:
self.insert_at_start(data)
else:
if position == self.length:
self.insert_at_end(data)
else:
length = self.list_length()
new_node = Node(data)
count = 0
temp = self.head
while count < position -1:
count += 1
temp = temp.get_next()
new_node.set_next(temp.get_next())
temp.set_next(new_node)
self.length = length + 1
# データに基づきノードを削除する。
def delete(self, data):
length = self.list_length()
temp = self.head
# 削除するノードが先頭の場合
if (temp.next is not None):
if(temp.data == data):
self.head = temp.get_next()
temp = None
self.length = length - 1
return
else:
# ノードを検索する。
while temp.next is not None:
if temp.data == data:
break
# 現在のノードを一つ前のノードとして保存し、次に進む。
prev = temp
temp = temp.get_next()
# ノードが見つからなかった場合。
if temp is None:
return
self.length = length - 1
prev.next = temp.get_next()
return
# データの検索
def search(self, node, data):
if node is None:
return False
if node.data == data:
return True
return self.search(node.get_next(), data)
if __name__ == '__main__':
List = LinkedList()
# ノード1
List.insert_at_start(1)
# ノード1 -> ノード2
List.insert_at_end(2)
# ノード1 -> ノード2 -> ノード3
List.insert_at_end(3)
# ノード4 -> ノード1 -> ノード2 -> ノード3
List.insert_at_start(4)
# ノード4 -> ノード1 -> ノード2 -> ノード5 -> ノード3
List.insert_position(3, 5)
# ノード4 -> ノード1 -> ノード2 -> ノード5 -> ノード3 -> ノード6
List.insert_at_end(6)
List.print_linked_list()
print()
# ノード4 -> ノード1 -> ノード2 -> ノード5 -> ノード6
List.delete(3)
List.print_linked_list()
print()
print(List.search(List.head, 1))