Pythonの単方向連結リスト

はじめに

データ構造の連結リストの勉強をしていて、頭の中がこんがらがったので、そのメモ。Rのことではないので、Pythonブログを作成した際に引っ越しするまでのメモ。

Unidirectional Linked List

from __future__ import annotations
from typing import Any

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

class LinkedList(object):
    def __init__(self, head=None) -> None:
        self.head = head

    def append(self, data: Any) -> None:
        new_node = Node(data)
        if self.head is None:
            self.head = new_node
            return

        last_node = self.head
        while last_node.next:
            last_node = last_node.next
        last_node.next = new_node

    def insert(self, data: Any) -> None:
        new_node = Node(data)
        new_node.next = self.head
        self.head = new_node

    def print(self) -> None:
        current_node = self.head
        while current_node:
            print(current_node.data)
            current_node = current_node.next

    def remove(self, data: Any) -> None:
        current_node = self.head
        if current_node and current_node.data == data:
            self.head = current_node.next
            current_node = None
            return

        previous_node = None
        while current_node and current_node.data != data:
            previous_node = current_node
            current_node = current_node.next

        if current_node is None:
            return

        previous_node.next = current_node.next
        current_node = None

    def reverse(self) -> None:
        previous_node = None
        current_node = self.head

        while current_node:
            next_node = current_node.next
            current_node.next = previous_node
            previous_node = current_node
            current_node = next_node

        self.head = previous_node

if __name__ == '__main__':
    l = LinkedList()
    l.append(10)
    l.append(20)
    l.append(30)
    l.append(40)
    l.insert(0)
    l.append(50)
    l.remove(20)
    l.print()

# 50
# 40
# 30
# 10
# 0

下記の画像は、プログラムの正確な挙動ではない。各appendやInsert、removeのタイミングで、その前にどのような変数が保存されていて、どのような書き換えがあったのかのイメージ。