連結リスト - データサイエンス関連+αのメモ

連結リスト（Linked List） は、各要素（ノード）がデータと次の要素への参照（ポインタ）を持つデータ構造

配列と異なり、メモリ上に連続して配置される必要がない

特徴：

要素の挿入・削除が $O(1)$ で可能（位置がわかっている場合）
任意の位置へのアクセスは $O(n)$ （先頭から順にたどる必要がある）
メモリの動的な割り当てが可能

操作：

insert(x): リストに要素xを挿入する
delete(x): リストから要素xを削除する
search(x): リストから要素xを検索する

class Node:
    def __init__(self, data):
        self.data = data
        self.next = None


class LinkedList:
    def __init__(self):
        self.head = None

    def insert(self, data):
        """先頭に要素を挿入"""
        new_node = Node(data)
        new_node.next = self.head
        self.head = new_node

    def delete(self, data):
        """指定した値を持つ最初のノードを削除"""
        if self.head is None:
            return

        # 先頭ノードが削除対象の場合
        if self.head.data == data:
            self.head = self.head.next
            return

        # 削除対象のノードを探す
        current = self.head
        while current.next is not None:
            if current.next.data == data:
                current.next = current.next.next
                return
            current = current.next

    def search(self, data):
        """指定した値を持つノードを検索"""
        current = self.head
        while current is not None:
            if current.data == data:
                return True
            current = current.next
        return False

    def display(self):
        """リストの全要素を表示"""
        elements = []
        current = self.head
        while current is not None:
            elements.append(current.data)
            current = current.next
        return elements

# 使用例
ll = LinkedList()
ll.insert(3)
ll.insert(2)
ll.insert(1)
print("リスト:", ll.display())
print("2を検索:", ll.search(2))
ll.delete(2)
print("2を削除後:", ll.display())

リスト: [1, 2, 3]
2を検索: True
2を削除後: [1, 3]

NOTE: Pythonのlistは動的配列

そのためlist[i]での参照は $O(1)$ で速く、挿入・削除が遅い

特性	Python `list`	連結リスト
メモリ配置	連続	非連続
`lst[i]` の計算量	O(1)	O(n)
末尾 `append`	平均 O(1)（償却）	O(1)
途中挿入・削除	O(n)（シフトが必要）	O(1)（参照があれば）
キャッシュ効率	良い	悪い