파이썬으로 더블 링크드리스트 구현

다양한 링크드 리스트 구조

• 더블 링크드 리스트 기본구조
  • 이중 연결 리스트라고도 함.
  • 장점: 양방향으로 연결되어 있어서 노드 탐색이 양쪽으로 모두가능
  • 단점: 이중 연결 리스트에는 일반적인 연결 리스트보다 포인터를 2배 더 많이 사용해야 하고, 구현이 복잡하다는 단점이 존재한다

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

# 노드메소드가 지정되어 있는 class
class Node:
  def __init__(self, data):
    self.head = MakeNode(data)
    self.tail = self.head

  # insert method 작성
  def insert(self, data):
    if self.head == None:
      self.head = MakeNode(data)
    else:
      node = self.head # 제일 앞 노드

      while node.next:
        node = node.next
      new_node = MakeNode(data)
      node.next = new_node
      new_node.prev = node
      self.tail = new_node
# ------------------------------------- #  
  def output(self):
    node = self.head
    while node:
      print(node.data)
      node = node.next
# ------------------------------------- #
  def search_from_head(self, data):
    checked = False
    if self.head == None:
      return checked

    node = self.head
    while node:
      if(node.data == data):
        checked = True
        return checked
      else:
        node = node.next
    print(23)
    return checked
# ------------------------------------- #
  def search_from_tail(self, data):
    if self.head == None:
      return False
    node = self.tail
    while node:
      if(node.data == data):
        return True
      else:
        node = node.prev
    return False
# ------------------------------------- #

  def insert_before(self, data, before_data):
    if self.head == None:
      self.head = MakeNode(data)
      return True
    
    else:
      node = self.tail

      while node.data != before_data:
        node = node.prev
        if node == None:
          return False
      # node = 4
      new_node = MakeNode(data) # 3
      before_node = node.prev # 2
      before_node.next = new_node
      new_node.prev = before_node
      new_node.next = node
      node.prev = new_node

      return True


node1 = Node(1)
node1.insert(2)
node1.insert(4)
node1.insert(5)

node1.insert_before(3,4)

node1.output()