포인터로 연결 리스트 만들기
# 포인터로 연결 리스트 구현하기
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:
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 __contains__(self, data:Any) -> bool:
return self.search(data) >= 0
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:
self.remove_first()
else:
ptr = self.head
pre = self.head
while ptr.next is not None:
pre = ptr
ptr = ptr.next
pre.next = None
self.current = pre
self.no -= 1
def remove(self, p:Node) -> None:
if self.head is not None:
if p is self.head:
self.remove_first()
else:
ptr = self.head
while ptr.next is not p:
ptr = ptr.next
if ptr is None:
return
ptr.next = p.next
self.current = ptr
self.no -= 1
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
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 __iter__(self) -> LinkedListIterator:
return LinkedListIterator(self.head)
class LinkedListIterator:
def __init__(self, head:Node):
self.current = head
def __iter__(self) -> LinkedListIterator:
return self
def __next__(self) -> Any:
if self.current is None:
raise StopIteration
else:
data = self.current.data
self.current = self.current.next
return data
프로그램
from enum import Enum
from for_class 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()
'Computer Science > 자료구조' 카테고리의 다른 글
[6.3] 09-2 이진 트리와 이진 검색 트리 (0) | 2021.06.03 |
---|---|
[6.2] 09-1 트리구조 (0) | 2021.06.02 |
[5.30] 08-2 포인터를 이용한 연결 리스트 (0) | 2021.05.30 |
[5.30] 08-1 연결 리스트 (0) | 2021.05.30 |
[5.29] 07-3 보이어, 무어법 Boyer-Moor method (0) | 2021.05.29 |