連結リスト（Linked List）とは
連結リスト（Linked List）とは、
です。
ノードは、データとともに次のノードへのリンク（ポインタ）を持っています。
連結リストはノードのリンクで繋がっていて、リンクを辿っていくことで各データにアクセスすることができます。
連結リストには、主に2つの種類があります。
連結リスト（Linked List）の計算量
連結リスト（Linked List）における各操作の計算量は以下のようになります。
| 連結リスト（Linked List） |
|
| 要素の参照 | O(n) |
| 要素の追加 |
O(1) |
| 要素の削除 | O(1) |
要素の参照をする際には頭からデータをたどる必要があるため、O(n)の計算量となってしまいます。
連結リスト（Linked List）の実装方法
連結リスト（Linked List）はclassで簡単に実装することができます。
# 単方向連結リスト
class LinkedList:
def __init__(self, value=None, next=None):
self.value = value
self.next = next10→20→50の連結リストを作成してみます。
root = LinkedList(10)
root.next = LinkedList(20)
root.next.next = LinkedList(50)
# 中身の確認
current = root
while current:
print(current.value)
current = current.next10
20
50
要素の追加をしてみます。
追加するノードのポインタと追加するノードの1つ前のノードのポインタの書き換えが必要になります。
# 要素の追加
new_node = LinkedList(30)
new_node.next = root.next
root.next = new_node
current = root
while current:
print(current.value)
current = current.next10
30
20
50
続いて要素の削除を行います。
削除するノードの1つ前のノードのポインタを書き換えれば完了です。
# 要素の削除
root.next = root.next.next
current = root
while current:
print(current.value)
current = current.next10
20
50
参考文献
コメント