[파이썬 자료구조] 이중연결리스트(Doubly Linked Lists)

이중연결리스트: 이중연결리스트(doubly linked lists)는 각 노드가 앞과 뒤를 가리치는 두 개의 레퍼런스를 가지는 연결리스트

단순연결리스트는 삽입이나 삭제할 때 반드시 이전 노드를 가리키는 레퍼런스를 추가로 알아내야 하고, 역방향으로 노드들을 탐색할 수 없음

이중연결리스트는 단순연결리스트의 이러한 단점을 보완하나, 각 노드마다 추가로 한 개의 레퍼런스를 추가로 저장해야 한다는 단점을 가짐

간단하게 이중연결리스트를 구현해보면

파이썬 코드

class DList:
    class _Node:
        def __init__(self, element, prev, next): #노드의 생성자
            self._element = element #노드의 element값
            self._prev = prev #노드의 이전값
            self._next = next #노드의 다음값
 
    def __init__(self):
        self._header = self._Node(None, None, None) #header 자체가 노드입니다.
        self._trailer = self._Node(None, None, None) #trailer 노드 설정
        self._header._next = self._trailer #초기에는 header와 trailer노드로 구성
        self._trailer._prev = self._head 
        size = 0 #초기사이즈는 0
    
    def insert_between(self, element, predecessor, successor):
        new_node = self._Node(element, predecessor, successor)
        predecessor._next = new_node
        successor._prev = new_node
        self._size += 1
        return new_node
    
    def insert_after(self, element, p):
        insert_between(self, element, p, p._next)
    
    def insert_before(self, element, p):
        insert_between(self, element, p._prev, p)
    
    def insert_first(self, element):
        insert_after(self, element, self._header)
 
    def insert_last(self, element):
        insert_before(self, element, self._trailer)
   
    def delete_last(self): #맨 뒤 노드를 삭제하는 함수
        if size == 0:
            return 
        elif size == 1:
            self._header._next = self._trailer 
            self._trailer._prev = self._head 
            size -= 1
        else :
            q = self.trailer._prev
            p = q._prev
            self.trailer._prev = p
            size -= 1
    
    def delete_first(self): #맨 처음 노드를 삭제하는 함수
        if size == 0: 
            return 
        elif size == 1:
            self._header._next = self._trailer  #header와 trailer가 서로 가르키게한다.
            self._trailer._prev = self._head 
            size -= 1 #size가 하나 줄음
        else :
            q = self.header._next 
            p = q._next
            self.header._next = p
            size -= 1