dummy double linked list

• 구현 편의성을 위해서 Dummy(데이터를 가지지 않는 노드) 사용
• 즉, head와 Tail은 데이터를 가지지 않음
• head : 리스트 맨 앞에 있는 더미를 가리킴
• tail : 리스트 맨 뒤에 있는 더미를 가리킴
• size : 리스트의 요소 개수

  class Node:
  
      def __init__(self, data = None):
          self.__data = data   # 노드가 가지는 데이터 변수
          self.__prev = None   # 이전 노드를 가리키는 변수
          self.__next = None   # 다음 노드를 가리키는 변수
          
      def __del__(self):
          print(f"deleted : [{self.__data}]")
         
      @property
      def data(self):
          return self.__data
      
      @data.setter
      def data(self, data):
          self.__data = data
          
      @property
      def prev(self):
          return self.__prev
     
      @prev.setter
      def prev(self, prev):
          self.__prev = prev
          
      @property
      def next(self):
          return self.__next
      
      @next.setter
      def next(self, next):
          self.__next = next
  
  
  class DoubleLinkedList:
    
      def __init__(self):
          # dummy 생성 시점
          # head, tail, d_size
          # head와 tail은 연결
          # 노드 추가 전이기 때문에 생성된 dummy의 head와 tail이 연결
          self.head = Node()  # head Dummy 노드 생성
          self.tail = Node()  # tail Dummy 노드 생성
          self.d_size = 0     # 리스트의 요소 개수 초기화
          self.head.next = self.tail # head Dummy가 tail Dummy를 가리킴
          self.tail.prev = self.head # tail Dummy가 head Dummy를 가리킴
          
      def empty(self):
          if self.d_size == 0:
              return True
          else:
              return False
          
      def size(self):
          return self.d_size
      
      def add_first(self, data):
          new_node = Node(data)
          
          # new_node 관점에서 연결
          # 그림 그려보기
          new_node.next = self.head.next
          new_node.prev = self.head
          
          # head 관점에서 연결(리스트 관점)
          # add_first는 head에 의존한다.
          # tail 쪽의 데이터 개수에 따라서 prev를 할 수 있기 때문에
          # head에서 접근해야 한다.
          self.head.next.prev = new_node
          self.head.next = new_node
          
          # 잊지 말고 사이즈 추가
          self.d_size += 1
         
      def add_last(self, data):
          new_node = Node(data)
          
          # new_node 관점에서 연결
          # 그림 그려보기
          new_node.prev = self.tail.prev
          new_node.next = self.tail
          
          # tail 관점에서 연결(리스트 관점)
          # add_last는 tail에 의존한다.
          self.tail.prev.next = new_node
          self.tail.prev = new_node
          
          # 잊지 말고 사이즈 추가
          self.d_size += 1
          
      def insert_after(self, data, node):
          new_node = Node(data)
          
          # new_node 관점에서 연결
          # 그림 그려보기
          new_node.next = node.next
          new_node.prev = node
         
          # node 관점에서 연결(리스트 관점)
          node.next.prev = new_node
          node.next = new_node
          
          # 잊지 말고 사이즈 추가
          self.d_size += 1
          
      def insert_before(self, data, node):
          new_node = Node(data)
          
          # new_node 관점에서 연결
          # 그림 그려보기
          new_node.prev = node.prev
          new_node.next = node
          
          # node 관점에서 연결(리스트 관점)
          node.prev.next = new_node
          node.prev = new_node
          
          # 잊지 말고 사이즈 추가
          self.d_size += 1
          
      def search_forward(self, target):
          cur = self.head.next
          
          # self.head로 시작하면 Dummy 노드이기 때문에 None이 나오게 된다.
          # 따라서 self.head의 다음 노드부터 시작해야 한다.
          # self.tail까지 순회해야 Dummy 노드를 포함하지 않는 범위까지 값을 읽는다.
          # 객체를 비교하기 때문에 "is" 비교를 사용
          while cur is not self.tail:
              if cur.data == target:
                  return cur
              cur = cur.next
          return None   # while문에 포함되지 않을 경우, None을 반환해야 한다.
      
      def search_backward(self, target):
          cur = self.tail.prev
          
          while cur is not self.head:
              if cur.data == target:
                  return cur
              cur = cur.prev
          return None
      
      def delete_first(self):
          # empty 조건을 달아주지 않으면 에러 발생
          if self.empty():
              return
          
          # self.head.next가 self.head.next.next가 되었기 때문에
          # self.head.next의 prev가 self.head가 되면 된다.
          # 그림 그려보기
          self.head.next = self.head.next.next
          self.head.next.prev = self.head
          
          # 잊지 말고 사이즈 감소
          self.d_size -= 1
         
      def delete_last(self):
          if self.empty():
              return
         
          # 그림 그려보기
          self.tail.prev = self.tail.prev.prev
          self.tail.prev.next = self.tail
          
          # 잊지 말고 사이즈 감소
          self.d_size -= 1
          
      def delete_node(self, node):
          
          # 그림 그려보기
          node.prev.next = node.next
          node.next.prev = node.prev
          
          # 잊지 말고 사이즈 감소
          self.d_size -= 1
      
      # 편의 함수 - generator
      def traverse(self, start = True):
          if start:
              # 리스트의 첫 데이터부터 순회하기 위해 head가 아닌 head.next
              cur =  self.head.next
              
              while cur is not self.tail:
                  yield cur
                  cur = cur.next
          else:
              # 리스트의 마지막 데이터부터 순회하기 위해 tail이 아닌 tail.prev
              cur = self.tail.prev
              
              while cur is not self.head:
                  yield cur
                  cur = cur.prev
  
  # "=="는 값을 비교하는 것이다.
  # "is"는 객체를 비교하는 것이다.
  # a = "I am your father"
  # b = "I an your father"
  # a == b --> True
  # a is b --> False
  # a와 b의 값은 똑같지만, 같은 객체는 아니다.
  
  def show_list(d_list):
      # generator
      g = d_list.traverse()
      
      for node in g:
          print(node.data, end = " ")
      print()
  
  
  if __name__ == "__main__":
     
      dlist = DoubleLinkedList()
      
  #    dlist.add_first(1)
  #    dlist.add_first(2)
  #    dlist.add_first(3)
  #    dlist.add_first(4)
  #    dlist.add_first(5)
      
      dlist.add_last(1)
      dlist.add_last(2)
      dlist.add_last(3)
      dlist.add_last(4)
      dlist.add_last(5)
      
      show_list(dlist)
      
      searched_data = dlist.search_backward(3)
      
      if searched_data:
          dlist.insert_before(15, searched_data)
  #         print(f'searched_data : {searched_data.data}')
      else:
          print("there is no data")
          
      show_list(dlist)
      dlist.delete_first()
      show_list(dlist)
      
      del_data = dlist.search_forward(15)
      
      if del_data:
          dlist.delete_node(del_data)
          del_data = None # del_data가 계속 찾은 노드를 가리키고 있기 때문에
                          # None 값을 넣어줘야 한다.
      else:
          print("기준 노드가 없습니다. 다시 확인하세요!")
          
      show_list(dlist)
      
      print("*"*20)
  
  >> 1 2 3 4 5 
     1 2 15 3 4 5 
     deleted : [1]
     2 15 3 4 5 
     deleted : [15]
     2 3 4 5 
     ********************
     deleted : [None]
     deleted : [None]
     deleted : [2]
     deleted : [3]
     deleted : [4]
     deleted : [5]