Doubly Linked List

Doubly Linked List

기존의 단순 연결리스트는 일련의 요소들을 다룰떄에 효과적이지만, 단점이 있습니다. 연결리스트를 운행할 때에 링크에 반대쪽으로 운행할 필요가 있을 경우에도 항상 연결리스트 첫 노드로 이동한 후 운행을 다시 시작하는 불편함이 있습니다. 그러나, 이중 연결 리스트는 이러한 단점을 없애기 위해서 노드에 prev 에 이전 노드를 참조하도록 합니다.

<이중 연결 리스트 노드>

Node Class

class Node:

    """ 가볍고, 논퍼블릭한 이중 연결 리스트 노드 """

    __slots__ = '_element', '_prev', '_next'

    def __init__(self, element, prev, nxt):
        self._element = element
        self._prev = prev
        self._next = nxt

더블 링크드 리스트 구현

class DoublyLinkedList:
    class Node:

        """ 가볍고, 논퍼블릭한 이중 연결 리스트 노드 """

        __slots__ = '_element', '_prev', '_next'

        def __init__(self, element, prev, nxt):
            self._element = element
            self._prev = prev
            self._next = nxt

    def __init__(self):

        """ 빈 링크드 리스트 생성 """

        self._header = self.Node(None,None,None)
        self._trailer = self.Node(None,None,None)
        self._header._next = self._trailer
        self._trailer._prev = self._header
        self._size = 0

    def __len__(self):

        """ 리스트의 크기를 리턴 """

        return self._size


    def is_empty(self):

        """ 리스트 크기가 0 일경우 True 반환 """
        return self._size == 0

    def insert_between(self. e, predecessor, succesor):

        """ 존재하는 두 노드 사이에 새로운 요소를 이어주고 새로운 노드를 반환 """

        newest  = self.Node(e, predecessor, succesor)
        predecessor._next = newest
        succesor._prev = newest
        self.size +=1

        return newest

    def delete_node(self,node):

        predecessor = node._prev
        succesor = node._next
        predecessor._next = sucessor
        sucessor._prev = predecessor
        self.size -=1
        element = node._element

        node._prev = node._next = node._element = None

        return element

더블 링크드 리스트로 Deque 구현

""" 이중 연결 리스트 클래스를 상속 """
class LinkedDeque(DoublyLinkedList):

    def first(self):

    """ 리스트의 첫반째 요소를 반환 삭제x"""

    if self.is_empty:
        raise Empty("Deque is empty")

    return self._header._next._element

    def last(self):

    """ 리스트의 마지막 요소를 반환 삭제x"""

    if self.is_empty:
        raise Empty("Deque is empty")

    return self._trailer._prev._element

    def insert_first(self, e):

    """ 요소를 데크 맨 앞에 삽입 """

        self.insert_between(e, self._header, self._header._next)

    def insert_last(self, e):

    """ 요소를 데크 맨 앞에 삽입 """

        self.insert_between(e, self._trailer._prev, self._trailer)

    def delete_first(self):

    """ 데크 맨앞의 노드를 제거후 그 요소를 반환 """

        if self.is_empty():
            raise Empty("Deque is empty")

        return self.delete_node(self._header._next)

    def delete_last(self):

    """ 데크 마지막 노드를  제거후 그 요소를 반환 """

        if self.is_empty():
            raise Empty("Deque is empty")

        return self.delete_node(self._trailer._prev)