[Python] 양방향 연결리스트 구현

class Node:
    def __init__(self, data):
        self.data = data
        self.prev = None
        self.next = None

class DoublyLinkedList:
    def __init__(self):
        self.head = None
        self.tail = None

    def add(self, data):
        new_node = Node(data)
        if self.head is None:               # 비어있는 노드일 때
            self.head = new_node
            self.tail = new_node
            #new_node.prev = self.head
            #new_node.next = self.tail
        else:                               # 비어있는 노드가 아닐 때
            new_node.prev = self.tail       # 1. 새로운 노드의 prev에 이미 저장되어 있는 노드의 tail을 가르킴
            self.tail.next = new_node
            self.tail = new_node

    def remove(self, data):
        current = self.head
        while current is not None:
            if current.data == data:
                
                if current.prev is not None:    # 노드가 2번째 이상인 data를 없앨 때
                    current.prev.next = current.next # self.head.prev의 node의 next를 current.next인 노드와 연결 
                else:   #  단일 노드일 때
                    self.head = None
                
                if current.next is not None: # 양방향 연결리스트이므로 next도 다음 노드의 이전과 연결
                    current.next.prev = current.prev
                else: # 단일 노드일 때 
                    self.tail = None
                break
            current = current.next

    def search(self, data):
        current = self.head
        while current is not None:
            if current.data == data:
                return True
            current = current.next  # data를 찾을 때까지 다음 노드로 계속 이동
        return False
 
    def print_forward(self):
        current = self.head
        if self.head is None:
                print("데이터가 없습니다.")
                return
        while current is not None:
            print(current.data, end=" ")
            current = current.next
        print()
    
    def print_backward(self):
        current = self.tail
        while current is not None:
            print(current.data, end=" ")
            current = current.prev
        print()
        
    def insert(self, data, index):
        if index < 0 or index > self.length():  # 예외처리
            raise IndexError("Invalid index")

        new_node = Node(data)

        if index == 0:  # index 0 번째에 삽입
            if self.head is None:   # 연결리스트에 아무것도 없을 때
                self.head = new_node
                self.tail = new_node
            else:   # 연결리스트에 값이 있지만 0번 째 index에 삽입
                new_node.next = self.head   # 지금 self.head는 기존 노드의 index 0을 가르키고 있으므로 new_node의 next에 값을 대입
                self.head.prev = new_node   # self.head.prev를 하면 기존 노드의 index 0의 prev노드에 new_node를 가르키게 한다.
                self.head = new_node        # 새로운 노드와 index 0인 노드가 서로 연결되었으니 self.head는 new_node를 가르키게 한다.
                
        elif index == self.length():    # 마지막에 삽입
            self.add(data)
            
        else:
            current = self.head
            # for문으로 current가 다음 노드를 가르키고 끝나는 것이 아니라 index-1이므로 1 번째에 값을 삽입하면 
            # 0 번째 노드를 가르키고 for문을 탈출함 즉, index가 0에서 새로운 노드를 삽입하는 것임
            for _ in range(index - 1):      # 예시) insert(4,1)
                current = current.next      # 0번째 index의 next, 기존의 data 2 노드를 가르킨다.    
            new_node.next = current.next    # new_node.next를 data가 2인 노드를 가르키게 한다.    
            new_node.prev = current         # current는 현재 index 0이다. new_node의 prev에 index 0번째를 가르킨다.
            current.next.prev = new_node    # data 2인 노드의 prev에 new_node를 가르키도록 한다.
            current.next = new_node         # 현재 data 2인 노드를 가르키고 있으므로 new_node를 가르키도록 한다.

    def length(self):
        count = 0
        current = self.head
        while current is not None:
            count += 1
            current = current.next # 노드 개수를 계산하기 위해 다음 노드를 가르킨다. 
        return count
    
#예시 실행
doubly_linked_list = DoublyLinkedList()

# 노드 추가
doubly_linked_list.add(1)
doubly_linked_list.add(2)
doubly_linked_list.add(3)

# 전체 리스트 출력 (순방향)
print("Forward: ", end="")
doubly_linked_list.print_forward()  # Output: 1 2 3

# 전체 리스트 출력 (역방향)
print("Backward: ", end="")
doubly_linked_list.print_backward()  # Output: 3 2 1

# 노드 삽입
doubly_linked_list.insert(4, 1)  # 1 4 2 3
doubly_linked_list.insert(5, 0)  # 5 1 4 2 3
doubly_linked_list.insert(6, 5)  # 5 1 4 2 3 6

# # 전체 리스트 출력 (순방향)
print("Forward: ", end="")
doubly_linked_list.print_forward()  # Output: 5 1 4 2 3 6

# 전체 리스트 출력 (역방향)
print("Backward: ", end="")
doubly_linked_list.print_backward()  # Output: 6 3 2 4 1 5

# 노드 제거
doubly_linked_list.remove(4)

# 전체 리스트 출력 (순방향)
print("Forward: ", end="")
doubly_linked_list.print_forward()  # Output: 5 1 2 3 6