【Python】線形リスト(連結リスト)【アルゴリズム】

# 線形リスト

from __future__ import annotations
from typing import Any, Type

class Node:
    """線形リスト用ノードクラス"""

    def __init__(self, data: Any = None, next: Node = None):
        """初期化"""
        self.data = data  # データ
        self.next = next  # 後続ポインタ

class LinkedList:
    """線形リストクラス"""

    def __init__(self) -> None:
        """初期化"""
        self.no = 0          # ノードの個数
        self.head = None     # 先頭ノードへの参照
        self.current = None  # 着目ノードへの参照

    def __len__(self) -> int:
        """線形リスト上のノード数を返却"""
        return self.no

head is None

head.next is None

head.next.next is None

p.next is None

def search(self, data: Any) -> int:
    """dataと等価なノードを探索"""
    cnt = 0
    ptr = self.head

    while ptr is not None:
        if ptr.data == data:
            self.current = ptr
            return cnt
        cnt += 1
        ptr = ptr.next
    return -1

def add_first(self, data: Any) -> None:
    """先頭にノードを挿入"""
    ptr = self.head  # 挿入前の先頭ノード
    self.head = self.current = Node(data, ptr)
    self.no += 1

def add_last(self, data: Any):
    """末尾にノードを挿入"""
    if self.head is None:     # リストが空であれば
        self.add_first(data)  # 先頭に挿入
    else:
        ptr = self.head
        while ptr.next is not None:
            ptr = ptr.next
        ptr.next = self.current = Node(data, None)
        self.no += 1

def remove_first(self) -> None:
    """先頭ノードを削除"""
    if self.head is not None:  # リストが空でなければ
        self.head = self.current = self.head.next
    self.no -= 1

def remove_last(self):
    """末尾ノードを削除"""
    if self.head is not None:
        if self.head.next is None: # ノードが1個だけであれば
            self.remove_first()    # 先頭ノードを削除
        else:
            ptr = self.head        # 走査中のノード
            pre = self.head        # 走査中のノードの先行ノード

            while ptr.next is not None:
                pre = ptr
                ptr = ptr.next
            pre.next = None        # preは削除後の末尾ノード
            self.current = pre
            self.no -= 1

def remove(self, p: Node) -> None:
    """ノードpを削除"""
    if self.head is not None:
        if p is self.head:       # pが先頭ノードであれば
            self.remove_first()  # 先頭ノードを削除
        else:
            ptr = self.head

            while ptr.next is not p:
                ptr = ptr.next
                if ptr is None:
                    return       # ptrはリストに存在しない
            ptr.next = p.next
            self.current = ptr
            self.no -= 1

def remove_current_node(self) -> None:
    """着目ノードを削除"""
    self.remove(self.current)

def clear(self) -> None:
    """全ノードを削除"""
    while self.head is not None: # 空になるまで
        self.remove_first()      # 先頭ノードを削除
    self.current = None
    self.no = 0

def next(self) -> bool:
    """着目ノードを一つ後方に進める"""
    if self.current is None or self.current.next is None:
        return False             # 進めることができなかった
    self.current = self.current.next
    return True

def print_current_node(self) -> None:
    """着目ノードを表示"""
    if self.current is None:
        print('着目ノードはありません。')
    else:
        print(self.current.data)

def print(self) -> None:
    """全ノードを表示"""
    ptr = self.head

    while ptr is not None:
        print(ptr.data)
        ptr = ptr.next

# 線形リスト

from __future__ import annotations
from typing import Any, Type

class Node:
    """線形リスト用ノードクラス"""

    def __init__(self, data: Any = None, next: Node = None):
        """初期化"""
        self.data = data  # データ
        self.next = next  # 後続ポインタ

