자료구조 - 이중 연결 리스트(Doubly Linked List)

1. 이중 연결 리스트(Doubly Linked List)란

앞서 단일 연결 리스트(Singly Linked List)에 대해 알아보았다.

 

2026.06.01 - [python] - 자료구조- 단일 링크드 리스트 (Singly Linked List)

 

이번 글에서는 이중 연결 리스트에 대해서 알아보자.

 

 

단일 연결리스트는 다음 노드의 주소 정보만 저장했던 반면, 이중 연결 리스트는 이전 노드와 다음 노드의 주소 정보를 모두 저장하는 자료구조이다.

---

2. 이중 연결 리스트(Doubly Linked List)의 장/단점

2.1 장점

1️⃣ 실행 중 메모리 할당과 재할당이 비교적 쉽다.

이중 연결 리스트는 실행 중에 노드를 추가하거나 삭제할 수 있다. 그래서 배열처럼 미리 크기를 정해둘 필요가 없다.

2️⃣ 양방향 순회가 가능하다

이중 연결 리스트는 prev와 next 포인터를 모두 가지고 있어, 앞뒤로 이동할 수 있다. 따라서 단일 연결리스트에서는 불가능했던 역방향 순회도 가능핟

3️⃣ 다른 자료구조에 비해 오버헤드가 비교적 적다

배열처럼 크기를 미리 크게 잡아 둘 필요가 없고, 필요한 노드만 메모리를 사용하기 때문에 상황에 따라 메모리를 효율적으로 사용할 수 있다.

---

2.2 단점

1️⃣ 임의 접근 불가

모든 요소들이 비연속적으로 메모리에 저장되기 때문에 요소들은 순차적으로만 접근 가능하고 임의 접근이 허용되지 않는다.

2️⃣ 추가 메모리 사용량

이중 연결리스트는 배열이나 단일 연결리스트에 비해 추가적인 메모리를 더 사용한다.
단일 연결 리스트는 다음 노드를 가리키는 포이터 (next) 하나만 저장하지만, 이중 연결리스트는 이전 노드(prev)와 다음 노드(next)의 주소를 보두 저장해야 하기 때문이다.

---

3. 이중 연결리스트의 실제 활용 예시

네비게이션 시스템

이중 연결 리스트는 이전 경로와 다음 경로를 모두 이동해야 하는 네비게이션 시스템에서 활용될 수 있다.
예를 들어 길 안내 중 이전 경로를 다시 확인하거나, 다음 경로로 이동해야 하는 경우가 있는데, 이 때 이중 연결 리스트 구조가 적합하다.

---

웹 브라우저의 뒤/앞(으)로 가기 기능

웹 브라우저의 뒤로 가기와 앞으로 가기 기능은 이중 연결 리스트의 대표적인 활용 예시라고 볼 수 있다.
그래서 사용자는 버튼 하나로 이전 페이지로 돌아가거나 다시 앞으로 이동할 수 있다.

---

4. 구현

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

class DoublyLinkedList:
  def __init__(self):
    self.head=None

  # ✅ 맨 앞에 노드 추가 
  def insert_at_head(self,data):
    new_node=DNode(data) # 새로 추가할 노드

# head 노드가 비어있으면 new_node를 head로 
    if self.head is None:
      self.head=new_node

      return

    else: # 리스트가 비어있지 않을 때
      self.head.prev=new_node # 현재 head의 이전 노드를 new_node로
      new_node.next=self.head # new_node의 next를 현재 head
      self.head=new_node 
      self.head.prev=None

# ✅ 마지막에 노드 삽입
  def insert_at_tail(self,data):  
    new_node=DNode(data)

# head 노드가 비어있으면 new_node를 head로 
    if self.head is None:
      self.head=new_node
      self.tail=new_node
      return

    else: # 리스트가 비어있지 않으면 

      current=self.head

     # 마지막 노드까지 순회
      while current.next:
        current=current.next


      current.next=new_node # 마지막 노드의 다음 노드를 new_node로
      new_node.prev=current # new_node의 이전 노드를 현재노드로 


  # ✅ 특정 노드 이후에 새로운 노드 추가
      # ㄴ마지막 노드 다음에 노드를 추가하는 것은 하지 않는다는 것을 가정함
  def insert_after_given(self,given,data):
    new_node=DNode(data)

    current=self.head

    # given 과 동일한 data를 가진 노드가 있는 지 순회하면서 찾아본다.
    while current:
      if current.data == given: # given가 current.data 와 동일할 때

          next_node=current.next # next_node = 현재 노드의 다음 노드

          new_node.next=next_node # new_node -> next_node
          new_node.prev=current # current <- new_node 
          current.next=new_node # current -> new_node
          next_node.prev=new_node # new_node <- next_node
          return

      current=current.next 

    print(f'{given}을 데이터로 가진 노드가 현재 없습니다.')


  # 노드 삭제

  # ✅ head 노드 삭제

  def delete_at_head(self):
    if self.head is None:  # 노드가 비어있으면 관련 메세지 출력 
      print('이중 연결 리스트가 비어있습니다')
      return

    if self.head.next is None:   # 노드가 1개인 경우
        self.head = None 
        return

    else: # 노드가 2개 이상일 때

      current=self.head
      self.head = current.next
      self.head.prev=None
      return


  # ✅ 가장 마지막 노드 (tail) 삭제    
  def delete_at_tail(self):

    if self.head is None: # 빈 리스트일때 
      print('이중 연결 리스트가 비어있습니다.')
      return

    if self.head.next is None: # 리스트의 요소가 1개밖에 없을 때 
      self.head= None

      return

    else:
      current=self.head

      # 리스트를 끝까지 순회 
      while current.next:
        current=current.next

      prev_node=current.prev # prev_node = 현재 노드의 이전 노드 
      prev_node.next=None # prev_node -> None 

# ✅ 특정 데이터를 가진 노드를 삭제
  def delete_node(self,given):

    if self.head is None:
      print("이중 연결 리스트가 비어있습니다.")
      return

    else:
      current=self.head 

      while current.next: # 노드를 순회
        if current.data == given : # current의 data 가 given 과 같을 때

          prev_node=current.prev # prev_node : 현재 노드의 이전 노드
          next_node=current.next # next_node : 현재 노드의 다음 노드

          prev_node.next=next_node # prev_node -> next_node
          next_node.prev=prev_node # prev_node <- next_node 
          return

        current=current.next

      print(f'{given}을 데이터로 가진 노드가 현재 없습니다.')

  def traversal(self): # 노드 순회한 것을 보여주기 

    if self.head is None: # 리스트가 비었을 때 비어있다는 메세지 출력
      print('리스트가 비어있습니다')
      return

    else:
      # 노드를 순회하면서 현재 노드의 data를 출력

      current= self.head
      while current:
        print(current.data,end='<->')
        current=current.next
      print("None")

dll=DoublyLinkedList()
dll.insert_at_tail(10)
dll.insert_at_tail(20)
dll.insert_at_tail(30)
dll.insert_at_tail(40)
dll.insert_at_tail(50)
dll.traversal()

dll.insert_after_given(20,100)
dll.traversal()

dll.delete_at_tail()
dll.traversal()

dll.delete_node(30)
dll.traversal()

 

실행 결과