지난 포스트에서는 데크에 대해서 다루었다. 데크의 직접 구현 부분에서는 연결 리스트를 사용하여 구현했다. 그래서 실은 순서가 뒤집히지 않았나 싶지만.. collections 라이브러를 통해서도 데크를 사용할 수 있기에 이번 포스트를 읽고 지난 포스트를 다시 보기를 권장한다.
각설하고, 이번 포스트에서는 연결 리스트에 대해서 다루겠다. 연결리스트의 키워드를 세 가지 뽑으라면 필자는 이렇게 말할 것이다.
노드, 삽입, 수정
리스트나 스택, 큐에서는 보관하고 있는 데이터가 raw data (원시 데이터 - 이를테면, 정수형) 였다. 하지만, 연결 리스트에 사용되는 데이터의 (클래스) 타입은 Node 이다. 왜 굳이 클래스를 사용하는가? 그것은 단순히 원시 데이터 이외에도 다음 노드를 가르킬 포인터(next)가 필요하기 때문이다.
class Node:
def __init__(self, data):
self.data = data
self.next: Node = None
node1 = Node(10)
node2 = Node(20)
node1.next = node2
그러나 우리는 노드가 점점 많아질수록 이들을 일일이 관리할 것인가? 그래서 우리는 노드들의 집합인 연결 리스트 라는 매개체를 통해 노드들을 효율적으로 관리 해야 한다.
그렇다면, 노드를 관리하는 과정(삽입, 삭제)을 그림으로 살펴보자.
[노드의 삽입]
class Node:
def __init__(self, data):
self.data = data
self.next: Node = None
node1 = Node(10)
node2 = Node(20)
node1.next = node2
node3 = Node(30) # 과정 1
node1.next = node3 # 과정 2
node3.next = node2 # 과정 3
[노드의 삭제]
class Node:
def __init__(self, data):
self.data = data
self.next: Node = None
node1 = Node(10)
node2 = Node(20)
node1.next = node2
node3 = Node(30)
node1.next = node3
node3.next = node2
node1.next = node2 # 과정 1 (과정 2는 gc에 의해 자동으로 수행)
여기서 과정 2에 대해 좀더 부연설명을 하자면, node1이 node2를 가르키게 되면서 node3를 가르키는 포인터가 더이상 존재하지 않는다. 그 과정에서 GC (Garbage Collector)에 의해 자동으로 메모리에서 해제된다. 이에 관련된 내용은 싱글톤 패턴 포스팅에서 instance() 메소드의 주석에 예시를 남겨두었다.
마지막으로 연결리스트를 어떻게 구현했는지 전체 코드를 보면서 포스팅을 마치겠다.
"""
* select_node()
- 해당 인덱스의 노드를 선택한다.
* insert()
- 특정 위치에 노드를 삽입한다.
* delete()
- 특정 위치의 노드를 삭제한다.
* is_empty()
- 연결리스트가 비었는지 확인한다.
* append()
- 맨 마지막에 새로운 노드를 추가한다.
* appendleft()
- 맨 앞에 새로운 노드를 추가한다.
* pop()
- 맨 마지막의 노드를 삭제한다.
* popleft()
- 맨 앞의 노드를 삭제한다.
* peek_all()
- 모든 노드를 반환한다.
"""
from typing import List
class Node:
def __init__(self, data):
self.data = data
self.next: Node = None
class SingleLinkedList:
def __init__(self, values: List):
# 맨 앞의 노드와 맨 마지막 노드, 노드들의 갯수 (연결리스트 길이)
self.head: Node = None
self.tail: Node = None
self._len = 0
# 연결리스트 초기화
self.__init_linked_list(values)
def __len__(self):
return self._len
def __init_linked_list(self, values):
"""
연결리스트 초기 생성
:param values: 값들의 리스
:return:
"""
# 값이 존재하지 않으면 아무것도 하지 않는다.
if not len(values):
return
# 앞 앞의 노드를 생성
self.head = curr_node = Node(values[0])
self._len = 1
# 두 번째 노드부터 순회하면서 연결
for value in values[1:]:
new_node = Node(value)
curr_node.next = new_node
curr_node = new_node
self._len += 1
# 마지막 노드를 설정
self.tail = curr_node
def select_node(self, idx):
"""
특정 위치의 노드를 반환
:param idx:
:return:
"""
# 연결리스트가 비었거나 요청한 인덱스가 연결리스트의 범위를 초과하면 아무것도 하지 않음.
if self.is_empty() or idx > self._len-1:
return
# 첫 번째 인덱스를 요청한 경우
if idx == 0:
return self.head
# 마지막 인덱스를 요청한 경우
elif idx == self._len-1:
return self.tail
# 중간의 인덱스를 요청한 경우
else:
# 맨 앞의 노드부터 순차 탐색
curr_idx, curr_node = 0, self.head
while curr_idx < idx:
curr_node = curr_node.next
curr_idx += 1
return curr_node
def insert(self, idx, value):
"""
특정 위치에 노드를 삽입
:param idx:
:param value:
:return:
"""
# 삽입을 요청한 위치가 연결리스트의 길이를 초과한 경우 아무것도 하지 않음.
if idx > self._len-1:
return
# 맨 앞에 삽입을 요청한 경우
if idx == 0:
self.append_left(value)
# 맨 뒤에 삽입을 요청한 경우
elif idx == self._len-1:
self.append(value)
# 중간에 삽입을 요청한 경우
else:
# 기준 노드(prev_node)와 그 다음 노드(next_node) 사이에 새로운 노드를 삽입
prev_node = self.select_node(idx)
next_node = prev_node.next
new_node = Node(value)
prev_node.next = new_node
new_node.next = next_node
self._len += 1
def delete(self, idx):
"""
특정 위치의 노드를 제거
:param idx:
:return:
"""
# 삭제를 요청한 위치가 연결리스트의 길이를 초과한 경우 아무것도 하지 않음.
if idx > self._len-1:
return
# 맨 앞에 삭제를 요청한 경우
if idx == 0:
self.pop_left()
# 맨 뒤에 삭제를 요청한 경우
elif idx == self._len-1:
self.pop()
# 중간에 삭제를 요청한 경우
else:
# 기준 노드(del_node)의 앞 노드(prev_node)와 뒷 노드(next_node)를 연결하고
# 기준 노드(del_node)는 제거
prev_node = self.select_node(idx-1)
del_node = prev_node.next
next_node = del_node.next
prev_node.next = next_node
del del_node
self._len -= 1
def is_empty(self):
"""
연결리스트가 비어있는지 검사
:return:
"""
return True if self._len == 0 else False
def append(self, value):
"""
맨 앞에 새로운 노드를 생성
:param value:
:return:
"""
new_node = Node(value)
self.tail.next = new_node
self.tail = new_node
self._len += 1
def append_left(self, value):
"""
맨 뒤에 새로운 노드를 생성
:param value:
:return:
"""
new_node = Node(value)
new_node.next = self.head
self.head = new_node
self._len += 1
def pop(self):
"""
맨 뒤의 노드를 제거
:return:
"""
new_node = self.select_node(self._len-2)
new_node.next = None
del self.tail
self.tail = new_node
self._len -= 1
def pop_left(self):
"""
맨 앞의 노드를 제거
:return:
"""
new_node = self.head.next
del self.head
self.head = new_node
self._len -= 1
def peek_all(self):
"""
맨 앞 노드부터 순차적으로 모든 노드들을 반환
:return:
"""
curr_node = self.head
nodes = list()
while curr_node is not None:
nodes.append(curr_node.data)
curr_node = curr_node.next
return nodes
def print(self):
"""
현재 연결리스트의 상태를 출력
:return:
"""
nodes = self.peek_all()
print(' -> '.join(map(str, nodes)), ' len : ', self._len)
sll = SingleLinkedList([3, 4, 5, 6, 10])
sll.print() # 3 -> 4 -> 5 -> 6 -> 10 len : 5
sll.insert(3, 100)
sll.print() # 3 -> 4 -> 5 -> 6 -> 100 -> 10 len : 6
sll.append(200)
sll.print() # 3 -> 4 -> 5 -> 6 -> 100 -> 10 -> 200 len : 7
sll.append_left(300)
sll.print() # 300 -> 3 -> 4 -> 5 -> 6 -> 100 -> 10 -> 200 len : 8
sll.pop()
sll.print() # 300 -> 3 -> 4 -> 5 -> 6 -> 100 -> 10 len : 7
sll.pop_left()
sll.print() # 3 -> 4 -> 5 -> 6 -> 100 -> 10 len : 6
sll.delete(2)
sll.print() # 3 -> 4 -> 6 -> 100 -> 10 len : 5'[CS] - Data Structure' 카테고리의 다른 글
| # 2. 데크 (Deque) (0) | 2021.12.02 |
|---|---|
| # 1. 스택과 큐 (Stack and Queue) (0) | 2021.12.02 |
| # 0. 자료구조 카테고리의 시작.. (0) | 2021.12.02 |
댓글