class LinkedList:
    """線形リストクラス"""

    def __init__(self) -> None:
        """初期化"""
        self.no = 0          # ノードの個数
        self.head = None     # 先頭ノードへの参照
        self.current = None  # 着目ノードへの参照

    def __len__(self) -> int:
        """線形リスト上のノード数を返却"""
        return self.no

    def search(self, data: Any) -> int:
        """dataと等価なノードを探索"""
        cnt = 0
        ptr = self.head

        while ptr is not None:
            if ptr.data == data:
                self.current = ptr
                return cnt
            cnt += 1
            ptr = ptr.next
        return -1

    def add_first(self, data: Any) -> None:
        """先頭にノードを挿入"""
        ptr = self.head  # 挿入前の先頭ノード
        self.head = self.current = Node(data, ptr)
        self.no += 1

    def add_last(self, data: Any):
        """末尾にノードを挿入"""
        if self.head is None:     # リストが空であれば
            self.add_first(data)  # 先頭に挿入
        else:
            ptr = self.head
            while ptr.next is not None:
                ptr = ptr.next
            ptr.next = self.current = Node(data, None)
            self.no += 1

    def remove_first(self) -> None:
        """先頭ノードを削除"""
        if self.head is not None:  # リストが空でなければ
            self.head = self.current = self.head.next
        self.no -= 1

    def remove_last(self):
        """末尾ノードを削除"""
        if self.head is not None:
            if self.head.next is None: # ノードが1個だけであれば
                self.remove_first()    # 先頭ノードを削除
            else:
                ptr = self.head        # 走査中のノード
                pre = self.head        # 走査中のノードの先行ノード

                while ptr.next is not None:
                    pre = ptr
                    ptr = ptr.next
                pre.next = None        # preは削除後の末尾ノード
                self.current = pre
                self.no -= 1

    def remove(self, p: Node) -> None:
        """ノードpを削除"""
        if self.head is not None:
            if p is self.head:       # pが先頭ノードであれば
                self.remove_first()  # 先頭ノードを削除
            else:
                ptr = self.head

                while ptr.next is not p:
                    ptr = ptr.next
                    if ptr is None:
                        return       # ptrはリストに存在しない
                ptr.next = p.next
                self.current = ptr
                self.no -= 1

    def remove_current_node(self) -> None:
        """着目ノードを削除"""
        self.remove(self.current)

    def clear(self) -> None:
        """全ノードを削除"""
        while self.head is not None: # 空になるまで
            self.remove_first()      # 先頭ノードを削除
        self.current = None
        self.no = 0

    def next(self) -> bool:
        """着目ノードを一つ後方に進める"""
        if self.current is None or self.current.next is None:
            return False             # 進めることができなかった
        self.current = self.current.next
        return True

    def print_current_node(self) -> None:
        """着目ノードを表示"""
        if self.current is None:
            print('着目ノードはありません。')
        else:
            print(self.current.data)


    def print(self) -> None:
        """全ノードを表示"""
        ptr = self.head

        while ptr is not None:
            print(ptr.data)
            ptr = ptr.next

# 線形リストクラスLinkedListの利用例

from enum import Enum
from linked_list import LinkedList

Menu = Enum('Menu', ['先頭に挿入', '末尾に挿入', '先頭を削除', '末尾を削除',
                     '着目を表示', '着目を進める', '着目を削除', '全削除',
                     '探索', '全ノードを表示', '終了'])

def select_Menu() -> Menu:
    """メニュー選択"""
    s = [f'({m.value}){m.name}' for m in Menu]

    while True:
        print(*s, sep=' ', end='')
        n = int(input(' : '))
        if 1 <= n <= len(Menu):
            return Menu(n)


lst = LinkedList()                    # 線形リストを生成

while True:
    menu = select_Menu()              # メニュー選択

    if menu == Menu.先頭に挿入:       # 先頭に挿入
        lst.add_first(int(input('値 : ')))

    elif menu == Menu.末尾に挿入:     # 末尾に挿入
        lst.add_last(int(input('値 : ')))

    elif menu == Menu.先頭を削除:     # 先頭を削除
        lst.remove_first()

    elif menu == Menu.末尾を削除:     # 末尾を削除
        lst.remove_last()

    elif menu == Menu.着目を表示:     # 着目を表示
        lst.print_current_node()

    elif menu == Menu.着目を進める:   # 着目を進める
        lst.next()

    elif menu == Menu.着目を削除:     # 着目を削除
        lst.remove_current_node()

    elif menu == Menu.全削除:         # 全削除
        lst.clear()

    elif menu == Menu.探索:           # 探索
        pos = lst.search(int(input('値 : ')))
        if pos >= 0:
            print(f'その値は{pos + 1}番目にあります。')
        else:
            print('その値は存在しません。')

    elif menu == Menu.全ノードを表示: # 全ノードを表示
        lst.print()

    else:                             # 終了
        break

