class Node:
"""
Linked List を構成する要素 ( ノード )。
"""
def __init__(self, name: str, age: int):
"""
:attribute next_node: 自分の次に位置するノード ( Node 型 )。自分が最後の場合は None 。
"""
self.name = name
self.age = age
self.next_node = None

def __repr__(self):
return f"{self.name}({self.age})"


class LinkedList:
"""
Linked List 実装クラス
"""
def __init__(self, first_node: Node = None):
"""
:param first_node: Linked List の最初のノード ( Node 型 )。
"""
self._first_node = first_node

def __repr__(self):
nodes = []
node = self._first_node
while node is not None:
nodes.append(repr(node))
node = node.next_node

nodes.append('None')
return ' -> '.join(nodes)

def __len__(self):
"""
:return: int型
"""
ct = 0
if (cur := self._first_node) is not None:
while cur is not None:
cur = cur.next_node
ct += 1
return ct

def prepend(self, other: Node):
"""
リストの先頭にノードを追加する。

:param other: 追加するノード
"""
if self._first_node is not None:
other.next_node = self._first_node
self._first_node = other

def append(self, other: Node):
"""
リストの最後にノードを追加する。

:param other: 追加するノード
"""
if self._first_node is None:
self._first_node = other
else:
cur = self._first_node
while cur.next_node is not None:
cur = cur.next_node
cur.next_node = other

def append_after(self, arg_name: str, other: Node):
"""
name 属性値として arg_name を持つノードの後に other を追加する。
arg_name を持つノードが存在しない場合はメッセージを表示し終了する（追加しない）。
同じ属性値を持つノードがリストに複数含まれている場合は、先頭から検索し最初にマッチしたノードの次に追加する。

:param arg_name: この値の name 属性を持つノードの後に追加する
:param other: 追加するノード
"""
cur = self.find_node(arg_name)
if cur is None:
print(f"リスト内に名前は存在しません: {arg_name}")
return

cur.next_node, other.next_node = other, cur.next_node

def find_node(self, arg_name: str):
"""
name 属性値として arg_name を持つノードを検索する。
同じ属性値を持つノードがリストに複数含まれている場合は、先頭から検索し最初にマッチしたノードを返す。

:param arg_name: この値の name 属性を持つノードを検索する
:return: 該当するノード、もしくは、None (見つからなかった場合)
"""
node = self._first_node
while node is not None and node.name != arg_name:
node = node.next_node

return node

def remove(self, arg_name: str):
"""
name 属性値として arg_name を持つノードを削除する。
同じ属性値を持つノードがリストに複数含まれている場合は、先頭から検索し最初にマッチしたノードを削除する。

:param arg_name: この値の name 属性を持つノードを削除する
"""
if self._first_node is None:
print("リストは空です")
return

cur = self._first_node
prev = None

while cur and cur.name != arg_name:
prev = cur
cur = cur.next_node

if prev is None:
# ノードの先頭、かつ、名前がマッチ
self._first_node = cur.next_node
elif cur:
# ２番目以降のノード、かつ、名前がマッチ
prev.next_node = cur.next_node
cur.next_node = None
else:
print(f"リスト内に名前は存在しません ({arg_name})。0 個のノードが削除されました。")

def reverse(self):
"""
Linked list の並び順を逆にする。
"""
if self._first_node is None:
print("リストは空です")
return

cur = self._first_node
prev = None
while cur:
following = cur.next_node
cur.next_node = prev
prev = cur
cur = following
self._first_node = prev

def reverse_recursive(self):
"""
reverse 関数の再帰バージョン
"""
def recursion(cur, prev):
if not cur:
return prev

following = cur.next_node
cur.next_node = prev

prev = cur
cur = following

return recursion(cur, prev)

self._first_node = recursion(cur=self._first_node, prev=None)


linked_list = LinkedList()


print(linked_list)
# None


print(linked_list.find_node('one'))
# None


linked_list.remove('nothing')
# リストは空です


linked_list.append(Node('two', 2))
linked_list.append(Node('three', 3))


print(linked_list)
# two(2) -> three(3) -> None


linked_list.prepend(Node('one', 1))


print(linked_list)
# one(1) -> two(2) -> three(3) -> None


linked_list.append(Node('four', 4))
linked_list.append(Node('five', 5))
linked_list.append(Node('seven', 7))


print(linked_list)
# one(1) -> two(2) -> three(3) -> four(4) -> five(5) -> seven(7) -> None


linked_list.append_after('five', Node('six', 6))


print(linked_list)
# one(1) -> two(2) -> three(3) -> four(4) -> five(5) -> six(6) -> seven(7) -> None


linked_list.reverse()


print(linked_list)
# seven(7) -> six(6) -> five(5) -> four(4) -> three(3) -> two(2) -> one(1) -> None


linked_list.reverse_recursive()


print(linked_list)
# one(1) -> two(2) -> three(3) -> four(4) -> five(5) -> six(6) -> seven(7) -> None


linked_list.remove('nothing')
# リスト内に名前は存在しません (nothing)。0 個のノードが削除されました。


linked_list.remove('one')


print(linked_list)
# two(2) -> three(3) -> four(4) -> five(5) -> six(6) -> seven(7) -> None


linked_list.remove('four')


print(linked_list)
# two(2) -> three(3) -> five(5) -> six(6) -> seven(7) -> None


linked_list.remove('seven')


print(linked_list)
# two(2) -> three(3) -> five(5) -> six(6) -> None


print(len(linked_list))
# 4


print(linked_list.find_node('three'))
# three(3)


print(linked_list.find_node('ten'))
# None