더블 링크드 리스트

이동근·2021년 5월 1일

자료구조

목록 보기

3/9

더블 링크드 리스트

싱글 링크드 리스트는 한 개의 데이터와 링크를 걸고자 하는 포인터로 이루어진 노드의 연결로 만들어진 리스트 이다.

더블 링크드 리스트는 여기에 prev라는 이전을 연결하는 포인터가 한 개 더 생긴 것을 의미한다.

이런식으로 데이터, Prev, Next 가 한개의 노드를 구성하고 있다.

노드, 링크드 리스트 만들어 주기

이 부분은 싱글 링크드 리스트와 별 차이가 없다.

다만 노드를 만들어 줄때

class Node:
   def __init__(self, data):
      self.data = data
      self.next = None
      self.prev = None   # 이 부분이 추가 되었다.

이전의 노드를 가리키는 포인터인 prev가 추가가 되었다.

더블 링크드 리스트의 접근과 탐색

싱글 리스트와 별 차이가 없다. 똑같다.

더블 링크드 리스트의 추가(append)연산

더블 링크드 리스트의 추가연산시
경우1. 링크드 리스트가 비어있을때
경우2. 아닐때
로 구분 지어서 하면 된다.

def append(self, data):
   new_node = Node(data)
   
   # 링크드 리스트가 비어 있을때
   if self.head is None:
      self.head = new_node
      self.tail = new_node
   # 링크드 리스트의 맨 끝에 추가 할때
   else:
     self.tail.next = new_node
     new.node.prev = self.tail   # new_node의 prev를 설정해주는 부분이 생겼다.
     self.tail = new_node

더블 링크드 리스트의 삽입(insert)연산

삽입 연산시
경우1 tail노드 뒤에 추가 할 경우 (추가 연산과 똑같다.)
경우2 두 노드 사이에 삽입할때

def insert_after(self, previous_node, data):
   new_node = Node(data)
   # tail노드 뒤에 삽입 할 경우
   if previous_node is self.tail:
      self.tail.next = new_node
      new_node.prev = self.tail
      self.tail = new_node
   # 두 노드 사이에 삽입할때 (약간 복잡하다.)
   else:
      previous_node.next.prev = new_node # 기존에 있던 previous_node의 다음 노드의 prev를 new 노드로 설정
      new_node.next = previous_node.next # new_node의 next를 기존의 previous_node의 다음으로 설정
      new_node.prev = previous_node      # 삽입하는 new_node의 prev를 previous노드로 설정
      previous_node.next = new_node      # previous_node의 next를 new_node로 설정

맨 앞에 삽입하기

더블 링크드 리스트 역시도 맨 앞에는 그냥 삽입이 안된다.
그래서 리스트가 비어있는 경우와 아닌 경우를 따져 줘야 된다.

def prepand(self, data):
   new_node = Node(data)
   if self.head is None:
      self.head = new_node
      self.tail = new_node
   else:
      new_node.next = self.head
      self.head.prev = new_node
      self.head = new_node

추가 연산 하는 것처럼 해주면 된다. 어렵지 않다.

삭제연산

싱글 링크드 리스트와 다르게 이전의 노드를 가리키는 포인터가 추가 됨에 따라 삭제하고 싶은 노드 그 자체를 받으면 된다.
조건
경우1 지우려는 노드가 마지막으로 남은 경우
경우2 head 노드를 지우는 경우, 마지막 노드 X
경우3 tail 노드를 지우는 경우, 마지막 노드 X
경우4 노드 사이에 삽입하는 경우

이 4자리를 생각 하면 된다.
함수의 이름은 delete 이고 삭제하고자하는 노드는 node to delete 이다.

def delete(self, node_to_data):
   # 경우 1
   if self.head is self.tail:
      self.head = None
      self.tail = None
   # 경우2
   elif node_to_delete is self.head:
      node_to_delete.next.prev = None
      self.head = node_to_delete.next
   # 경우3
   elif node_to_delete is self.tail:
      node_to_delete.prev.next = None
      self.tail = node_to_delete.prev
   # 경우4
   else:
      node_to_delete.prev.next = node_to_delete.next
      node_to_delete.next.prev = node_to_delete.prev