이중 연결리스트는 연결리스트를 이루는 각 노드들이 다른 노드에 대한 참조 (이전 노드, 다음 노드)를 포함하여 탐색은 의 시간복잡도를 가지지만 삭제와 삽입에는 의 시간복잡도를 가져 삭제 및 삽입이 잦을 때에 효율적인 자료구조입니다.
하나의 노드를 표현하는 클래스
class Node:
def __init__(self, data):
self.data = data
self.prev = None
self.next = None
Python
복사
위와 같이 이전 노드와 다음 노드가 없는 노드를 단일 노드 (Singleton)이라고 합니다.
단일 노드 삽입
어떤 연결리스트에 속한 노드 u 뒤에 singleton을 삽입할 때에는 삽입하는 singleton의 prev와 next를 업데이트 해준 뒤 업데이트된 prev는 singleton을 next로, next는 singleton을 prev로 가지도록 업데이트 해줍니다. 코드를 보면 더 쉽게 이해할 수 있습니다.
def insert_next(u, singleton):
singleton.prev = u
singleton.next = u.next
if singleton.prev is not None:
singleton.prev.next = singleton
if singleton.next is not None:
singleton.next.prev = singleton
Python
복사
어떤 연결리스트에 속한 노드 u 앞에 singleton을 삽입할 때에는 삽입하는 singleton의 prev와 next를 업데이트 해주는 부분만 조금 바뀝니다.
def insert_prev(u, singleton):
singleton.prev = u.prev
singleton.next = u
if singleton.prev is not None:
singleton.prev.next = singleton
if singleton.next is not None:
singleton.next.prev = singleton
Python
복사
노드 삭제
연결 리스트에 속한 노드 u를 삭제하려면
노드 u는 단일 노드로 만들고 u의 이전노드와 다음 노드를 이어주면 됩니다.
def pop(u):
if u.prev is not None:
u.prev.next = u.next
if u.next is not None:
u.next.prev = u.prev
u.prev = u.next = None
Python
복사
