이번에 코딩 테스트를 하면서 지금 내게 부족하다고 판단된건 자료구조의 대한 무지라고 생각된다. 어떤 문제를 보면 어떤 자료구조를 이용할지 떠오르지만 막상 적용하는데 어려움이 있다보니 결국 for문 부터 적게된다. 이번에 파이썬을 활용해서 연결리스트, 스택, 큐, 트리, 그래프와 같은 기본적인 자료구조를 구현해 볼 생각이다. 이번건 절대로 작심삼일로 끝나지 않을 것이다!
연결 리스트
연속된 물리적 위치가 아니라 하이퍼 문서처럼 링크를 이용해 다음 순서의 자료를 구현하는 방식을 연결 자료구조라고 합니다.
우리가 배열이라고 하는 기본적인 자료구조(선형 리스트)는 메모리를 연속적으로 할당받는다. 따라서 중간에 값을 삭제하는 경우 값들의 자리교체가 필요해지므로 많은 오버헤드가 발생한다. 연결리스트는 분산된 메모리속에서 링크를 통해 다음 값을 알아내므로 중간 값이 삭제되는 경우 링크만 바꿔주면 된다는 장점이 있다. 물론 파이썬에선 배열이 연결 리스트로 구현되어 예외다.
- 단순 연결 리스트
- 원형 연결 리스트
- 이중 연결 리스트
연결 리스트는 위 3가지 형태로 작성된다. 연결 리스트를 알기전에 노드라는 것에 대해서 언급해야 하는데, 노드는 값 + 링크의 형태를 갖추고 있는 구조를 말한다. 링크는 포인터로 구현되어 다른 노드를 참조하는 값이다.
단순 연결 리스트 : 단순 연결 리스트는 헤더 노드가 존재하며 헤더 노드는 다음 노드를 그리고 다음 노드는 그 다음 노드를 가리킨다. 한 방향으로 연결되어 단순 연결 리스트라고 부른다.
원형 연결 리스트 : 원형 연결 리스트는 헤더 노드와 테일 노드가 존재하며 단순 연결 리스트와 구조상 동일하지만 테일 노드가 헤더 노드를 가리키고 있다는 것이 차이점이다.
이중 연결 리스트 : 이중 연결 리스트는 헤더 노드만 존재하며 각 노드는 다음 노드를 가리키는 링크를 가지는 동시에 이전 노드를 가리키는 링크를 가지고 있다.
파이썬에서 포인터...?
필자가 어려움을 겪었던 건 링크에 대한 구현이었다. C에서는 포인터를 사용해서 다음 리스트를 가리키면 되지만 파이썬에선 어찌 가리킬 수 있을지 엄두가 나지 않았다. 하지만 이내 파이썬은 정말 혁신적인 언어라는 것을 알 수 있었다. 구현하는 내내 재밌었다. 이 기세라면 그래프까지 가능할지도
class Node:
def __init__(self, data):
self.data = data
self.next = None파이썬에서 노드는 위와같이 구현하였다. 위 구조에서 현재 노드에서 다음 노드를 어떻게 참조 시킬 수 있을까?
head = Node(5)
next_node = Node(12)
head.next = next_node위와같이 구현하여 참조시킬 수 있다. 자료형이 없는게 불편하다고 생각했는데 정말 좋은 언어였다 :) 이제 위와같이 노드를 생성하고 관리하는 클래스를 구현하여 사용할 것이다.
단순 연결 리스트
단순 연결 리스트에서 구현될 항목은 아래와 같다.
- 첫 번째 노드 삽입
- 중간 노드 삽입
- 마지막 노드 삽입
- 노드 삭제
노드 탐색
우선 각 항목을 구현하기전에 단순 연결 리스트의 클래스를 생성하였다.
class SingleLinkedList:
def __init__(self, data):
new_node = Node(data)
self.head = new_node
self.list_size = 1단순 연결 리스트의 경우 head가 필요하므로 생성자에서 만들어 주었고 사이즈를 호출하는 메서드는 구현은 간단하지만 길이를 계산하는 것 보다 O(n), 길이를 가지고 있는 편이 좋을 것 같아서 O(1) 추가하였다.
아래부터 구현될 모든 메서드는 클래스 내부에서 구현되었다.
첫 번째 노드 삽입
def insertFirst(self, data):
new_node = Node(data) # 새로운 노드 생성
temp_node = self.head # 기존 헤드를 잠시 보관
self.head = new_node # 헤드를 새로운 노드로 변경
self.head.next = temp_node # 새로 생성된 헤드의 링크를
# 기존 헤드의 링크로 변경
self.list_size += 1헤더가 교체되는 작업이다.
노드 선택
다른 메서드의 작업을 좀 더 편리하게 하기 위해서 익덱스 번호로 노드를 선택할 수 있게 하였다.
def selectNode(self, num):
if self.list_size < num:
return # 오버플로우
node = self.head
count = 0
while count < num:
node = node.next
count += 1
return node위와같이 파이썬에선 node = node.next처럼 간단하게 노드를 전환하고 연결된 링크로 이동할 수 있다.
중간 노드 삽입
def insertMiddle(self, num, data):
if self.head.next == None:
# 헤더가 만들어진 직후에 메서드를 사용하는 경우
insertLast(data)
return
node = self.selectNode(num)
new_node = Node(data)
temp_next = node.next
node.next = new_node
new_node.next = temp_next
self.list_size += 1마지막 노드 삽입
def insertLast(self, data):
node = self.head
while True:
if node.next == None: # 다음 링크가 없으면
break
node = node.next
new_node = Node(data)
node.next = new_node # 마지막 노드로 링크
self.list_size += 1노드 삭제
def deleteNode(self, num):
if self.list_size < 1:
return # 언더플로우
elif self.list_size < num:
return # 오버플로우
if num == 0:
self.deleteHead()
return
node = self.selectNode(num - 1) # 이전 노드의 링크를 다다음 노드와 연결하기 위해
# 이전 노드를 선택하였다
node.next = node.next.next
del_node = node.next
del del_node헤드 노드 삭제
def deleteHead(self):
node = self.head
self.head = node.next
del node단순 연결 리스트의 전체 소스코드
class Node:
def __init__(self, data):
self.data = data
self.next = None
def __str__(self):
return str(self.data)
class SingleLinkedList:
def __init__(self, data):
new_node = Node(data)
self.head = new_node
self.list_size = 1
def __str__(self):
print_list = '[ '
node = self.head
while True:
print_list += str(node)
if node.next == None:
break
node = node.next
print_list += ', '
print_list += ' ]'
return print_list
def insertFirst(self, data):
new_node = Node(data)
temp_node = self.head
self.head = new_node
self.head.next = temp_node
self.list_size += 1
def insertMiddle(self, num, data):
if self.head.next == None:
insertLast(data)
return
node = self.selectNode(num)
new_node = Node(data)
temp_next = node.next
node.next = new_node
new_node.next = temp_next
self.list_size += 1
def insertLast(self, data):
node = self.head
while True:
if node.next == None:
break
node = node.next
new_node = Node(data)
node.next = new_node
self.list_size += 1
def selectNode(self, num):
if self.list_size < num:
print("Overflow")
return
node = self.head
count = 0
while count < num:
node = node.next
count += 1
return node
def deleteNode(self, num):
if self.list_size < 1:
return # Underflow
elif self.list_size < num:
return # Overflow
if num == 0:
self.deleteHead()
return
node = self.selectNode(num - 1)
node.next = node.next.next
del_node = node.next
del del_node
def deleteHead(self):
node = self.head
self.head = node.next
del node
def size(self):
return str(self.list_size)
if __name__ == "__main__":
m_list = SingleLinkedList(1)
m_list.insertLast(5)
m_list.insertLast(6)
print('LinkedList :', m_list)
print('LinkedList Size() :', m_list.size())
print('LinkedList SelectNode(1) :', m_list.selectNode(1))
m_list.insertMiddle(1, 15)
print('LinkedList Insert Middle(1, 15) :', m_list)
m_list.insertFirst(100)
print('LinkedList Insert First(100) : ', m_list)
print('LinkedList SelectNode(0) :', m_list.selectNode(0))
m_list.deleteNode(0)
print('LinkedList Delete Node(0) : ', m_list)
m_list.deleteNode(1)
print('LinkedList Delete Node(1) : ', m_list)LinkedList : [ 1, 5, 6 ]
LinkedList Size() : 3
LinkedList SelectNode(1) : 5
LinkedList Insert Middle(1, 15) : [ 1, 5, 15, 6 ]
LinkedList Insert First(100) : [ 100, 1, 5, 15, 6 ]
LinkedList SelectNode(0) : 100
LinkedList Delete Node(0) : [ 1, 5, 15, 6 ]
LinkedList Delete Node(1) : [ 1, 15, 6 ]원형 연결 리스트
"원형 연결 리스트를 구현해서 얻는 이점이 뭘까?" 원형 연결 리스트를 구현하여 했던 생각이다. 단순히 머리와 꼬리를 연결하는게 어떤 이점이 있을까? 필자가 느꼈던 가장 큰 장점은 마지막 노드에 삽입할 경우였다. 단순 연결 리스트의 경우 마지막에 삽입할때 어떤 루틴이었는지 되돌아보면
- 헤드 -> 노드 -> ... -> 노드 ->
None
None이 나올때까지 노드를 탐색하고 마지막에 넣을 수 있게된다. 원형 연결 리스트는 그럴 필요없이 꼬리와 머리 사이에 넣으면 되기에 성능상 큰 이점이 있다.
- 노드 -> 테일 ->
new_node-> 헤드 -> 노드 ->
아래는 극단적인 결과값이다. 1부터 10000까지 마지막 노드에 삽입했을때 걸린 시간이다.
▲ 단순 연결 리스트 사용시
▲ 원형 연결 리스트 사용시
원형 연결 리스트 전체 소스코드
class CircleLinkedList:
def __init__(self, data):
new_node = Node(data)
self.head = new_node
self.tail = None
self.list_size = 1
def __str__(self):
print_list = '[ '
node = self.head
while True:
print_list += str(node)
if node == self.tail:
# 단순 연결 리스트와 달리
# 노드가 테일 노드면 끝난다
break
node = node.next
print_list += ', '
print_list += ' ]'
return print_list
def insertFirst(self, data):
new_node = Node(data)
if self.tail == None:
self.tail = self.head
temp_node = self.head
self.head = new_node
self.head.next = temp_node
self.tail.next = new_node
self.list_size += 1
def insertMiddle(self, num, data):
node = self.selectNode(num)
new_node = Node(data)
temp_next = node.next
node.next = new_node
new_node.next = temp_next
self.list_size += 1
def insertLast(self, data):
new_node = Node(data)
if self.tail == None:
self.tail = new_node
self.head.next = self.tail
else:
self.tail.next = new_node
self.tail = new_node
self.tail.next = self.head
self.list_size += 1
def selectNode(self, num):
if self.list_size < num:
print("Overflow")
return
node = self.head
count = 0
while count < num:
node = node.next
count += 1
return node
def deleteNode(self, num):
if self.list_size < 1:
return # Underflow
elif self.list_size < num:
return # Overflow
if num == 0:
self.deleteHead()
return
node = self.selectNode(num - 1)
node.next = node.next.next
del_node = node.next
del del_node
def deleteHead(self):
node = self.head
self.head = node.next
del node
def size(self):
return str(self.list_size)단순 연결 리스트와 비교해 앞단에 삽입할 때와 뒷단에 삽입할 때를 제외하곤 전체적으로 비슷하다. (단순 연결 리스트 코드를 기반으로 수정해서 그런가... 왠지 놓친 부분이 있을 것 같은 예감이다.)
이중 연결 리스트
이중 연결 리스트의 경우에 느껴졌던 장점은 탐색이었다. 중간에 있는 값 혹은 뒤쪽에 가까운 값을 찾아내고 싶을때 단일이든 원형이든 헤드부터 순차적으로 찾아나간다. 하지만 이중 연결 리스트는 똑같이 헤드에서 시작하지만 뒤쪽으로 이동할 수 있다.
class Node:
def __init__(self, data):
self.data = data
self.next = None
self.prev = None
def __str__(self):
return str(self.data)따라서 노드의 변경이 약간 필요하다. 이중 연결 리스트를 구현하면서 주의해야 겠다고 생각한건 단일 연결 리스트의 경우 한쪽으로 연결만 해주면 됐지만 이중은 가는쪽을 고쳤으면 오는쪽도 반드시 고치라는 것이다. 당연한건데 많이 놓쳤던 부분이다.
이중 연결 리스트 전체 소스코드
class Node:
def __init__(self, data):
self.data = data
self.next = None
self.prev = None
def __str__(self):
return str(self.data)
class DualLinkedList:
def __init__(self, data):
new_node = Node(data)
self.head = new_node
self.list_size = 1
def __str__(self):
print_list = '[ '
node = self.head
while True:
print_list += str(node)
if node.next == self.head:
break
node = node.next
print_list += ', '
print_list += ' ]'
return print_list
def insertFirst(self, data):
new_node = Node(data)
if not self.head.prev == None:
new_node.prev = self.head.prev
self.head.prev.next = new_node
if not self.head.next == None:
new_node.next = self.head.next
self.head.prev = new_node
self.head = new_node
def insertMiddleAfter(self, num, data):
node = self.selectNode(num)
new_node = Node(data)
new_node.prev = node
new_node.next = node.next
node.next.prev = new_node
node.next = new_node
self.list_size += 1
def insertMiddleBefore(self, num, data):
node = self.selectNode(num)
new_node = Node(data)
new_node.prev = node.prev
new_node.next = node
node.prev.next = new_node
node.prev = new_node
self.list_size += 1
def insertLast(self, data):
new_node = Node(data)
if self.head.next == None:
self.head.next = new_node
new_node.prev = self.head
if not self.head.prev == None:
self.head.prev.next = new_node
new_node.prev = self.head.prev
self.head.prev = new_node
new_node.next = self.head
self.list_size += 1
def selectNode(self, num):
if self.list_size < 1:
return # Underflow
elif self.list_size <= num:
return # Overflow
count = 0
node = self.head
if int(self.list_size/2) > num:
while count < num:
node = node.next
count += 1
else:
repeat = self.list_size - num
while count < repeat:
node = node.prev
count += 1
return node
def deleteNode(self, num):
if self.list_size < 1:
return # Underflow
elif self.list_size <= num:
return # Overflow
if num == 0:
self.deleteHead()
return
node = self.selectNode(num)
node.prev.next = node.next
node.next.prev = node.prev
del node
def deleteHead(self):
node = self.head
node.prev.next = node.next
node.next.prev = node.prev
self.head = node.next
del node
def size(self):
return str(self.list_size)
Ghost