패스트 캠퍼스 챌린지 7일차 - 자료구조 연결 리스트(Linked List)#4

목차

1. 더블 링크드 리스트
2. 간단한 구현

1.더블 링크드 리스트

• 노드 갯수가 10000개라고 가정하고 찾고자 하는 노드가 대략 9000번째에 있다면 검색하는데 너무 많은 시간이 든다.
• 이때 뒤에서 부터 검색을 할수 있다면 앞에서 부터 찾는것 보다 9배는 빠르게 찾을수 있다.
• 뒤에 오는 노드 뿐만 아니라 앞에있는 노드를 기억하는 List를 Double Linked List라 한다.

출처: wikipedia, https://en.wikipedia.org/wiki/Linked_list

---

2.간단한 구현

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

#DoubleLinkedList
class DoubleLinkedList:
  def __init__(self,data):
    self.head=Node(data)
    self.tail=self.head

  def insert_before(self,data,before_data):
    if self.head==None:
      self.head=Node(data)
      return True 
    else:
      node=self.tail
      while node.data!=before_data:
        node=node.prev
        if node==None:
          return False
      print("find: ",node.data)
      new=Node(data)
      before_new=node.prev
      before_new.next=new
      new.next=node
      return True
    
  def insert_after(self,data,after_data):
    if self.head==None:
      self.head=Node(data)
      return True
    else:
      node=self.head
      while node.data!=after_data:
        node=node.next
        if node==None:
          return False
      new=Node(data)
      after_new=node.next
      new.next=after_new
      new.prev = node
      node.next = new
      if new.next == None:
        self.tail = new
      return True
        
  def insert(self, data):
    if self.head == None:
      self.head = Node(data)
    else:
      node = self.head
      while node.next:
        node = node.next
      new = Node(data)
      node.next = new
      new.prev = node
      self.tail = new

  def desc(self):
    node = self.head
    while node:
      print (node.data)
      node = node.next
#------------------------------------------------------------------------------

double=DoubleLinkedList(0)
#추가
for data in range(1,10):
  double.insert(data)
double.desc()
#타겟 노드 뒤에 넣기
double.insert_after(1.5,1)
print("")
double.desc()
print("")
#타겟 노드 앞에 넣기
double.insert_before(1.3,1)
print("")
double.desc()

https://bit.ly/37BpXiC