시작하기에 앞서,
연결리스트(Linked List)란, 노드의 집합으로서 각 노드가 데이터와 포인터를 가지고 한 줄로 연결되어 있는 방식으로 데이터를 저장하는 자료구조이다.
여기서 말하는 노드란 무엇일까?
1. 노드
노드란, 다음 노드의 주소를 저장하고 데이터를 저장하는 데이터의 묶음이라고 볼 수 있다.
다음은 단일 연결리스트에서의 노드 모습을 볼 수 있다.
여기서 볼 수 있듯이 우리가 실제로 필요한 데이터를 Node 안의 Data에 담고 있는 모습을 볼 수 있으며
다음의 데이터를 참조하기 위해 다음 노드의 주소를 저장하는 Next를 담고 있는 모습을 확인할 수 있다.
그렇다면 실제로 연결리스트는 이러한 노드로 어떻게 이루어져 있는지 확인해보자.
2. 연결리스트
해당 연결리스트는 연결리스트 중 단일 연결리스트를 나타내고 위에서 설명한 노드들이 연속적으로 연결되어 배열(파이썬에서의 리스트)와 같이 사용할 수 있게 된다.
Node는 위에서 언급한 것과 같이 데이터와 다음 노드의 위치를 나타내는 것임을 알지만 Head는 무엇일까?
Head는 해당 리스트의 시작점을 나타내는 Dummy이다.
이중 연결리스트에서는 리스트의 끝을 나타내는 Dummy인 tail을 추가하기도 한다.
이를 통해 얻을 수 있는 이점은 바로 다음 배열 vs 연결리스트에서 설명하겠다.
그렇다면 배열과 비슷한 면이 존재하지만 왜 연결리스트를 사용할까라는 의문이 들 수도 있다.
그에 대한 차이점에 대해 설명해보려고 한다.
3. 배열 vs 연결리스트
각각에서의 차이는 시간적인 측면의 효율성에서 나타난다.
이를 설명하기 위해, 다음 예시를 들어보려고 한다.
배열과 연결리스트에서 다음과 같이 동일한 데이터가 존재한다고 가정하자.
(1) 데이터 조회
데이터를 조회
배열에서는 단순히 해당 인덱스에 조회하면 되니 O(1)만큼이 소요될 것이다.
그에 비해, 연결리스트는 앞에서부터 차근히 해당 데이터까지 접근을 해야하니 해당 데이터가 k번째에 존재한다고 하면 O(k)만큼이 소요될 것이다.
조회 측면에서는 배열 자체가 조금 더 효율적이라고 볼 수 있다.
(2) 데이터 삽입
리스트의 끝에 추가
리스트의 끝에데이터를 추가하려고 할 때, 배열에서 추가하려면 Python의 List에서 append를 통해 단순 O(1)으로 진행할 수 있다.
연결리스트의 경우에는 리스트의 끝까지 찾아가 추가하려면 리스트의 총 개수가 n개라고 하면 찾아가는 비용 O(n) + 추가하는 비용 O(1)이 되어 총 O(n+1)이 될 것이다.
하지만 이중 연결리스트의 경우 head와 마찬가지로 Tail을 추가하게 되면 끝을 찾아가 해당 Tail 전의 노드로 접근하는 비용 O(1) + 추가하는 비용 O(1) 즉, 단순 O(2)의 비용으로 해결할 수 있다.
리스트의 처음에 추가
리스트의 처음에 데이터를 추가하려고 할 때, 배열에서는 처음에 추가를 하고 원래 있었던 모든 데이터들을 뒤로 밀어야 한다.
그에 따라 n개의 데이터가 배열에 존재했을 때, 추가하는 비용 O(1)과 데이터를 뒤로 미는 비용 O(n)이 들게 되어 총 O(n+1)으로 진행 하게 된다.
연결리스트의 경우에는 리스트의 처음 부분인 Head를 소유하고 있으므로 해당 Head와 그 다음 노드를 이용해 사이에 연결해주면 되 므로 리스트의 끝에서의 추가와 마찬가지로 접근하는데 O(1) 추가하는데 O(1) 총 O(2)으로 진행할 수 있다.
리스트의 중간에 추가
리스트의 중간에 데이터를 추가하려고 할 때, 배열에서는 k번째에 데이터를 추가하기 위해 n개의 데이터가 배열에 존재한다고 할 때, (n-k)개의 데이터를 뒤로 밀어야하기에 추가하는 비용 O(1)과 뒤로 미는 비용 O(n-k)이 들게 되어 총 O(n-k+1) 결국 O(n)으로 진행하게 된다.
연결리스트의 경우에는 해당 k번째까지 접근하는데 걸리는 비용 O(k) 추가하는 것의 비용 O(1)로서 총 O(k+1)의 비용이 들게 된다.
(3) 데이터 삭제
리스트의 끝에 삭제
리스트의 끝에데이터를 삭제하려고 할 때, 배열에서 삭제하려면 Python의 List에서 pop을 통해 단순 O(1)으로 진행할 수 있다.
연결리스트의 경우에는 리스트의 끝까지 찾아가 삭제하려면 리스트의 총 개수가 n개라고 하면 찾아가는 비용 O(n) + 추가하는 비용 O(1)이 되어 총 O(n+1)이 될 것이다.
하지만 이중 연결리스트의 경우 head와 마찬가지로 Tail을 추가하게 되면 끝을 찾아가 단순 삭제하면 해당 Tail 전의 노드로 접근하는 비용 O(1) + 추가하는 비용 O(1) 즉, 단순 O(2)의 비용으로 해결할 수 있다.
리스트의 처음에 삭제
리스트의 처음에 데이터를 삭제하려고 할 때, 배열에서는 처음에 삭제를 하고 원래 있었던 모든 데이터들을 앞으로 당겨야 한다.
그에 따라 n개의 데이터가 배열에 존재했을 때, 추가하는 비용 O(1)과 데이터를 앞으로 당기는 비용 O(n)이 들게 되어 총 O(n+1)으로 진행하게 된다.
연결리스트의 경우에는 리스트의 처음 부분인 Head를 소유하고 있으므로 해당 Head와 그 다음 노드를 이용해 사이에 연결해주면 되므로 리스트의 끝에서의 삭제와 마찬가지로 접근하는데 O(1) 삭제하는데 O(1) 총 O(2)으로 진행할 수 있다.
리스트의 중간에 삭제
리스트의 중간에 데이터를 삭제하려고 할 때, 배열에서는 k번째에 데이터를 삭제하기 위해 n개의 데이터가 배열에 존재한다고 할 때, (n-k)개의 데이터를 앞으로 당겨하기에 삭제하는 비용 O(1)과 앞으로 당기는 비용 O(n-k)이 들게 되어 총 O(n-k+1) 결국 O(n)으로 진행하게 된다.
연결리스트의 경우에는 해당 k번째까지 접근하는데 걸리는 비용 O(k) 삭제하는 것의 비용 O(1)로서 총 O(k+1)의 비용이 들게 된다.
이렇게 말로만 설명하면 연결리스트에서의 삽입과 삭제가 와닿지 않아 그림으로 표현하면 다음과 같다.
이렇게 배열과 연결리스트에서의 차이를 알아보았다.
하지만 전체적인 시간 복잡도를 확인해보면 조회 외에는 큰 차이를 느낄 수는 없다고 느낄 것이다.
하지만 "조회"라는 관점보다는 "추가"와 "삭제"라는 관점에서 보면 크게 느낄 것이다.
배열에서는 추가와 삭제 자체에서 뒤로 미는 작업과 앞으로 당기는 작업으로 인해 시간 복잡도가 상당히 크지만,
연결리스트 자체에서는 조회를 제외하고 추가와 삭제라는 행위만 보면 O(1)로 수행할 수 있다.
따라서, 우리는 추가와 삭제보다 조회가 주로 이루어지는 문제에서는 배열을 활용하면 좋을 것이고.
조회보다 추가와 삭제가 주로 이루어지는 문제에서는 연결 리스트를 활용하면 좋을 것이다.
필자는 지금까지 연결리스트 중 흔히 사용되는 단일 연결리스트와 이중 연결리스트 중 단일 연결리스트를 토대로 설명하였다.
이중 연결리스트는 단일 연결리스트와 달리 한 방향으로의 노드 연결이 아닌 양 방향으로의 연결을 지향한다는 점에서 차이가 존재한다.
그에 따라 이동이 용이해 단일 연결리스트에 비해 조회에서 용이하다는 장점이 존재한다.
이제 실제로 다음 코드들을 파이썬으로 구현해보자.
4. 단일 연결리스트
노드 구현
class Node():
def __init__(self, data):
self.data = data
self.next = None다음과 같이 다음 노드를 참조할 수 있도록 저장해주는 next, 데이터를 저장하는 data로 이루어진 Node 클래스를 구성하였다.
이 노드 클래스를 활용해 단일 연결리스트를 구성해보자.
단일 연결리스트 구현
class SingleLinkedList():
def __init__(self):
self.head = Node("dummy")
self.size = 0
def sizes(self):
return self.size
def isEmpty(self):
return False if self.size else True
def find(self, idx):
if self.size == 0 or idx >= self.size :
return IndexError
else:
store = self.head
for i in range(idx):
store = store.next
return store
def appendleft(self, data):
newNode = Node(data)
store = self.head.next
# head next 연결
self.head.next = newNode
newNode.next = store
self.size += 1
def append(self, data):
newNode = Node(data)
# 조회
store = self.head
while store.next != None:
store = store.next
# 연결
store.next = newNode
self.size += 1
def insert(self, idx, data):
if idx >= self.size:
return IndexError
newNode = Node(data)
# 조회
store = self.head
for i in range(idx):
store = store.next
# 연결
temp = store.next
store.next = newNode
newNode.next = temp
def delete(self, idx):
if self.size == 0 or idx >= self.size:
return IndexError
else:
# 조회
store = self.head
for i in range(idx):
store = store.next
# 연결
temp = store.next.next
store.next = temp
self.size -= 1
def __str__(self):
s = ""
store = self.head.next
while store.next:
s += str(store.data) + " -> "
store = store.next
s += str(store.data)
return s
단일 연결리스트 테스트
# Single LinkedList Insert Test
link = SingleLinkedList()
for i in range(4):
link.append(i)
print("SingleLinkedList Print :", link) # LinkedList 출력
link.insert(3, 5) # LinkedList 삽입
print("SingleLinkedList Print :", link) # LinkedList 출력
print("SingleLinkedList Size :", link.sizes()) # LinkedList 사이즈
print("SingleLinkedList isEmpty :", link.isEmpty()) # LinkedList Empty 확인
print()
# Single LinkedList Delete Test
link.delete(1) # LinkedList
print("SingleLinkedList Print :", link)
print("SingleLinkedList Size :", link.sizes())
테스트 결과
5. 이중 연결리스트
이중 연결리스트 구현
class DoubleLinkedList():
def __init__(self):
self.head = Node("dummy")
self.size = 0
self.tail = Node("dummy")
self.head.next = self.tail
self.tail.prev = self.head
def sizes(self):
return self.size
def isEmpty(self):
return False if self.size else True
def find(self, idx):
if self.size == 0 or idx >= self.size :
return IndexError
else:
if (self.size - idx) > idx:
store = self.head
for i in range(idx):
store = store.next
else:
store = self.tail
for i in range(idx):
store = store.prev
return store
def appendleft(self, data):
newNode = Node(data)
store = self.head.next
# head와 양방향 연결
self.head.next = newNode
newNode.prev = self.head
# next node와 양방향 연결
store.prev = newNode
newNode.next = store
self.size += 1
def append(self, data):
newNode = Node(data)
store = self.tail.prev
# tail과 양방향 연결
newNode.next = self.tail
self.tail.prev = newNode
# prev node와 양방향 연결
store.next = newNode
newNode.prev = store
self.size += 1
def insert(self, idx, data):
if idx >= self.size:
return IndexError
else:
newNode = Node(data)
if (self.size - idx) > idx:
store = self.head
for i in range(idx):
store = store.next
else:
store = self.tail
for i in range(self.size-idx+1):
store = store.prev
temp = store.next
# 중간에 양방향 연결
store.next = newNode
newNode.prev = store
newNode.next = temp
temp.prev = newNode
def delete(self, idx):
if self.size == 0 or idx >= self.size:
return IndexError
else:
if (self.size - idx) > idx:
store = self.head
for i in range(idx):
store = store.next
else:
store = self.tail
for i in range(idx):
store = store.prev
temp = store.next.next
store.next = temp
temp.prev = store
self.size -= 1
def __str__(self):
s = ""
store = self.head.next
while store.next:
s += str(store.data) + " -> "
store = store.next
s += str(store.data)
return s
이중 연결리스트 테스트
# Double LinkedList Insert Test
link = DoubleLinkedList()
for i in range(4):
link.append(i)
print("DoubleLinkedList Print :", link) # LinkedList 출력
link.insert(3, 5) # LinkedList 삽입
print("DoubleLinkedList Print :", link) # LinkedList 출력
print("DoubleLinkedList Size :", link.sizes()) # LinkedList 사이즈
print("DoubleLinkedList isEmpty :", link.isEmpty()) # LinkedList Empty 확인
print()
# Double LinkedList Delete Test
link.delete(1) # LinkedList
print("DoubleLinkedList Print :", link)
print("DoubleLinkedList Size :", link.sizes())
테스트 결과
구현 코드