(1)先頭に挿入 (2)末尾に挿入 (3)先頭を削除 (4)末尾を削除 (5)着目を表示 (6)着目を進める (7)着目を削除 (8)全削除 (9)探索 (10)全ノードを表示 (11)終了 : 1
値 : 3
(1)先頭に挿入 (2)末尾に挿入 (3)先頭を削除 (4)末尾を削除 (5)着目を表示 (6)着目を進める (7)着目を削除 (8)全削除 (9)探索 (10)全ノードを表示 (11)終了 : 2
値 : 4
(1)先頭に挿入 (2)末尾に挿入 (3)先頭を削除 (4)末尾を削除 (5)着目を表示 (6)着目を進める (7)着目を削除 (8)全削除 (9)探索 (10)全ノードを表示 (11)終了 : 1
値 : 2
(1)先頭に挿入 (2)末尾に挿入 (3)先頭を削除 (4)末尾を削除 (5)着目を表示 (6)着目を進める (7)着目を削除 (8)全削除 (9)探索 (10)全ノードを表示 (11)終了 : 2
値 : 5
(1)先頭に挿入 (2)末尾に挿入 (3)先頭を削除 (4)末尾を削除 (5)着目を表示 (6)着目を進める (7)着目を削除 (8)全削除 (9)探索 (10)全ノードを表示 (11)終了 : 1
値 : 1
(1)先頭に挿入 (2)末尾に挿入 (3)先頭を削除 (4)末尾を削除 (5)着目を表示 (6)着目を進める (7)着目を削除 (8)全削除 (9)探索 (10)全ノードを表示 (11)終了 : 10
1
2
3
4
5
(1)先頭に挿入 (2)末尾に挿入 (3)先頭を削除 (4)末尾を削除 (5)着目を表示 (6)着目を進める (7)着目を削除 (8)全削除 (9)探索 (10)全ノードを表示 (11)終了 : 4
(1)先頭に挿入 (2)末尾に挿入 (3)先頭を削除 (4)末尾を削除 (5)着目を表示 (6)着目を進める (7)着目を削除 (8)全削除 (9)探索 (10)全ノードを表示 (11)終了 : 9
値 : 5
その値は存在しません。
(1)先頭に挿入 (2)末尾に挿入 (3)先頭を削除 (4)末尾を削除 (5)着目を表示 (6)着目を進める (7)着目を削除 (8)全削除 (9)探索 (10)全ノードを表示 (11)終了 : 9
値 : 3
その値は3番目にあります。
(1)先頭に挿入 (2)末尾に挿入 (3)先頭を削除 (4)末尾を削除 (5)着目を表示 (6)着目を進める (7)着目を削除 (8)全削除 (9)探索 (10)全ノードを表示 (11)終了 : 3
(1)先頭に挿入 (2)末尾に挿入 (3)先頭を削除 (4)末尾を削除 (5)着目を表示 (6)着目を進める (7)着目を削除 (8)全削除 (9)探索 (10)全ノードを表示 (11)終了 : 10
2
3
4
(1)先頭に挿入 (2)末尾に挿入 (3)先頭を削除 (4)末尾を削除 (5)着目を表示 (6)着目を進める (7)着目を削除 (8)全削除 (9)探索 (10)全ノードを表示 (11)終了 : 9
値 : 1
その値は存在しません。
(1)先頭に挿入 (2)末尾に挿入 (3)先頭を削除 (4)末尾を削除 (5)着目を表示 (6)着目を進める (7)着目を削除 (8)全削除 (9)探索 (10)全ノードを表示 (11)終了 : 5
2
(1)先頭に挿入 (2)末尾に挿入 (3)先頭を削除 (4)末尾を削除 (5)着目を表示 (6)着目を進める (7)着目を削除 (8)全削除 (9)探索 (10)全ノードを表示 (11)終了 : 6
(1)先頭に挿入 (2)末尾に挿入 (3)先頭を削除 (4)末尾を削除 (5)着目を表示 (6)着目を進める (7)着目を削除 (8)全削除 (9)探索 (10)全ノードを表示 (11)終了 : 7
(1)先頭に挿入 (2)末尾に挿入 (3)先頭を削除 (4)末尾を削除 (5)着目を表示 (6)着目を進める (7)着目を削除 (8)全削除 (9)探索 (10)全ノードを表示 (11)終了 : 10
2
4
(1)先頭に挿入 (2)末尾に挿入 (3)先頭を削除 (4)末尾を削除 (5)着目を表示 (6)着目を進める (7)着目を削除 (8)全削除 (9)探索 (10)全ノードを表示 (11)終了 : 11