[자료구조 / Python] 이중 연결 리스트 | Doubly Linked List using Python

class DList:
    
    class Node:
        def __init__(self, item, prev, link):  # 노드 생성자
            self.item = item  # 항목
            self.prev = prev  # 앞노드 레퍼런스
            self.next = link  # 뒤노드 레퍼런스
 
    def __init__(self):  # 이중 연결 리스트 생성자
        # head, tail, 항목수로 구성
        # 두 더미노드(head, tail)에는 실제 항목 저장하지 않음
        self.head = self.Node(None, None, None)
        self.tail = self.Node(None, self.head, None)
        self.head.next = self.tail
        self.size = 0
 
    def size(self):
        return self.size
 
    def isempty(self):
        return self.size == 0
 
    def insert_before(self, p, item):  # p가 가리키는 노드 앞에 새 노드를 삽입
        t = p.prev # p 앞의 기존 노드
        n = self.Node(item, t, p)  # 삽입할 노드
        p.prev = n  # 새 노드와 뒤 노드 연결
        t.next = n  # 새 노드와 앞 노드 연결
        self.size += 1 
 
    def insert_after(self, p, item):  # p가 가리키는 노드 뒤에 새 노드를 삽입
        t = p.next # p 뒤의 기존 노드
        n = self.Node(item, p, t)  # 삽입할 노드
        t.prev = n  # 새 노드와 뒤 노드 연결
        p.next = n  # 새 노드와 앞 노드 연결
        self.size += 1
 
    def delete(self, x):  # 노드 x 삭제
        f = x.prev # x 앞의 기존 노드
        r = x.next # x 뒤의 기존 노드
        f.next = r  # x를 건너뛰고 x의 앞뒤 노드를 연결
        r.prev = f  # x를 건너뛰고 x의 앞뒤 노드를 연결
        self.size -= 1
        return x.item
 
    def print_list(self):
        if self.isempty():
            print('List is empty.')
        else:
            p = self.head.next
            while p != self.tail:
                if p.next != self.tail:
                    print(p.item, ' <=> ', end='')
                else:
                    print(p.item)
                p = p.next  # 노드를 차례로 방문
 
class EmptyError(Exception):  # Underflow시 에러 처리
    pass
 
 
s = DList() # 이중 연결 리스트 생성
s.insert_after(s.head, 'apple') 
s.insert_before(s.tail, 'orange')
s.insert_before(s.tail, 'cherry')
s.insert_after(s.head.next, 'pear')
s.print_list()
 
print('마지막 노드 삭제 후:\t', end='')
s.delete(s.tail.prev)
s.print_list()
 
print('맨 끝에 포도 삽입 후:\t', end='')
s.insert_before(s.tail, 'grape')
s.print_list()
 
print('첫 노드 삭제 후:\t', end='')
s.delete(s.head.next)
s.print_list()
 
print('두 번째 노드 삭제 후:\t', end='')
s.delete(s.head.next.next)
s.print_list()
 
print('첫 노드 삭제 후:\t', end='')
s.delete(s.head.next)
s.print_list()
 
print('첫 노드 삭제 후:\t', end='')
s.delete(s.head.next)
s.print_list()

출처 : https://it-garden.tistory.com/326?category=864289