4. 양방향 연결 리스트 (Doubly linked list ADT) 파이썬

단방향 연결리스트는 역방향 탐색이 쉽지 않습니다.
이를 해결하는 가장 쉬운 방법은 이전 노드의 링크를 만들어 주는 것입니다. 

 

이럴 경우 메모리를 좀 더 소모하고, 프로그램이 약간 복잡해지는 단점이 있습니만, 
삭제 과정에서 이전 노드를 찾을 필요가 없기 때문에 삭제가 단순해지는 장점도 있습니다. 

 

실제로 프로그래밍을 해보면 단방향에서 조금만 코드를 수정하면 됩니다. 
단방향과 비교해서 뭐가 달라졌는지 확인해보십시오. 

 

 

class Node:
    def __init__(self, element):
        self.element = element
        self.next = None
        self.previous = None


class DoublyLinkedList:
    def __init__(self):
        self.head = Node('head')

    def find(self, item):
        cur_node = self.head
        while cur_node.element != item:
            cur_node = cur_node.next
        return cur_node

    def insert(self, item, new):
        new_node = Node(new)
        cur_node = self.find(item)
        new_node.next = cur_node.next
        cur_node.next = new_node
        new_node.previous = cur_node

    def show(self):
        cur_node = self.head
        while cur_node.next is not None:
            print(cur_node.element, end=' -> ')
            cur_node = cur_node.next
        print(cur_node.element)

    """ find_previous 는 사용할 필요가 없다. """

    def remove(self, item):
        cur_node = self.find(item)

        cur_node.previous.next = cur_node.next
        cur_node.previous = None

        if cur_node.next is not None:
            cur_node.next.previous = cur_node.previous
            cur_node.next = None

    def find_last(self):
        cur_node = self.head
        while cur_node.next is not None:
            cur_node = cur_node.next
        return cur_node

    def show_reverse(self):
        cur_node = self.find_last()
        while cur_node.previous is not None:
            print(cur_node.element, end=' <- ')
            cur_node = cur_node.previous
        print(cur_node.element)


boo = DoublyLinkedList()
boo.insert('head', '1')
boo.insert('1', '2')
boo.insert('2', '3')
boo.insert('3', '4')
boo.show()
boo.remove('4')
boo.show()
print(boo.find_last().element)
boo.show_reverse()

head -> 1 -> 2 -> 3 -> 4
head -> 1 -> 2 -> 3
3
3 <- 2 <- 1 <- head