class LinkedListNode:

  def __init__(self, input_data):
    # 다음 노드에 대한 정보를 담는 인스턴스 변수
    # 다음 노드 지정은 선언 후 이루어집니다
    self.next_node = None
    # 이전 노드에 대한 정보를 담는 인스턴스 변수
    self.prev_node = None
    # 노드 인스턴스가 담을 데이터
    self.data = input_data

  # 노드가 소속된 연결리스트에 가장 뒤에 받은 데이터를 담는 새로운 노드를 추가하는 함수
  def append_to_tail(self, input_data):
    # 입력 받은 데이터를 생성해 end_node라는 변수에 할당
    end_node = LinkedListNode(input_data)
    # 루프동안 체크할 노드를 담을 temp_next를 선언 후 노드 자신을 할당
    temp_next = self
    while temp_next.next_node != None: # 자신이 가장 마지막 노드가 아니라면 루프 진행
      temp_next = temp_next.next_node  # temp_next를 temp_next.next_node로 할당해 다음 연결을 체크

    # 마지막 노드까지 진행되면 루프가 멈추고 temp_next에 현재까지 가장 마지막 노드가 할당됨
    temp_next.next_node = end_node # 가장 마지막 노드의 next_node에 위에서 새로 생성한 노드를 연결해주고 함수 끝

  # 양방향 연결리스트의 특징으로 자신의 이전 노드를 알 수 있어
  # 이전 노드 탐색 반복을 통해 어떤 노드에서도 헤드로의 추가가 가능합니다
  # 다만 노드에서 진행하는 append가 아닌 LinkedList 객체에서는 헤드로의 직접 접근이 가능하여
  # 이 메소드가 필요하지 않을 수 있습니다.
  def append_to_head(self, input_data):
    # 입력 받은 데이터를 생성해 start_node라는 변수에 할당
    start_node = LinkedListNode(input_data)
    # 루프동안 체크할 노드를 담을 temp_prev를 선언 후 노드 자신을 할당
    temp_prev = self
    while temp_prev.prev_node != None: # 자신이 첫번째 노드(헤드노드)가 아니라면 루프 진행
      temp_prev = temp_prev.prev_node  # temp_prev를 temp_prev.prev_node로 할당해 다음 연결을 체크

    # 마지막 노드까지 진행되면 루프가 멈추고 temp_prev에 현재까지 가장 마지막 노드가 할당됨
    temp_prev.prev_node = start_node # 가장 마지막 노드의 prev_node에 위에서 새로 생성한 노드를 연결해주고 함수 끝
    return start_node


  # 입력받은 노드를 자신의 다음 노드로 지정하는 함수
  # (연결리스트 시작점에 새로운 헤드노드를 할당시 사용)
  def point_next_node(self, input_node):
    self.next_node = input_node

  # 입력받은 노드를 자신의 이전 노드로 지정하는 함수
  # (연결리스트 시작점에 새로운 헤드노드를 할당시 사용)
  def point_prev_node(self, input_node):
    self.prev_node = input_node

class LinkedList:

  def __init__(self, head_data):
    # 연결리스트 정의부터 헤드노드를 인스턴스 변수로 할당
    # 연결리스트 정의때 입력받는 데이터는 헤드노드가 담고있을 데이터입니다
    self.head_node = LinkedListNode(head_data)

  # 입력받은 데이터를 담고있는 노드를 연결리스트에서 삭제하는 함수
  def delete_node(self, input_data):
    # 헤드노드 부터 시작해 여러노드를 점검하기 위해 임시로 할당할 변수 선언 및 헤드노드 할당
    temp_node = self.head_node
    if (temp_node.data == input_data): # 루프전, 조건 입력받은 데이터와 현재 체크하는 노드의 데이터 동일 여부 확인
      temp_node.prev_node = None # 헤드노드가 될 노드의 prev_node 정보 제거
      self.head_node = temp_node.next_node
      return # 링크드리스트의 헤드노드를 헤드노드의 다음 노드로 지정하고 함수 리턴

    while temp_node.next_node != None: # 마지막 노드가 아니면 루프 진행
      if temp_node.next_node.data == input_data: # 체크노드 다음노드의 데이터와 입력 데이터 확인
        node_to_remove = temp_node.next_node
        temp_node.next_node.next_node.prev_node = temp_node # 다다음 노드의 prev_node를 먼저 temp_node로 연결
        temp_node.next_node = temp_node.next_node.next_node # 체크노드의 다음노드를 다음노드의 다음노드로 지정
        node_to_remove.next_node, node_to_remove.prev_node = None # 제거할 노드의 링크 제거

        return # 함수 리턴
      temp_node = temp_node.next_node # 루프 진행동안은 다음노드를 체크하기 위해 임시 변수를 다음 노드로 할당

  # 연결리스트에서 마지막 노드 다음노드로 새로운 노드를 추가하는 메소드
  def append_to_tail(self, input_data):
    # 노드 클래스의 메소드를 이용하여 간단히 구현가능
    self.head_node.append_to_tail(input_data)

  # 연결리스트에서 헤드보다 앞에 새로운 노드를 추가하는 메소드
  # 노드 클래스에서 생성한 메소드 없이 진행 방법
  def append_to_head(self, input_data):
    # 새로운 노드 정의
    new_head_node = LinkedListNode(input_data)
    # 현재 헤드노드가 새로운 노드를 prev_node로 지정
    self.head_node.point_prev_node(new_head_node)
    # 새로운 노드에게 현재 헤드노드를 다음노드로 가리키도록 지정
    new_head_node.point_next_node(self.head_node)
    # 연결리스트의 헤드노드를 새로운 노드로 지정
    self.head_node = new_head_node

  # 노드 클래스에서 정의한 메소드 사용방법
  def append_to_head_two(self, input_data):
    new_head = self.head_node.append_to_head(input_data)
    self.head_node = new_head