Python日記vol.21🐍連結リストのもやっとを吐き出してみる
こんにちは。aliceです。
昨日はノンプロ研のPython輪読会でした。
本はこちら📖
Pythonというより数学ですね。
土曜の夜になれない数学の話をするのは、なんともおもしろいものです。
好きか嫌いかと聞かれたら好きなんですけどね。
理解するのに時間がかかる。というより理解したとは言い難い。
言っている意味がわからん。
ChatGPTに聞いても、そもそもそれがあっているのかがわからない。
という状態なのですが、このもやっとした気持ちを吐き出したいと思ったので、思い出にnoteに書きます。
はじめに
最初に書いたとおり、このnoteはもやっとを吐き出すためのnoteです。
内容があっているか・違っているかはわかりません！
といういつも以上にゆるーい内容なことをご理解ください。
連結リスト
連結リストとは
連結リストは、データを小さな部品（ノードと呼ばれます）に分けて、それらをつなげてデータを保存するリストの一種です。
ねぇ、chatGPT。
連結リストを小学生にわかるように説明して🙏
連結リストは、データをつなげて保存する特別なリストです。通常のリスト（配列）は、データを隣り合った場所に順番に保存しますが、連結リストはデータを小さなパズルのピースのようにつなげて保存します。
それぞれのデータは、自分のピース（ノードと呼びます）を持っています。そして、そのピースには、自分のデータと、次にどのピースに進むかを教える手紙（ポインタ）があります。
例えば、次のような話にできます：
連結リストは、友達が手紙を渡すゲームのようなものです。各友達は手紙を持っており、その手紙には次の友達の名前が書いています。友達同士は手紙を渡しあって、順番につながっています。手紙を持つ友達がデータで、手紙の中の次の友達の名前が次のデータを教えてくれるのです。
このように連結リストは、データを順番につなげて、一つずつたどっていくことができる特別なリストなんです。
連結リストの挿入
連結リストにデータを挿入する場合、新しいデータをノードに包み込み、それを既存のリストの中に差し込むことができます。
この新しいノードは、既存のノードとリンクされ、データを保持します。
このように、連結リストに新しいデータを挿入することができます。
２と３の間に新しいデータを入れてみます。
連結リストの削除
連結リストからデータを削除する場合、削除したいノードを見つけてそれをリストから取り除きます。
２を取り除きました。
連結リストの読み取り
連結リストは通常、要素にアクセスするには先頭から順番に読み取る必要があるデータ構造のため、インデックスを使用して要素を直接指定することはできません。
連結リストは、各要素（ノード）が次の要素へのリンク（ポインタ）を持っており、リストの最初から順番にノードをたどっていくことで、要素にアクセスします。
リストと連結リストの使い分け
連結リストは、挿入・削除する位置が特定できているとO(1)で処理できます。
ChatGPTにコードを書いてもらった
これだと「へー」で終わるのでChatGPTにコードを書いてもらいました。
書いてもらったところで「へー」で終わりました。
連結リストを作成する
連結リストを作成します。
意味がわからないため、コメント多めです。
# ノードを表すクラスを定義します
class Node:
def __init__(self, data):
self.data = data # データを格納する
self.next = None # 次のノードへの参照
# 連結リストを表すクラスを定義します
class LinkedList:
def __init__(self): # 連結リストの初期化
self.head = None # 最初のノードへの参照
# リストの最後に要素を追加するメソッド
def append(self, data): # リストの最後に要素を追加するメソッド
new_node = Node(data) # 新しいノードを作成
if not self.head: # リストが空の場合
self.head = new_node # リストの先頭に新しいノードを追加
return # メソッドを終了
current = self.head # リストの先頭を current とする
while current.next: # current が最後のノードでない限り
current = current.next # current を次のノードに更新
current.next = new_node # 最後のノードの次に新しいノードを追加
# リストの要素を表示するメソッド
def display(self): # リストの要素を表示するメソッド
current = self.head # リストの先頭を current とする
while current: # current が None になるまで
print(current.data, end=" -> ") # current のデータを表示
current = current.next # current を次のノードに更新
print("None") # None を表示
# 連結リストを作成して操作してみましょう
my_linked_list = LinkedList()
my_linked_list.append(1)
my_linked_list.append(2)
my_linked_list.append(3)
my_linked_list.display()実行結果はこちら。
このよう連結リストが作成されました。
といってもわからないので、中身をチェック🧐
データと次のアドレスを持ったノードがある連結リストが作られました。（多分）
連結リストの挿入
次は連結リストを挿入します。
# ノードを表すクラスを定義します
class Node:
def __init__(self, data):
self.data = data # データを格納する
self.next = None # 次のノードへの参照
# 連結リストを表すクラスを定義します
class LinkedList:
def __init__(self): # 連結リストの初期化
self.head = None # 最初のノードへの参照
# リストの最後に要素を追加するメソッド
def append(self, data): # リストの最後に要素を追加するメソッド
new_node = Node(data) # 新しいノードを作成
if not self.head: # リストが空の場合
self.head = new_node # リストの先頭に新しいノードを追加
return # メソッドを終了
current = self.head # リストの先頭を current とする
while current.next: # current が最後のノードでない限り
current = current.next # current を次のノードに更新
current.next = new_node # 最後のノードの次に新しいノードを追加
# リストの要素を表示するメソッド
def display(self): # リストの要素を表示するメソッド
current = self.head # リストの先頭を current とする
while current: # current が None になるまで
print(current.data, end=" -> ") # current のデータを表示
current = current.next # current を次のノードに更新
print("None") # None を表示
# 指定した位置に要素を挿入するメソッド
def insert_at(self, position, data):
new_node = Node(data) # 新しいノードを作成
if position < 0: # 指定した位置が不正な場合
print("Invalid position") # エラーメッセージを表示
return # 挿入操作を終了
if position == 0: # 先頭に挿入する場合
new_node.next = self.head # 新しいノードのnextを現在の先頭にする
self.head = new_node # リストの先頭を新しいノードにする
if new_node.next: # 元々先頭にノードが存在していた場合
new_node.next.prev = new_node # 元々先頭だったノードのprevを新しいノードにする
return # 挿入操作を終了
current = self.head # 現在のノード
prev = None # 1つ前のノード
count = 0 # 現在の位置
while current and count < position: # 指定した位置まで移動
prev = current # 1つ前のノードを保持
current = current.next # 次のノードに移動
count += 1 # カウントを1増やす
if current: # 指定した位置が有効な場合
prev.next = new_node # 1つ前のノードのnextを新しいノードにする
new_node.prev = prev # 新しいノードのprevを1つ前のノードにする
new_node.next = current # 新しいノードのnextをcurrentにする
current.prev = new_node # currentのprevを新しいノードにする
else:
print("Invalid position")
# 連結リストを作成して操作してみましょう
my_linked_list = LinkedList() # 連結リストを作成
for i in range(1, 5): # 1から4までのデータを追加
my_linked_list.append(i)
# 2の後ろに5をO挿入
my_linked_list.insert_at(2, 5)
my_linked_list.display()実行結果はこちら
挿入前の連結リスト
挿入後の連結リスト
新しいノードが追加されました。
連結リストの削除
最後に連結リストを削除します。
# ノードを表すクラスを定義します
class Node:
def __init__(self, data):
self.data = data # データを格納する
self.next = None # 次のノードへの参照
# 連結リストを表すクラスを定義します
class LinkedList:
def __init__(self): # 連結リストの初期化
self.head = None # 最初のノードへの参照
# リストの最後に要素を追加するメソッド
def append(self, data): # リストの最後に要素を追加するメソッド
new_node = Node(data) # 新しいノードを作成
if not self.head: # リストが空の場合
self.head = new_node # リストの先頭に新しいノードを追加
return # メソッドを終了
current = self.head # リストの先頭を current とする
while current.next: # current が最後のノードでない限り
current = current.next # current を次のノードに更新
current.next = new_node # 最後のノードの次に新しいノードを追加
# リストの要素を表示するメソッド
def display(self): # リストの要素を表示するメソッド
current = self.head # リストの先頭を current とする
while current: # current が None になるまで
print(current.data, end=" -> ") # current のデータを表示
current = current.next # current を次のノードに更新
print("None") # None を表示
# リストの要素を削除するメソッド
def remove(self, node_to_remove): # リストの要素を削除するメソッド
if not node_to_remove: # 削除するノードがない場合
return # メソッドを終了
if node_to_remove.next:
# 次のノードがある場合、次のノードのデータを現在のノードにコピーし、次のノードを削除
node_to_remove.data = node_to_remove.next.data # 次のノードのデータを現在のノードにコピー
node_to_remove.next = node_to_remove.next.next # 次のノードを削除
else:
# 次のノードがない場合、現在のノードを単純に削除
current = self.head # リストの先頭を current とする
prev = None # current の前のノードを None とする
# 連結リストを作成
my_linked_list = LinkedList()
for i in range(1, 5):
my_linked_list.append(i)
# 削除前の連結リストを表示
print("削除前:")
my_linked_list.display()
# 2番目の要素を削除（O(1) で削除）
node_to_remove = my_linked_list.head
for _ in range(1): # 2番目の要素まで移動
node_to_remove = node_to_remove.next # 次のノードに移動
my_linked_list.remove(node_to_remove) # 2番目の要素を削除
# 削除後の連結リストを表示
print("削除後:")
my_linked_list.display()実行結果はこちら
削除前の連結リスト
削除後の連結リスト
２のノードが削除されてリンクも変更されました。
もやっとポイント
連結リストは要素にアクセスするには先頭から順番に読み取る必要があるってことは、挿入するにも削除するにも、その場所までは順番にたどっていかないとたどり着かないんじゃない？と思いました。（素人発想）
そのためにfor文とかwhile文を使っているのでしょう。
挿入や削除する場所が連結リストの後ろの方のときは、普通のリストの場合と比べて計算量はそんなに変わらないとはならないのかな？
「位置の特定」とは？？
もやっとをぶつけてみる
挿入する位置が特定できるときはO(1)でできるの？
ポインタは用意できるの？
何に使うんだろう、連結リスト
いちばんのもやっとは今までの説明とコードがあっているか全くわからないということです。
もやっと、おしまい。
この記事が気に入ったらサポートをしてみませんか？