더블리 링크드 리스트 (Doubly Linked List)
노드들이 다음 노드 뿐만 아니라 이전 노드에 대한 레퍼런스까지 가진 링크드 리스트를 더블리 링크드 리스트라고 한다. 앞과 뒤의 노드에 대한 레퍼런스를 가지고 있기 때문에 양 방향으로 탐색할 수 있는 특징이 있다.
노드(Node)
class Node:
"""더블리 링크드 리스트 노드"""
def __init__(self, data) -> None:
self.data = data
self.next = None # 다음 노드에 대한 레퍼런스
self.prev = None # 이전 노드에 대한 레퍼런스
def __str__(self) -> str:
return str(self.data)
# 노드 인스턴스
node1 = Node(3)
node2 = Node(7)
node3 = Node(12)
# 노드 사이의 레퍼런스 설정
node1.next = node2
node2.prev = node1
node2.next = node3
node3.prev = node2
# 결과 출력
print(node1)
print(node1.next) # node2
print(node2.prev) # node1
print(node1.next.next) # node3
print(node3.prev.prev) # node13
7
3
12
3
Node 클래스를 보면 싱글리 링크드 리스트와는 달리 prev 속성이 추가되었다. 이를 통해 이전 노드에 대한 레퍼런스를 얻고 맨 뒤에서부터 앞으로 탐색을 할 수 있게 되었다.
더블리 링크드 리스트 (Doubly Linked List)
추가 연산 (append)
더블리 링크드 리스트의 append 연산에서 주목해야 할 점은 노드가 앞뒤로 연관되어 있으므로 서로 간 연결을 시키고 나서 tail을 옮겨주어야 한다는 것이다. 순서가 뒤섞여 tail에 먼저 새 노드의 레퍼런스를 담아버리면 이전 노드의 레퍼런스를 잃으므로 순서를 잘 지키자.
인덱스를 통해 노드를 찾는 indexing메소드와 값을 통해 노드를 찾는 search메소드는 싱글리 리스트와 같으므로 코드에 이미 추가했다.
class Node:
"""더블리 링크드 리스트 노드"""
def __init__(self, data) -> None:
self.data = data
self.next = None # 다음 노드에 대한 레퍼런스
self.prev = None # 이전 노드에 대한 레퍼런스
def __str__(self) -> str:
return str(self.data)
class DoublyLinkedList:
"""더블리 링크드 리스트"""
def __init__(self) -> None:
self.head = None
self.tail = None
def append(self, data):
"""노드 추가"""
new_node = Node(data)
if self.head is None:
self.head = new_node
self.tail = new_node
else:
self.tail.next = new_node
new_node.prev = self.tail
self.tail = new_node
def indexing(self, index):
"""인덱스로 링크드 리스트 접근"""
iterator = self.head
for _ in range(index):
iterator = iterator.next
return iterator
def search(self, data):
"""링크드 리스트 내에서 data와 매치되는 노드 리턴"""
iterator = self.head
while iterator is not None:
if iterator.data == data:
return iterator
iterator = iterator.next
return None
def print_all_nodes(self):
"""모든 노드 출력"""
iterator = self.head
while iterator is not None:
print(iterator.data)
iterator = iterator.next
# 링크드 리스트 인스턴스 생성
doubly_linked_list = DoublyLinkedList()
# 노드 추가
doubly_linked_list.append(3)
doubly_linked_list.append(7)
doubly_linked_list.append(12)
doubly_linked_list.append(15)
doubly_linked_list.append(32)
# 확인
doubly_linked_list.print_all_nodes()3
7
12
15
32
다음과 같이 노드들이 연결되어 있을 때 tail은 Node5를 가리키고 있고, Node5의 prev는 Node4, next는 None이다. 이때 새로운 노드를 append하려고 하면 tail을 통해 Node5에 접근해 Node5의 next를 new_node로 지정하고, new_node는 prev를 Node5로 지정해준 뒤 tail을 new_node로 옮겨주면 된다.
삽입 연산 (insert_after)
class SinglyLinkedList:
"""싱글리 링크드 리스트"""
def insert_after(self, previous_node, data):
"""특정 노드 뒤에 새로운 노드 추가"""
new_node = Node(data)
if previous_node == self.tail:
self.tail.next = new_node
new_node.prev = self.tail
self.tail = new_node
else:
# 새로운 노드가 기존 노드 앞뒤를 각각 레퍼런스하도록 설정
new_node.prev = previous_node
new_node.next = previous_node.next
# 기존 노드가 새로운 노드를 레퍼런스하도록 설정(순서 중요!!)
previous_node.next.prev = new_node
previous_node.next = new_node
# 링크드 리스트 인스턴스 생성
doubly_linked_list = DoublyLinkedList()
# 노드 추가
doubly_linked_list.append(3)
doubly_linked_list.append(7)
doubly_linked_list.append(12)
doubly_linked_list.append(15)
doubly_linked_list.append(32)
# insert_after
test_node = doubly_linked_list.indexing(2)
doubly_linked_list.insert_after(test_node, 100)
# 확인
doubly_linked_list.print_all_nodes()3
7
12
100
15
32
임의의 노드 뒤에 새로운 노드를 연결시키는 연산으로, 임의의 노드가 가장 마지막 노드, 즉 tail일 경우와 링크드 리스트 중간의 어떤 노드일 경우를 나눠서 생각해야 한다.
tail일 경우는 append연산과 똑같이 해주면 되지만, 중간일 경우에는 조금 복잡하다. 새로운 노드를 기존 노드 사이에 삽입하면서 각 노드 앞뒤로 새롭게 연결을 시켜줘야 한다. 먼저 새로운 노드 new_node의 prev와 next를 각각 기존 노드로 연결시키고 그다음으로 기존 노드가 new_node를 연결시켜주면 된다.
previous_node.next.prev = new_node
previous_node.next = new_node
이때 순서가 중요한데, 만약 순서를 바꿔 previous_node.next를 먼저 new_node로 대체해버리면 previous_node.next.prev에 접근할 수 없게 된다.
맨앞 삽입 연산 (prepend)
append나 insert_after 메소드를 사용하면 링크드 리스트의 맨 앞에는 삽입이 불가능하다. 이를 해결하기 위해 prepend 메소드를 만들어보자.
class DoublyLinkedList:
"""더블리 링크드 리스트"""
def prepend(self, data):
"""가장 앞에 삽입하는 메소드"""
new_node = Node(data)
if self.head is None:
self.head = new_node
self.tail = new_node
else:
self.head.prev = new_node
new_node.next = self.head
self.head = new_node
head를 통해 맨 앞 노드에 바로 접근해 삽입할 수 있으므로 O(1)의 시간 복잡도를 가진다.
삭제 연산 (delete)
더블리 링크드 리스트는 노드가 앞과 뒤의 레퍼런스를 모두 갖고 있기 때문에 지우려는 노드의 앞뒤 노드를 서로 연결시켜주기만 하면 해당 노드를 삭제할수 있다. 따라서 싱글리 링크드 리스트에서는 해당 노드의 다음 노드만을 지울 수 있었던 것(delete_after)과는 달리 더블리 링크드 리스트는 해당 노드를 지울 수 있다.
다만 더블리 링크드 리스트에서 노드를 지울 때 고려해야 하는 케이스는 네가지가 있다. (1) 노드가 하나 또는 없는 경우, (2) 노드가 head인 경우, (3) 노드가 tail인 경우, (4) 일반적인 경우
def delete(self, node_to_delete):
"""노드를 삭제하는 메소드"""
if self.head == self.tail:
# 노드가 하나 또는 없는 경우
self.head = None
self.tail = None
elif node_to_delete == self.head:
# 노드가 head인 경우
self.head = self.head.next
self.head.prev = None
elif node_to_delete == self.tail:
# 노드가 tail인 경우
self.tail = self.tail.prev
self.tail.next = None
else:
# 일반적인 경우
node_to_delete.prev.next = node_to_delete.next
node_to_delete.next.prev = node_to_delete.prev
return node_to_delete.data삭제 연산은 주로 삭제된 노드의 값을 리턴하므로 return을 추가해주었다. 삽입 연산과 마찬가지로 삭제할 노드에 탐색하거나 접근해 삭제 연산을 해야 하므로 사실상 O(n)의 시간 복잡도를 가진다.
SLL vs DLL
| 요소 | Singly Linked List | Doubly Linked List |
| 공간 | 기본 공간: O(n) 추가적인 레퍼런스 공간 : O(n-1) = O(n) |
기본 공간: O(n) 추가적인 레퍼런스 공간: O(2n - 2) = O(n) |
| 공통점 | 어떤 노드던지 링크드 리스트 안 모든 노드에 접근할 수 있다. | |
| 차이점 | 뒤의 노드만 접근할 수 있다 | 뒤는 물론이고 앞의 노드도 접근할 수 있다 |
| 사용시기 | 앞의 노드에 접근할 필요가 없으며 공간을 더 효율적으로 사용하고자 할 때 | 앞과 뒤의 노드에 양방향으로 접근해야 할 때 |
'프로그래밍 > Computer Science' 카테고리의 다른 글
| [Data Structure] Linear - (4) Deque (0) | 2023.09.12 |
|---|---|
| [Data Structure] Linear - (3) Linked List - Circular Linked List (0) | 2023.09.11 |
| [Data Structure] Linear - (2) Linked List - Singly Linked List (0) | 2023.08.16 |
| [Data Structure] Linear - (1) Array (0) | 2023.08.16 |
| [Overview] 03. Operating Systems - (2) Kernel and Virtual Machine (0) | 2023.08.02 |