double linked list 구현

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번 이동을 해주어야 되기 때문에 비효율적인 탐색이 있는데, 양방향 리스트에서는 이 부분을 해결할 수 있다. 그 외에도 삽입, 삭제의 경우 index의 위치에 따라 2/n 번만 이동해도 찾아낼 수 있기 때문에, 조금이나마 효율적인 탐색이 가능하다.