더블리 링크드 리스트란?
노드가 전 노드의 레퍼런스까지 저장하고 있는 더블리 링크드 리스트를 알아보자.
더블리 링크드리스트는 앞 노드와 뒤 노드에 대한 레퍼런스를 모두 갖는다.
각 노드가 바로 다음 노드에 대한 레퍼런스만 갖는 경우를 싱글리 링크드 리스트라고 한다.
더블리 링크드리스트는 뒤 노드에 대한 레퍼런스를 저장하는 next라는 속성과 바로 전 노드에 대한 레퍼런스를 저장하는 prev라는 속성으로 이루어진다.
더블리 링크드리스트 구현
prev라는 속성을 추가해준다.
class Node:
"""링크드 리스트 노드"""
def __init__(self, data):
self.data = data
self.next = None
self.prev = None그리고 LinkedList 클래스를 만들어준다.
find_node_at(접근 연산), find_node_with_data(탐색 연산), 그리고 __str__ 메소드가 싱글리 링크드 리스트랑 겹친다.
1. 접근
def find_node_at(self, index):
"""링크드 리스트 접근 연산 메소드. 파라미터 인덱스는 항상 있다고 가정한다"""
iterator = self.head # 링크드 리스트를 돌기 위해 필요한 노드 변수
# index 번째 있는 노드로 간다
for _ in range(index):
iterator = iterator.next
return iterator2. 탐색
def find_node_with_data(self, data):
"""링크드 리스트에서 주어진 데이터를 갖고있는 노드를 리턴한다. 단, 해당 노드가 없으면 None을 리턴한다"""
iterator = self.head # 링크드 리스트를 돌기 위해 필요한 노드 변수
while iterator is not None:
if iterator.data == data:
return iterator
iterator = iterator.next
return None3. str 메소드
def __str__(self):
"""링크드 리스트를 문자열로 표현해서 리턴하는 메소드"""
res_str = "|"
# 링크드 리스트 안에 모든 노드를 돌기 위한 변수. 일단 가장 앞 노드로 정의한다.
iterator = self.head
# 링크드 리스트 끝까지 돈다
while iterator is not None:
# 각 노드의 데이터를 리턴하는 문자열에 더해준다
res_str += " {} |".format(iterator.data)
iterator = iterator.next # 다음 노드로 넘어간다
return res_str4. 추가 append
새로운 노드를 맨 뒤에 추가하기 위해 원래 노드의 마지막 노드의 next를 새로운 노드로 설정, 새로운 노드의 prev를 원래 노드의 마지막으로 설정한 후에 tail을 새로운 노드로 설정한다.
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_node5. 삽입 insert_after
삽입의 경우도 두 가지 경우로 나누어서 볼 수 있다.
경우1) tail 노드 뒤에 삽입할 때
: append와 비슷하게 짠다.
경우2) 두 노드 사이에 삽입할 때
: 새로운 노드를 먼저 연결시키고, 이미 있는 노드들의 prev와 next를 새로운 노드로 지정한다.
def insert_after(self, previous_node, data):
new_node = Node(data)
if previous_node.next == None: # tail 노드 뒤에 삽입할 때:
new_node.prev = previous_node
previous_node.next = new_node
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_node6. prepend 메소드
링크드 리스트 가장 앞에 데이터를 추가시키는 메소드
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_node7. 삭제 연산
더블리 링크드 리스트는 전노드와 이후 노드의 레퍼런스를 모두 가지고 있다. 이걸 이용해 지우려는 노드와 링크드 리스트의 연결만 끊어주면 노드를 지울 수 있다.
싱글리 링크드 리스트와 달리 지우려는 노드 값 자체를 넘겨주면 된다.
총 4가지의 경우로 나누어 구현할 수 있다.
def delete(self, node_to_delete):
"""더블리 링크드 리스트 삭제 연산"""
# 지우려는 노드가 리스트의 마지막 남은 노드인 경우(하나 남아있고, 그걸 지우려는 경우)
if self.head == self.tail:
self.head = None
self.tail = None
# 헤드노드를 지우는 경우(여러 노드가 있고, 그중 헤드노드만 지우고 싶은 경우)
elif node_to_delete == self.head:
self.head = node_to_delete.next
self.head.prev = None
# tail 노드를 지우는 경우(여러 노드가 있고, 그중 tail노드만 지우고 싶은 경우)
elif node_to_delete == self.tail:
self.tail = node_to_delete.prev
self.tail.next = None
# 두 노드 사이에 있는 노드를 삭제할 경우
else:
node_to_delete.prev.next = node_to_delete.next # 지우려는 노드의 전 노드가 node_to_delete의 다음 노드를 가리키게 한다.
node_to_delete.next.prev = node_to_delete.prev # node_to_delete의 다음 노드가 node_to_delte의 전 노드를 가리키게 한다.
return node_to_delete.data싱글리 vs 더블리
-
싱글리 링크드리스트
- next 노드에 대한 레퍼런스만 저장
- 노드 접근) 특정 노드에서 앞에 있는 노드로 이동할 수 없다.
- 추가적 공간) 실제 데이터와 next노드에 대한 레퍼런스 저장 -> 링크드 리스트 안에 레퍼런스 개수 : n-1
따라서 O(n)의 추가적인 공간을 사용
-
더블리 링크드리스트
- prev, next 노드에 대한 레퍼런스 둘 다 저장
- 노드 접근) 어떤 노드던지 링크드리스트 안 모든 노드에 접근할 수 있다.
- 추가적 공간) 링크드 리스트 안에 레퍼런스 개수 : 2n-2
따라서 O(n)의 추가적인 공간을 사용
-
두 자료구조의 추가적인 공간복잡도가 동일하나, 실제로는 두 배정도 차이가 난다. 따라서 공간을 효율적으로 사용해야 할 때는 더블리 링크드리스트보다 싱글리 링크드리스트를 쓰는 게 더 좋다.
-
추가적 공간이란?
자료구조가 사용하는 공간 중 실제 저장하려는 데이터를 제외한 다른 정보가 저장된 공간을 의미
링크드 리스트 노드들은 다른 노드들에 대한 레퍼런스를 저장한다. 이 레퍼런스를 저장하는 공간을 추가적인 공간이라고 할 수 있다. 아래에서 빨간 부분을 의미한다.
