리스트란?
데이터 구조의 하나로, 데이터를 일직선으로 나열한 형태를 가지고 있음
데이터 추가나 삭제는 쉽지만, 원하는 데이터에 접근하려면 시간이 많이 걸림. = 삽입과 삭제가 빠름
연결 리스트를 단순한 배열로 구현하면 데이터를 삽입, 삭제할 때마다 데이터를 옮겨야 하므로 비효율적인 문제가 발생한다. 이 문제를 해결하기 위해 아래에서는 포인터를 이용하여 연결 리스트를 구현할 것이다.
위 그림이 리스트의 개념도이다. 여기서는 세 개의 문자열 'Blue', 'Yellow', 'Red'가 데이터로 저장되어 있다.
또한, 각 데이터에는 '포인터(Pointer)'가 있으며, 다음 데이터의 메모리 위치를 가리키고 있다.
'Red'는 마지막 데이터이므로 'Red'의 포인터는 아무것도 가리키지 않는다.
연결리스트에서 사용되는 용어
- 노드(node): 각각의 원소(Blue, Yellow, Red)
- 데이터(data): 노드가 가지고 있는 값
- 포인터(pointer): 뒤쪽 노드를 가리키는 값
- 머리 노드(head node): 맨 앞에 있는 노드
- 꼬리 노드(tail node): 맨 끝에 있는 노드
- 앞쪽 노드(prodecessor node): 각 노드에서 바로 앞에 있는 노드
- 뒤쪽 노드(successor node): 각 노드에서 바로 뒤에 있는 노드
메모리에 데이터가 저장되는 방식
리스트는 데이터가 메모리상의 연속된 위치에 저장되지 않아도 되며, 일반적으로 떨어진 영역에 흩어져서 저장된다.
다시 말하면 흩어져서 저장돼 있으므로 포인터를 처음부터 순서대로 따라가야만 원하는 데이터에 접근할 수 있다.
예를 들어, 위 그림과 같이 'Red'에 접근하자 할 때는 먼저 'Blue'에 접근해야 하고, 그 다음 'Yellow'를 따라가야만 'Red'에 접근할 수 있다.
데이터 추가
데이터 추가는 추가할 위치의 앞 뒤 포인터를 변경하는 방식으로 진행한다.
예를 들어, 'Blue'와 'Yellow' 사이에 'Green'을 추가하고 싶을 때를 생각해보면 다음 그림과 같다.
'Blue'의 포인터를 'Green'을 가리키도록 변경하고, 'Green'의 포인터를 'Yellow'를 다음 그림과 같이 가리키도록 하면 데이터 추가가 완료된다.
데이터 삭제
데이터 삭제도 데이터 추가와 같은 방식으로 진행된다. 포인터의 방향만 바꾸어주면 된다.
예를 들어, 'Yellow'를 삭제하고 싶다면 'Green'의 포인터를 'Yellow'가 아닌 'Red'를 가리키도록 변경하면 삭제가 완료된다.
이 때, 'Yellow'는 메모리에는 남지만 어디에서도 접근할 수 없으므로 일부러 삭제할 필요는 없다. 이후에 이 영역이 사용될 때 덮어쓰기가 되어 다시 사용할 수 있게 된다.
리스트의 시간복잡도
데이터에 접근할 때 리스트의 앞에서부터 차례로 진행(선형 탐색)하기 때문에 접근하고 싶은 데이터가 뒤쪽에 있는 경우에는 O(n)의 계산 시간이 걸린다.
반면, 데이터 추가는 두 개의 포인터만 변경하면 되기 때문에 n에 관계없는 상수 시간 O(1)이 된다. 물론, 추가하고 싶은 위치에 이미 접근해 있는 것을 전제로 할때이다. 또한 삭제도 마찬가지로 O(1)이다.
포인터로 연결 리스트 만들기
# 포인터로 연결 리스트 구현하기
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 # 뒤쪽 포인터
노드 클래스 Node
노드 클래스 Node에는 다음과 같은 필드와 __init__( ) 함수가 있다.
필드
앞에서 살펴보았듯이 노드 클래스 Node는 다음과 같이 필드 2개로 구성된다.
- data: 데이터(데이터에 대한 참조: 임의의 형)
- next: 뒤쪽 포인터(뒤쪽 노드에 대한 참조: Node형)
__init__( ) 함수
__init__( ) 함수는 전달받은 data와 next를 해당 필드에 대입한다. 호출할 때 어떤 인수도 생략할 수 있으며, 생략할 경우에는 None으로 간주한다.
파이썬의 리스트는 자료구조가 아니다
연결 리스트는 임의의 위치에 원소를 삽입하거나 삭제할 때 빠르게 수행할 수 있다는 장점이 있다. 하지만 기억 영역(메모리)과 속도 면에서는 배열보다 효율이 뒤떨어진다.
파이썬의 리스트는 이러한 연결 리스트의 자료구조가 아니라 모든 원소를 연속으로 메모리에 배치하는 '배열'로 내부에서 구현하고 있다. 그로므로 속도가 급격히 떨어지지는 않는다. 또 원소를 하나씩 추가, 삽입할 때마다 내부에서 메모리를 확보하거나 해제하지 않는다. 실제 필요한 메모리보다 여유 있게 미리 마련해 놓기 때문이다.
연결 리스트 클래스
class LinkedList:
"""연결 리스트 클래스"""
def __init__(self) -> None:
"""초기화"""
self.no = 0 # 노드의 개수
self.head = None # 머리 노드
self.current = None # 주목 노드
def __len__(self) -> int:
"""연결 리스트의 노드 개수를 반환"""
return self.no
연결 리스트 클래스 LinkedList
연결 리스트 클래스 LinkedList는 다음과 같이 필드 3개로 구성된다.
- no: 리스트에 등록되어 있는 노드의 개수
- head: 머리 노드에 대한 참조
- current: 현재 주목하고 있는 노드에 대한 참조이며, 주목 포인터라고 부를 수 있음. 리스트에서 노드를 검색하여 그 노드를 주목한 직후에 노드를 삭제하는 등의 용도로 사용
초기화하는 __init__( ) 함수
연결 리스트 클래스 LinkedList의 __init__( ) 함수는 노드가 하나도 없는 빈 연결 리스트를 생성한다.
아래 그림처럼 머리 노드를 참조하기 위한 Node형 필드 head에 None을 대입한다.
head는 머리 노드에 대한 참조일뿐 머리 노드 그 자체가 아님을 주의해야 한다. 노드가 존재하지 않는 빈 연결 리스트는 head가 참조하는 곳이 없으므로(참조해야 하는 노드가 존재하지 않으므로) 그 값을 None으로 한다.
노드 개수를 반환하는 __len__( ) 함수
연결 리스트의 노드 개수를 반환하는 함수이다. no 값을 그대로 반환한다.
이 함수를 구현함으로써 연결 리스트를 len( ) 함수의 인수로 전달받을 수 있다. 즉, len( ) 함수로 연결 리스트의 노드 개수를 알아낼 수 있다.
빈 연결 리스트
위 그림처럼 연결 리스트가 비어 있을(노드가 하나도 존재하지 않을) 때 head값은 None이다. 그러므로 연결 리스트가 비어 있는지는 다음 식으로 검사할 수 있다.
head is None # 연결 리스트가 비어 있는지 확인
노드가 1개인 연결 리스트
아래 그림은 노드가 하나만 존재하는 연결 리스트이다. Node형 필드인 head가 참조하는 곳은 머리 노드 A이다. 이 머리 노드 A는 리스트의 꼬리 노드이기도 하므로 뒤쪽 포인터의 값은 None이다.
head가 참조하는 뒤쪽 포인터의 값이 None이므로 연결 리스트에 존재하는 노드가 하나뿐인지는 다음 식으로 수행할 수 있다.
head.next is None # 연결 리스트의 노드가 1개인지 확인
노드가 2개인 연결 리스트
아래 그림은 노드가 2개 있는 연결 리스트이다. 머리 노드는 노드 A이고, 꼬리 노드는 노드 B이다. 이때 head가 참조하는 곳인 노드 A의 뒤쪽 포인터 next가 노드 B를 참조한다.(곧, head.next가 참조하는 곳은 노드 B이다.) 맨 끝에 위치한 노드 B의 뒤쪽 포인터가 None이므로 연결 리스트의 노드가 2개인지는 다음 식으로 수행할 수 있다.
head.next.next is None # 연결 리스트의 노드가 2개인지 확인뒤쪽 포인터가 아니라 데이터를 나타내는 식을 생각해보았을 때, 노드 A의 데이터에 대한 참조를 나타낸 식은 head.data이고, 노드 B의 데이터에 대한 참조를 나타낸 식은 head.next.data이다.
지금까지 살펴본 3가지 경우의 판단은 no == 0, no == 1, no == 2를 사용할 수 있다.
꼬리 노드의 판단
Node형인 변수 p가 리스트에 있는 노드를 참조한다면, 이때 p가 참조하는 노드가 연결 리스트의 꼬리 노드인지는 다음 식으로 수행할 수 있다.
p.next is None # p가 참조하는 노드가 꼬리 노드인지 확인
검색을 수행하는 search( ) 함수
인수로 주어진 데이터 data와 값이 같은 노드를 검색하는 함수이다. 검색 알고리즘은 선형 검색을 사용한다. 아래 그림과 같이 목적 노드를 만날 때까지 머리 노드부터 순서대로 스캔한다. 아래 그림은 노드 D를 검색하는 모습이고, ①→②→③→④ 순서로 스캔하면 검색에 성공한다.
노드를 스캔할 때 다음 조건 가운데 하나만 성립해도 검색이 종료된다.
- 종료 조건 1: 검색 조건을 만족하는 노드를 발견하지 못하고 꼬리 노드까지 왔을 경우
- 종료 조건 2: 검색 조건을 만족하는 노드를 발견한 경우
아래 코드는 검색하는 과정을 나타낸다.
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
31~32행(cnt와 ptr에 값을 대입하는 부분): 스캔 중인 노드를 참조하기 위한 변수 ptr을 head로 초기화한다. 아래 그림의 a처럼 ptr이 참조하는 곳은 head가 참조하는 머리 노드 A가 된다. 그리고 맨 앞에서 몇 번째 원소를 스캔하고 있는지를 나타낸 카운터용 변수 cnt를 0으로 초기화한다.
33~38행(while문 내부): 앞에서 정리한 종료 조건 1의 판단을 수행한다. ptr값이 None이 아니면, 루프 본문의 34~36행과 37~38행을 실행한다. ptr의 값이 None이면 스캔할 노드가 존재하지 않으므로 while문을 종료하고 39행(return -1 부분)으로 간다.
34~36행(if문 부분): 앞에서 정리한 종료 조건 2의 판단을 수행하며, 검색할 data와 스캔 중인 노드의 데이터 ptr.data와 값이 같은지 판단한다. 값이 같으면 검색 성공이다. 주목 포인터 current에 ptr을 대입하고 찾은 노드의 위치를 나타내는 카운터 cnt를 반환한다. 참고로 cnt는 0부터 시작하는 값이다.(찾은 노드가 맨 앞이면 0이다.)
37~38행(while문 내부의 cnt와 ptr 부분): ptr에 ptr.next를 대입하고 다음 노드로 스캔을 진행한다. 참고로 ptr이 노드 A를 참조하는 아래 그림의 a 상태에서 ptr = ptr.next의 대입을 실행하면 b가 된다. 뒤쪽 노드 B에 대한 참조인 ptr.next가 ptr에 대입된 결과 ptr이 참조하는 곳이 노드 A에서 노드 B로 업데이트 되기 때문이다.
39행(return -1 부분): 프로그램의 흐름이 여기에 도달했다면 검색에 실패한 것이다. 검색 실패임을 나타내는 -1을 반환한다.
데이터가 포함되어 있는지 판단하는 __contains__( ) 함수
리스트에 data와 값이 같은 노드가 포함되어 있는지를 판단하는 함수이다. 포함되어 있으면 True를 반환하고, 그렇지 않으면 False를 반환한다.
이 함수를 구현함으로써 연결 리스트에 in 연산자를 적용할 수 있다.
머리에 노드를 삽입하는 add_first( ) 함수
리스트의 맨 앞에 노드를 삽입하는 함수이다. 아래 그림과 함께 add_first( ) 함수를 이해해보자.
def add_first(self, data: Any) -> None:
"""맨 앞에 노드를 삽입"""
ptr = self.head # 삽입하기 전의 머리 노드
self.head = self.current = Node(data, ptr)
self.no += 1
48행(ptr 부분): 삽입하기 전의 머리 노드 A를 참조하는 포인터를 ptr에 저장해 둔다.
49행(self.head 부분): 삽입할 노드 G를 Node(data, ptr)로 생성한다. 노드 G의 데이터는 data가 되고, 뒤쪽 포인터가 참조하는 곳은 ptr(삽입하기 전의 머리 노드 A)이 된다. 이때 수행하는 대입으로 head는 삽입한 노드를 참조하도록 업데이트 된다.
주목 포인터 current도 삽입한 노드를 참조하도록 업데이트 된다.(꼬리에 노드를 삽입하는 add_last( ) 함수에서도 마찬가지이다.)
아래 그림에서는 노드를 구체적으로 삽입하는 과정을 나타낸다. 그림 a에서 리스트 맨 앞의 머리 노드에 노드 G를 삽입하면 그림 b 상태가 된다.
꼬리에 노드를 삽입하는 add_last( ) 함수
리스트의 맨 끝에 노드를 삽입하는 함수이다. 리스트가 비어 있는지(head is None이 성립하는지) 확인하고 그에 따라 다르게 처리한다.
아래 그림과 함께 add_last( ) 함수를 이해해보자.
- 리스트가 비어 있을 때: 맨 앞에 노드를 삽입하는 것과 같은 처리를 수행하므로 add_first( ) 함수를 호출한다.
- 리스트가 비어 있지 않을 때: 리스트의 맨 끝에 노드 G를 삽입한다.(아래 그림 b에서 구체적인 삽입 과정을 보여준다.)
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
59~60행(while문 내부): 꼬리 노드를 찾는 과정을 수행한다. ptr이 참조하는 곳을 그 뒤쪽 포인터로 업데이트 하는 과정을 반복함으로써 노드를 맨 앞부터 순서대로 스캔한다. while문의 반복이 종료되는 것은 ptr.next가 참조하는 곳이 None으로 되었을 때이다. 이때 ptr이 참조하는 곳은 꼬리 노드 F로 되어 있다.
while문을 종료할 때 ptr은 꼬리 노드를 참조한다.
61행(ptr.next로 시작하는 부분): 삽입하는 노드 G를 Node(data, None)으로 생성한다. 뒤쪽 포인터를 None으로 하는 것은 맨 끝에 위치한 노드 G가 어떤 노드도 참조하지 않도록 하기 위한 것이다. 노드 F의 뒤쪽 포인터 ptr.next가 참조하는 곳이 새로 삽입한 노드 G가 되도록 업데이트 한다.
머리 노드를 삭제하는 remove_first( ) 함수
머리 노드를 삭제하는 함수이다. 삭제 처리를 수행하는 것은 리스트가 비어 있지 않을(head is not None이 성립할)때이다.
def remove_first(self) -> None:
"""머리 노드를 삭제"""
if self.head is not None: # 리스트가 비어 있지 않다면
self.head = self.current = self.head.next
self.no -= 1
아래 그림은 구체적인 삭제 과정이다. a에서 머리 노드 A를 삭제하면 b 상태가 된다.
맨 앞에서 2번째 노드 B에 대한 참조인 head.next를 머리 노드에 대한 참조인 head에 대입함으로써 head가 참조하는 곳을 노드 B로 업데이트 한다. 이때 주목 포인터 current가 참조하는 곳도 노드 B로 업데이트 한다. 그 결과 삭제하기 전의 머리 노드 A는 어디에서도 참조되지 않는다.
리스트에 노드가 하나밖에 없는 경우의 삭제 처리를 생각해보자. 삭제하기 전의 머리 노드는 꼬리 노드이기도 하므로 뒤쪽 포인터 head.next의 값은 None이다. 이 None을 head에 대입하면 리스트는 빈 상태가 된다.
꼬리 노드를 삭제하는 remove_last( ) 함수
꼬리 노드를 삭제하는 함수이다. 삭제 처리를 수행하는 것은 리스트가 비어 있지 않을 때이다. 리스트에 존재하는 노드가 하나뿐인지 확인하고 그에 따라 다음과 같이 다르게 처리한다.
- 리스트에 노드가 하나만 존재할 때: 머리 노드를 삭제하는 것이므로 remove_first( ) 함수를 호출한다.
- 리스트에 노드가 2개 이상 존재할 때: 리스트의 맨 끝에서 노드 F를 삭제한다. 아래 그림의 b에서 구체적인 삭제 과정을 보여준다.
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
78~83행(else~while문 내부): 꼬리 노드와 맨 끝에서 2번째 노드를 찾는다. 따라서 스캔 방법은 앞에서 살펴본 add_last( ) 함수와 거의 같다. 다만 스캔 중인 노드의 앞쪽 노드를 참조하는 변수 pre를 추가한 점이 다르다. 아래 그림의 경우 while문을 종료할 때 pre가 참조하는 곳은 노드 E이고, ptr이 참조하는 곳은 노드 F이다.
즉, while 문을 종료할 때 ptr은 꼬리 노드를 참조하고, pre는 맨 끝에서 2번째 노드를 참조한다.
84~86행(pre.next 이후 부분): 맨 끝에서 2번째 노드 E의 뒤쪽 포인터에 None을 대입한다. 그 결과 노드 F는 어디에서도 참조되지 않는다.
주목 포인터 current가 참조하는 곳은 삭제한 뒤의 꼬리 노드 pre로 업데이트한다.
임의의 노드를 삭제하는 remove( ) 함수
임의의 노드를 삭제하는 함수이다. 삭제 처리를 수행하는 것은 리스트가 비어 있지 않고 인수로 주어진 노드 p(p가 참조하는 노드)가 존재할 때이다.
- p가 머리 노드일 때: 머리 노드를 삭제하는 것이므로 remove_first( ) 함수를 호출한다.
- p가 머리 노드가 아닐 때: 리스트에서 p가 참조하는 노드 D를 삭제한다. 아래 그림에서 구체적인 삭제 과정을 보여준다.
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
95~100행(remove 함수 내 else 문의 while문까지): 삭제할 노드 p의 앞쪽 노드를 찾는 과정을 수행한다. while문은 머리 노드에서 시작하여 스캔 중인 노드 ptr의 뒤쪽 포인터인 ptr.next가 p와 같아질 때까지 반복한다. 다만 None을 만나는 경우에는 p가 참조하는 노드가 존재하지 않는다는 것이다. 삭제 처리를 수행하지 않고 return 문으로 함수를 종료한다.
ptr.next가 p와 같아지면 while 문은 종료한다. 이때 ptr이 참조하는 곳은 삭제할 노드 D의 앞쪽 노드인 C가 된다.
101~103행(remove 함수의 ptr.next 부분): 노드 D의 뒤쪽 포인터 p.next를 노드 C의 뒤쪽 포인터 ptr.next에 대입함으로써 노드 C의 뒤쪽 포인터가 참조하는 곳을 노드 E로 업데이트 한다. 그 결과 노드 D는 어디에서도 참조되지 않는다.
주목 포인터 current가 참조하는 곳은 삭제한 노드의 앞쪽 노드가 되도록 업데이트 한다.
주목 노드를 삭제하는 remove_current_node( ) 함수
현재 주목하고 있는 노드를 삭제하는 함수이다. 주목 포인터 current를 remove( ) 함수에 전달하여 처리를 맡긴다.
주목 포인터 current가 참조하는 곳은 삭제한 노드의 앞쪽 노드로 업데이트 한다.
모든 노드를 삭제하는 clear( ) 함수
모든 노드를 삭제하는 함수이다. 연결 리스트가 비어 있을 때(head가 None이 될 때)까지 머리 노드의 삭제를 반복하여 모든 노드를 삭제한다.
리스트가 비어 있으므로 주목 포인터 current의 값도 None으로 업데이트 한다.
주목 노드를 한 칸 뒤로 이동시키는 next( ) 함수
주목 노드를 한 칸 뒤로 이동시키는 함수이다. 다만 주목 노드를 한 칸 뒤로 이동시키려면 리스트가 비어 있지 않고 주목 노드에 뒤쪽 노드가 존재해야 한다. 구체적으로는 주목 포인터 current를 current.next로 업데이트 한다. 주목 노드를 이동시키면 True를 반환하고, 그렇지 않으면 False를 반환한다.
주목 노드를 출력하는 print_current_node( ) 함수
주목 노드를 출력하는 함수이다. 구체적으로 주목 포인터 current가 참조하는 곳의 노드 데이터인 current.data를 출력한다. 다만 주목 노드가 존재하지 않는 경우(current가 None인 경우)에는 '주목 노드가 존재하지 않습니다.'를 출력한다.
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
모든 노드를 출력하는 print( ) 함수
리스트 순서대로 모든 노드의 데이터를 출력하는 함수이다. ptr을 사용하여 머리 노드에서 꼬리 노드까지 스캔하면서 각 노드의 데이터 ptr.data를 출력한다.
print_current_node( ) 함수와 print( ) 함수는 주목 포인터 current 값을 업데이트 하지 않는다.
다음 표는 각 함수를 실행한 뒤의 current 값을 정리한 것이다.
def __iter__(self) -> LinkedListIterator:
"""이터레이터를 반환"""
return LinkedListIterator(self.head)
class LinkedListIterator:
"""클래스 LinkedList의 이터레이터용 클래스"""
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
이터러블 객체와 이터레이터의 구현
str형 문자열, list형 리스트, tuple형 튜플 등은 이터러블(반복 가능)하다는 공통점이 있다. 이터러블 객체는 원소를 1개씩 꺼내는 구조의 객체이다. 이터러블 객체를 내장 함수인 iter( ) 함수에 인수로 전달하면 그 객체에 대한 이터레이터(반복자)를 반환한다.
이터레이터는 데이터가 줄지어 늘어선 것을 표현하는 객체이다. 이터레이터의 __next__( ) 함수를 호출하거나, 내장 함수인 next( ) 함수에 반복자를 전달하면 줄지어 늘어선 원소를 순차적으로 꺼낸다. 꺼낼 원소가 없으면 StopIteration 예외 처리를 내보낸다.
next( ) 함수의 첫 번째 호출에서는 맨 앞 원소를 꺼내고, 2번째 호출에서는 2번째 원소를 꺼낸다. 이런 식으로 호출할 때마다 다음 원소를 꺼낸다.
클래스 LinkedList는 이터러블이 되도록 이터레이터를 구현한다. 이터레이터를 나타내는 것이 클래스 LinkedListIterator이다. 이터레이터 클래스는 다음과 같이 구현한다
- __next__( ) 함수를 갖는 이터레이터를 반환하는 __iter__( ) 함수를 구현한다.
- __next__( ) 함수는 다음 원소를 꺼내 반환한다. 반환하는 원소가 없으면 StopIteration 예외 처리를 내보낸다.
위 프로그램의 이터레이터는 주목 포인터 current를 업데이트 하지 않는다.
포인터로 연결 리스트 프로그램 만들기
아래 프로그램은 지금까지 설명한 연결 리스트 클래스인 LinkedList를 사용하는 프로그램이다.
# 포인터를 이용한 연결 리스트 클래스 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.멤버십판단: # 멤버십을 판단
print('그 값의 데이터는 포함되어'
+(' 있습니다.' if int(input('판단할 값을 입력하세요.: ')) in lst else ''
'있지 않습니다.'))
elif menu == Menu.모든노드출력: # 모든 노드를 출력
lst.print()
elif menu == Menu.스캔: # 모든 노드를 스캔
for e in lst:
print(e)
else: # 종료
break
실행 결과
(1)머리에노드삽입 (2)꼬리에노드삽입 (3)머리노드삭제 (4)꼬리노드삭제 (5)주목노드출력 (6)주목노드이동 (7)주목노드삭제 (8)모든노드삭제 (9)검색 (10)멤버십판단 (11)모든노드출력 (12)스캔 (13)종료: 1
머리 노드에 넣을 값을 입력하세요.: 1
(1)머리에노드삽입 (2)꼬리에노드삽입 (3)머리노드삭제 (4)꼬리노드삭제 (5)주목노드출력 (6)주목노드이동 (7)주목노드삭제 (8)모든노드삭제 (9)검색 (10)멤버십판단 (11)모든노드출력 (12)스캔 (13)종료: 2
꼬리 노드에 넣을 값을 입력하세요.: 5
(1)머리에노드삽입 (2)꼬리에노드삽입 (3)머리노드삭제 (4)꼬리노드삭제 (5)주목노드출력 (6)주목노드이동 (7)주목노드삭제 (8)모든노드삭제 (9)검색 (10)멤버십판단 (11)모든노드출력 (12)스캔 (13)종료: 1
머리 노드에 넣을 값을 입력하세요.: 10
(1)머리에노드삽입 (2)꼬리에노드삽입 (3)머리노드삭제 (4)꼬리노드삭제 (5)주목노드출력 (6)주목노드이동 (7)주목노드삭제 (8)모든노드삭제 (9)검색 (10)멤버십판단 (11)모든노드출력 (12)스캔 (13)종료: 2
꼬리 노드에 넣을 값을 입력하세요.: 12
(1)머리에노드삽입 (2)꼬리에노드삽입 (3)머리노드삭제 (4)꼬리노드삭제 (5)주목노드출력 (6)주목노드이동 (7)주목노드삭제 (8)모든노드삭제 (9)검색 (10)멤버십판단 (11)모든노드출력 (12)스캔 (13)종료: 1
머리 노드에 넣을 값을 입력하세요.: 14
(1)머리에노드삽입 (2)꼬리에노드삽입 (3)머리노드삭제 (4)꼬리노드삭제 (5)주목노드출력 (6)주목노드이동 (7)주목노드삭제 (8)모든노드삭제 (9)검색 (10)멤버십판단 (11)모든노드출력 (12)스캔 (13)종료: 4
(1)머리에노드삽입 (2)꼬리에노드삽입 (3)머리노드삭제 (4)꼬리노드삭제 (5)주목노드출력 (6)주목노드이동 (7)주목노드삭제 (8)모든노드삭제 (9)검색 (10)멤버십판단 (11)모든노드출력 (12)스캔 (13)종료: 9
검색할 값을 입력하세요.: 12
해당하는 데이터가 없습니다.
(1)머리에노드삽입 (2)꼬리에노드삽입 (3)머리노드삭제 (4)꼬리노드삭제 (5)주목노드출력 (6)주목노드이동 (7)주목노드삭제 (8)모든노드삭제 (9)검색 (10)멤버십판단 (11)모든노드출력 (12)스캔 (13)종료: 9
검색할 값을 입력하세요.: 10
그 값의 데이터는 2번째에 있습니다.
(1)머리에노드삽입 (2)꼬리에노드삽입 (3)머리노드삭제 (4)꼬리노드삭제 (5)주목노드출력 (6)주목노드이동 (7)주목노드삭제 (8)모든노드삭제 (9)검색 (10)멤버십판단 (11)모든노드출력 (12)스캔 (13)종료: 5
10
(1)머리에노드삽입 (2)꼬리에노드삽입 (3)머리노드삭제 (4)꼬리노드삭제 (5)주목노드출력 (6)주목노드이동 (7)주목노드삭제 (8)모든노드삭제 (9)검색 (10)멤버십판단 (11)모든노드출력 (12)스캔 (13)종료: 11
14
10
1
5
(1)머리에노드삽입 (2)꼬리에노드삽입 (3)머리노드삭제 (4)꼬리노드삭제 (5)주목노드출력 (6)주목노드이동 (7)주목노드삭제 (8)모든노드삭제 (9)검색 (10)멤버십판단 (11)모든노드출력 (12)스캔 (13)종료: 9
검색할 값을 입력하세요.: 1
그 값의 데이터는 3번째에 있습니다.
(1)머리에노드삽입 (2)꼬리에노드삽입 (3)머리노드삭제 (4)꼬리노드삭제 (5)주목노드출력 (6)주목노드이동 (7)주목노드삭제 (8)모든노드삭제 (9)검색 (10)멤버십판단 (11)모든노드출력 (12)스캔 (13)종료: 7
(1)머리에노드삽입 (2)꼬리에노드삽입 (3)머리노드삭제 (4)꼬리노드삭제 (5)주목노드출력 (6)주목노드이동 (7)주목노드삭제 (8)모든노드삭제 (9)검색 (10)멤버십판단 (11)모든노드출력 (12)스캔 (13)종료: 3
(1)머리에노드삽입 (2)꼬리에노드삽입 (3)머리노드삭제 (4)꼬리노드삭제 (5)주목노드출력 (6)주목노드이동 (7)주목노드삭제 (8)모든노드삭제 (9)검색 (10)멤버십판단 (11)모든노드출력 (12)스캔 (13)종료: 11
10
5
(1)머리에노드삽입 (2)꼬리에노드삽입 (3)머리노드삭제 (4)꼬리노드삭제 (5)주목노드출력 (6)주목노드이동 (7)주목노드삭제 (8)모든노드삭제 (9)검색 (10)멤버십판단 (11)모든노드출력 (12)스캔 (13)종료: 9
검색할 값을 입력하세요.: 10
그 값의 데이터는 1번째에 있습니다.
(1)머리에노드삽입 (2)꼬리에노드삽입 (3)머리노드삭제 (4)꼬리노드삭제 (5)주목노드출력 (6)주목노드이동 (7)주목노드삭제 (8)모든노드삭제 (9)검색 (10)멤버십판단 (11)모든노드출력 (12)스캔 (13)종료: 6
(1)머리에노드삽입 (2)꼬리에노드삽입 (3)머리노드삭제 (4)꼬리노드삭제 (5)주목노드출력 (6)주목노드이동 (7)주목노드삭제 (8)모든노드삭제 (9)검색 (10)멤버십판단 (11)모든노드출력 (12)스캔 (13)종료: 5
5
(1)머리에노드삽입 (2)꼬리에노드삽입 (3)머리노드삭제 (4)꼬리노드삭제 (5)주목노드출력 (6)주목노드이동 (7)주목노드삭제 (8)모든노드삭제 (9)검색 (10)멤버십판단 (11)모든노드출력 (12)스캔 (13)종료: 10
판단할 값을 입력하세요.: 7
그 값의 데이터는 포함되어있지 않습니다.
(1)머리에노드삽입 (2)꼬리에노드삽입 (3)머리노드삭제 (4)꼬리노드삭제 (5)주목노드출력 (6)주목노드이동 (7)주목노드삭제 (8)모든노드삭제 (9)검색 (10)멤버십판단 (11)모든노드출력 (12)스캔 (13)종료: 12
10
5
(1)머리에노드삽입 (2)꼬리에노드삽입 (3)머리노드삭제 (4)꼬리노드삭제 (5)주목노드출력 (6)주목노드이동 (7)주목노드삭제 (8)모든노드삭제 (9)검색 (10)멤버십판단 (11)모든노드출력 (12)스캔 (13)종료: 13
Process finished with exit code 0'자료구조, 알고리즘 입문' 카테고리의 다른 글
| 기본 자료구조와 배열 (0) | 2024.06.10 |
|---|---|
| [알고리즘] 재귀 알고리즘을 활용한 8퀸 문제 풀이 (0) | 2022.05.18 |