4. 리스트(List)
4-2. LinkedList
4-2-3. 탐색
.get(i)
주어진 인덱스 i의 항목을 반환.
조건이 참이면 i에 해당하는 노드 값 또는 데이터를 반환하고
i가 유효한 범위 내에 있지 않을 때 '범위 밖입니다'라는 메시지를 출력함.
get(i): # .get(i) : i번째 원소를 가져오는 것을 의미.
if i >= 0 and i < num_items:
return get_node(i).item
else:
print('범위 밖입니다.')
.get_node(i)
주어진 인덱스 i에 해당하는 노드를 찾아서 반환.
반복문을 통해 연결 리스트의 노드를 탐색하고, i+1번째 노드를 반환.
get_node(i):
curr = head
for index in range(i+1):
curr = curr.next # 현재 노드(i)의 다음 노드(i+1)을 가리킴.
return curr
.index(x)
주어진 값 x의 인덱스를 찾아서 반환. 반복문을 통해 연결 리스트의 노드를 탐색하고, 값을 비교하여 인덱스를 찾음.
값이 일치하는 경우 해당 인덱스를 반환하고, 값이 존재하지 않는 경우 None을 반환.
index(x):
curr = head # 더미노드
for index in range(num_items):
curr = curr.next
if curr.item = x:
return index
return None
4-2-4. 기타
.is_empty()
연결 리스트가 비어있는지를 확인하는 함수.
num_items 변수가 0이면 True를 반환하고, 그렇지 않으면 False를 반환.
is_empty():
return num_items == 0
.size()
연결 리스트의 크기 또는 항목 수를 반환하는 함수.
num_items 변수를 반환하여 연결 리스트의 크기를 알 수 있음.
size():
return num_items
.clear()
새로운 노드를 생성하고 연결 리스트의 헤드를 설정하며,
연결 리스트의 항목 수를 0으로 초기화하는 작업을 수행.
new_node.next = None
head = new_node
num_items = 0
4-3. 구현
class ListNode:
def __init__(self, new_item, next_node):
self.item = new_item
self.next = next_node
class LinkedListBasic:
def __init__(self):
self.head = ListNode('dummyhead', None)
self.num_items = 0
# 추가 : 특정 위치 삽입
def insert(self, i: int, new_item):
if i >= 0 and i <= self.num_items:
prev = self.get_node(i - 1)
new_node = ListNode(new_item, prev.next)
prev.next = new_node
self.num_items += 1
else:
print(f'{i}는 범위 안의 수가 아닙니다.')
# 특정 노드 위치 찾기 : 인덱스가 없어서 직접 찾아야함
def get_node(self, i: int) -> ListNode:
curr = self.head
for index in range(i+1):
curr = curr.next
return curr
# 추가 : 가장 마지막에 삽입
def append(self, new_item):
prev = self.get_node(self.num_items - 1)
new_node = ListNode(new_item, None)
prev.next = new_node
self.num_items += 1
# 삭제 : i번째
def pop(self, i: int):
if i >= 0 and i < self.num_items:
prev = self.get_node(i - 1)
# prev.next = prev.next.next
curr = prev.next
prev.next = curr.next
self.num_items -= 1
return curr.item
else:
return None
def popi(self, i: int = -1):
if i >= 0 and i < self.num_items:
prev = self.get_node(i - 1)
curr = prev.next
prev.next = curr.next
self.num_items -= 1
return curr.item
elif i < 0:
true_index = self.num_items + i
prev = self.get_node(true_index - 1)
curr = prev.next
prev.next = curr.next
self.num_items -= 1
return curr.item
else:
return None
# 삭제 : 특정 인수
def remove(self, x):
(prev, curr) = self.find_node(x)
if curr != None:
prev.next = curr.next
self.num_items -= 1
def find_node(self, x):
prev = self.head # 더미헤드부터 시작
curr = prev.next # 0번 노드
while curr != None:
if curr.item == x:
return (prev, curr)
else:
prev = curr
curr = curr.next
return (None, None)
# 탐색 : i번째 데이터
def get(self, i: int):
if self.is_empty():
return None
if i >= 0 and i < self.num_items:
return self.get_node(i).item
else:
return None
# 탐색 : x가 몇 번째 원소인지 알려주는 것
def index(self, x) -> int:
curr = self.head.next # 0번 노드
for index in range(self.num_items):
if curr.item == x:
return index
else:
curr = curr.next
return -999
# 기타
def is_empty(self) -> bool:
return self.num_items == 0
def size(self) -> int:
return self.num_items
def clear(self):
self.head = ListNode('header', None)
self.num_items = 0
# 추가
# 같은 원소의 개수 세기
def count(self, x) -> int:
cnt = 0
curr = self.head.next # 0번 노드
while curr != None:
if curr.item == x:
cnt += 1
curr = curr.next
return cnt
# 같은 리스트 연결하기
def extend(self, a: LinkedListBasic):
# for index in a:
for index in range(a.size()):
self.append(a.get(index))
# 동일한 리스트로 복사하기
def copy(self):
a = LinkedListBasic()
for index in range(self.num_items):
a.append(self.get(index))
return a
