デュアルチェーンテーブルの実装

class Node: 
    def __init__(self, value, next, prev):
        self.value = value
        self.next = next
        self.prev = prev # 일반 연결리스트에 예전 노드로 돌아갈 수 있는 변수 추가


class DoublyLinkedList:
    def __init__(self):
        self.head = None
        self.tail = None # 끝을 판단할 수 있는 변수 추가
        self.length = 0

    def is_empty(self):
        if self.head == None:
            return True
        else:
            return False

    def prepend(self, value):
        if self.head == None: # 노드가 아무것도 없는 경우
            node = Node(value, None, None)
            self.head = node
            self.tail = node # 꼬리까지 노드로 지정
        else: # 리스트가 존재할 경우 
            node = Node(value, self.head, None)
            self.head.prev = node # 새로운 노드를 현재 헤드의 노드가 가르키게 함
            self.head = node # 현재 헤드를 새로운 노드로 바꿔줌
        self.length += 1

    def append(self, value):
        if self.tail == None:
            node = Node(value, None, None)
            self.head = node
            self.tail = node
        else:
            node = Node(value, None, self.tail)
            self.tail.next = node # 새로운 노드를 현재 꼬리가 가리키게 함
            self.tail = node # 새로운 노드가 꼬리가 됨
            # 기존 단방향 리스트는 끝까지 탐색해야 했는데, 양방향은 O(1)로 탐색 가능
        self.length += 1

    def set_head(self, index):
        if self.length <= index or index < 0:
            return "list index out of range"
        else:
            curr = self.head
            for _ in range(index): 
                curr = curr.next
            self.head = curr
            self.head.prev = None
        self.length -= index

    def set_tail(self, index): # 헤드를 꼬리에서 부터 시작해주는 것 외에 다른 것 없음
        if self.length <= index or index < 0:
            return "list index out of range"
        else:
            curr = self.tail 
            for _ in range(self.length - index):
                curr = curr.prev
            self.tail = curr
            self.tail.next = None
        self.length -= (self.length - index)


    def access(self, index):
        if self.length <= index or index < 0:
            return "list index out of range"
        else:
            if index >= self.length // 2:
                # 인덱스가 절반보다 클 경우 tail에서부터 접근
                # 양방향 리스트의 이점을 살리기 위해
                curr = self.tail
                for _ in range(self.length - index - 1):
                    curr = curr.prev
                return curr.value

            else:
                # 반대일 경우 head에서부터 접근
                curr = self.head
                for _ in range(index):
                    curr = curr.next
                return curr.value

    def insert(self, index, value):
        if self.length <= index or index < 0:
            return "list index out of range"
        else:
            if index == 0:
                self.prepend(value)
            elif index == self.length-1:
                self.append(value)
            else:
                if index >= self.length // 2:
                    # 인덱스가 절반보다 클 경우 tail에서부터 접근
                    curr = self.tail
                    for _ in range(self.length - index):
                        curr = curr.prev
                    node = Node(value, curr.next, curr)
                    curr.next = node

                else:
                    # 반대일 경우 head에서부터 접근
                    curr = self.head
                    for _ in range(index-1):
                        curr = curr.next
                    node = Node(value, curr.next, curr)
                    curr.next = node
                self.length += 1

    def remove(self, index):
        if self.length <= index or index < 0:
            return "list index out of range"
        else:
            if index >= self.length // 2:
                # 인덱스가 절반보다 클 경우 tail에서부터 접근

                if index == self.length -1:
                    self.tail = self.tail.prev
                    self.tail.next = None
                else:
                    curr = self.tail
                    for _ in range(self.length - index):
                        curr = curr.prev
                    curr.next = curr.next.next
                    curr.next.prev = curr

            else:
                # 반대일 경우 head에서부터 접근
                if index == 0:
                    self.head = self.head.next
                    self.head.prev = None
                else:
                    curr = self.head
                    for _ in range(index - 1):
                        curr = curr.next
                    curr.next = curr.next.next
                    curr.next.prev = curr
            self.length -= 1

    def print(self):
        curr = self.head
        while curr != None:
            print(curr.value, end=" ")
            curr = curr.next
        print()

    def print_inverse(self):
        curr = self.tail
        while curr != None:
            print(curr.value, end=" ")
            curr = curr.prev
        print()

基本的には,双方向リストを実現する際には,一方向リストの欠点を補うことができるように実現すべきであると考えられる.特にappendは,最初から最後までn回移動しなければならないため,効率の悪いナビゲーションがあり,双方向リストでこれを解決できる.また,挿入,削除の際には,インデックスの位置に応じて2/n回移動するだけで見つけることができるため,いくつかの有効な検索が可能である.