リスト: 単方向リストと両方向リスト

5.1 リストの定義とその種類

リスト はデータ要素（ノード）から成る動的なデータ構造で、各ノードはデータと他のノードへのリンクを含んでいます。配列とは異なり、リストはプログラム実行中にサイズを変更できます。

重要！ ここで述べているのはPythonのlistクラスではなく、アルゴリズム理論におけるデータ構造のことです。

リストの種類:

• 単方向リスト (Singly Linked List): 各ノードはデータと次のノードへのリンクを持っています。
• 両方向リスト (Doubly Linked List): 各ノードはデータ、次のノードへのリンク、および前のノードへのリンクを持っています。

5.2 単方向リストの動作原理

単方向リストの構造:

• ノード (Node): データと次のノードへのリンクの2つの部分から成ります。
• ヘッド (Head): リストの最初のノードへのポインタです。

動作原理:

• ノードの追加: 新しいノードを作成し、最後のノードのリンクを新しいノードに更新することで行われます。
• ノードの削除: 削除されるノードの次のノードへの前のノードのリンクを更新する必要があります。

実装例:

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

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

    def append(self, data):
        new_node = Node(data)
        if not self.head:
            self.head = new_node
            return
        last = self.head
        while last.next:
            last = last.next
        last.next = new_node

    def display(self):
        current = self.head
        while current:
            print(current.data, end=" -> ")
            current = current.next
        print("None")

# 使用例:
sll = SinglyLinkedList()
sll.append(1)
sll.append(2)
sll.append(3)
sll.display()  # 出力: 1 -> 2 -> 3 -> None

5.3 両方向リストの動作原理

両方向リストの構造:

• ノード (Node): データ、次のノードへのリンク、および前のノードへのリンクの3つの部分から成ります。
• ヘッド (Head): リストの最初のノードへのポインタです。
• テイル (Tail): リストの最後のノードへのポインタ（必須ではありませんが、よく使用されます）。

動作原理:

• ノードの追加: 新しいノードを作成し、最後のノードと新しいノードのリンクを更新することで行われます。
• ノードの削除: 削除されるノードの前後のノードのリンクを更新する必要があります。

実装例:

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

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

    def append(self, data):
        new_node = Node(data)
        if not self.head:
            self.head = new_node
            return
        last = self.head
        while last.next:
            last = last.next
        last.next = new_node
        new_node.prev = last

    def display(self):
        current = self.head
        while current:
            print(current.data, end=" <-> ")
            current = current.next
        print("None")

# 使用例:
dll = DoublyLinkedList()
dll.append(1)
dll.append(2)
dll.append(3)
dll.display()  # 出力: 1 <-> 2 <-> 3 <-> None

5.4 基本操作

基本操作: 挿入、削除、検索

挿入:

• 単方向リスト: 新しいノードをリストの末尾に挿入するには すべてのノードを最後までたどる必要がありますので、最後のノードのリンクを更新します。
• 両方向リスト: 新しいノードをリストの末尾に挿入するのは単方向リストと同様ですが、新しいノードのprevリンクも前のノードに更新する必要があります。

削除:

• 単方向リスト: ノードの削除には、 削除するノードまでリストをたどり、削除されるノードの次のノードへの前のノードのリンクを更新する必要があります。
• 両方向リスト: ノードの削除には、削除されるノードの隣接ノードのnextおよびprevリンクを更新する必要があります。

検索: リストをヘッドからテイルまでたどり、各ノードのデータを検索値と比較します。時間の計算量はO(n)です。

5.5 リストの使用例

例として、単方向リストを使用してスタックを実装してみましょう。

スタックは、単方向リストを使って、要素を追加するpushメソッドと削除するpopメソッドを使用して簡単に実装できます。2つのメソッドがあります:

• push — リストの末尾に新しい要素を追加する
• pop — リストの末尾から最後の要素を取り出す

実装例:

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

class Stack:
    def __init__(self):
        self.top = None

    def push(self, data):
        new_node = Node(data)
        new_node.next = self.top
        self.top = new_node

    def pop(self):
        if not self.top:
            return None
        data = self.top.data
        self.top = self.top.next
        return data

    def display(self):
        current = self.top
        while current:
            print(current.data, end=" -> ")
            current = current.next
        print("None")

# 使用例:
stack = Stack()
stack.push(1)
stack.push(2)
stack.push(3)
stack.display()  # 出力: 3 -> 2 -> 1 -> None
print(stack.pop())  # 出力: 3
stack.display()  # 出力: 2 -> 1 -> None