이중 연결 리스트

컴퓨터 과학에서 이중 연결 리스트, 이중 링크드 리스트 또는 더블리 링크드 리스트(Doubly linked list)는 순차적으로 연결된 레코드들의 집합으로 구성된 연결 자료 구조이며, 이 레코드는 노드라고 불린다. 각 노드는 세 가지 필드를 포함한다: 두 개의 링크 필드 (참조하는 이전 노드와 다음 노드에 대한 참조)와 하나의 데이터 필드. 시작 노드와 끝 노드의 이전 및 다음 링크는 각각 어떤 종류의 종결자(일반적으로 센티널 노드 또는 널)를 가리켜 리스트 탐색을 용이하게 한다. 센티널 노드가 하나뿐인 경우 리스트는 센티널 노드를 통해 원형으로 연결된다. 이는 동일한 데이터 항목으로 구성되었지만 순서가 반대인 두 개의 단일 연결 리스트로 개념화될 수 있다.


두 노드 링크를 통해 리스트를 양방향으로 탐색할 수 있다. 이중 연결 리스트에서 노드를 추가하거나 제거하는 것은 단일 연결 리스트에서 동일한 작업을 수행하는 것보다 더 많은 링크를 변경해야 하지만, 작업은 더 간단하고 (첫 번째 노드를 제외한 노드의 경우) 잠재적으로 더 효율적이다. 탐색 중에 이전 노드를 추적할 필요가 없거나 이전 노드를 찾기 위해 리스트를 탐색할 필요가 없어 링크를 수정할 수 있기 때문이다.

명명법 및 구현
실질적인 모든 응용 프로그램에서 이중 연결 리스트의 첫 번째 및 마지막 노드는 즉시 접근 가능하며 (즉, 탐색 없이 접근 가능하며 일반적으로 헤드 및 테일이라고 불림) 따라서 리스트의 시작 또는 끝에서 각각 리스트를 탐색할 수 있다. 예를 들어, 특정 데이터 값을 가진 노드를 찾기 위해 리스트를 처음부터 끝까지 또는 끝에서 처음까지 탐색할 수 있다. 일단 얻은 이중 연결 리스트의 어떤 노드도 주어진 노드에서 양방향(시작 또는 끝 방향)으로 리스트의 새로운 탐색을 시작하는 데 사용될 수 있다.

이중 연결 리스트 노드의 링크 필드는 종종 다음 및 이전 또는 앞 및 뒤라고 불린다. 링크 필드에 저장된 참조는 일반적으로 포인터로 구현되지만 (모든 연결된 데이터 구조에서와 같이) 노드가 존재하는 배열의 주소 오프셋 또는 인덱스일 수도 있다.

기본 알고리즘
아래 Ada로 작성된 기본 알고리즘을 살펴보자:

개방형 이중 연결 리스트
 record DoublyLinkedNode {
     next // 다음 노드에 대한 참조
     prev // 이전 노드에 대한 참조
     data // 데이터 또는 데이터에 대한 참조
 }

 record DoublyLinkedList {
      DoublyLinkedNode firstNode   // 리스트의 첫 번째 노드를 가리킴
      DoublyLinkedNode lastNode    // 리스트의 마지막 노드를 가리킴
 }

리스트 탐색
이중 연결 리스트의 탐색은 양방향으로 가능하다. 사실, 원하는 경우 탐색 방향을 여러 번 변경할 수 있다. 탐색은 종종 반복이라고 불리지만, 그 용어 선택은 불행하다. 왜냐하면 반복은 (예를 들어 수학에서) 탐색과 유사하지 않은 잘 정의된 의미론을 가지고 있기 때문이다.

앞으로
 node  := list.firstNode
 while node ≠ null
     <node.data로 뭔가 함>
     node  := node.next

뒤로
 node  := list.lastNode
 while node ≠ null
     <node.data로 뭔가 함>
     node  := node.prev

노드 삽입
다음 대칭 함수는 주어진 노드 뒤 또는 앞에 노드를 삽입한다:

 function insertAfter(List list, Node node, Node newNode)
     newNode.prev  := node
     if node.next == null
         newNode.next  := null -- (항상 필요한 것은 아님)
         list.lastNode  := newNode
     else
         newNode.next  := node.next
         node.next.prev  := newNode
     node.next  := newNode

 function insertBefore(List list, Node node, Node newNode)
     newNode.next  := node
     if node.prev == null
         newNode.prev  := null -- (항상 필요한 것은 아님)
         list.firstNode  := newNode
     else
         newNode.prev  := node.prev
         node.prev.next  := newNode
     node.prev  := newNode

또한 비어 있을 수 있는 리스트의 시작 부분에 노드를 삽입하는 함수가 필요하다:

 function insertBeginning(List list, Node newNode)
     if list.firstNode == null
         list.firstNode  := newNode
         list.lastNode   := newNode
         newNode.prev  := null
         newNode.next  := null
     else
         insertBefore(list, list.firstNode, newNode)

대칭 함수는 끝에 삽입한다:

 function insertEnd(List list, Node newNode)
      if list.lastNode == null
          insertBeginning(list, newNode)
      else
          insertAfter(list, list.lastNode, newNode)

노드 제거
노드 제거는 삽입보다 쉽지만, 제거할 노드가 firstNode 또는 lastNode인 경우 특별한 처리가 필요하다:

 function remove(List list, Node node)
     if node.prev == null
         list.firstNode  := node.next
     else
         node.prev.next  := node.next
     if node.next == null
         list.lastNode  := node.prev
     else
         node.next.prev  := node.prev

위 절차의 미묘한 결과 중 하나는 리스트의 마지막 노드를 삭제하면 firstNode와 lastNode가 모두 null로 설정되므로, 한 요소 리스트에서 마지막 노드를 제거하는 것을 올바르게 처리한다는 것이다. 또한 "removeBefore" 또는 "removeAfter" 메서드가 별도로 필요하지 않다는 점에 유의하라. 이중 연결 리스트에서는 "remove(node.prev)" 또는 "remove(node.next)"를 사용할 수 있기 때문이다. 이는 또한 제거되는 노드가 존재한다고 가정한다. 노드가 이 리스트에 존재하지 않으면 오류 처리가 필요할 것이다.

원형 이중 연결 리스트

리스트 탐색
someNode가 비어 있지 않은 리스트의 노드라고 가정하면, 이 코드는 someNode(어떤 노드든 상관없음)에서 시작하여 해당 리스트를 탐색한다:

앞으로
 node  := someNode
 do
     node.value로 뭔가 함
     node  := node.next
 while node ≠ someNode

뒤로
 node  := someNode
 do
     node.value로 뭔가 함
     node  := node.prev
 while node ≠ someNode

테스트가 루프 끝으로 연기된다는 점에 유의하라. 이는 리스트가 단일 노드 someNode만 포함하는 경우에 중요하다.

노드 삽입
이 간단한 함수는 주어진 요소 뒤에 노드를 이중 연결 원형 연결 리스트에 삽입한다:

 function insertAfter(Node node, Node newNode)
     newNode.next  := node.next
     newNode.prev  := node
     node.next.prev  := newNode
     node.next       := newNode

"insertBefore"를 하려면 단순히 "insertAfter(node.prev, newNode)"를 사용할 수 있다.

비어 있을 수 있는 리스트에 요소를 삽입하려면 특별한 함수가 필요하다:

 function insertEnd(List list, Node node)
     if list.lastNode == null
         node.prev := node
         node.next := node
     else
         insertAfter(list.lastNode, node)
     list.lastNode := node

시작에 삽입하려면 단순히 "insertAfter(list.lastNode, node)"를 사용한다.

마지막으로, 노드 제거는 리스트가 비어 있는 경우를 처리해야 한다:

 function remove(List list, Node node);
     if node.next == node
         list.lastNode := null
     else
         node.next.prev := node.prev
         node.prev.next := node.next
         if node == list.lastNode
             list.lastNode := node.prev;
     destroy node

노드 삭제
이중 연결 리스트와 마찬가지로 "removeAfter"와 "removeBefore"는 "remove(list, node.prev)"와 "remove(list, node.next)"로 구현할 수 있다.

고급 개념

비대칭 이중 연결 리스트
비대칭 이중 연결 리스트는 단일 연결 리스트와 일반 이중 연결 리스트의 중간에 있다. 단일 연결 리스트의 일부 기능(단방향 탐색)과 이중 연결 리스트의 다른 기능(수정 용이성)을 공유한다.

이것은 각 노드의 이전 링크가 이전 노드를 가리키는 것이 아니라 그 자체에 대한 링크를 가리키는 리스트이다. 이것은 노드들 사이에서 큰 차이를 만들지 않지만 (이전 노드 내의 오프셋을 가리킬 뿐임), 리스트의 헤드를 변경한다: 첫 번째 노드가 firstNode 링크를 쉽게 수정할 수 있게 한다.

노드가 리스트에 있는 한, 이전 링크는 결코 null이 아니다.

노드 삽입
다른 노드 앞에 노드를 삽입하려면, 이전 링크를 사용하여 이전 노드를 가리키던 링크를 변경한다. 그런 다음 새 노드의 다음 링크가 이전 노드를 가리키도록 설정하고, 해당 노드의 이전 링크를 그에 따라 변경한다.

 function insertBefore(Node node, Node newNode)
     if node.prev == null
         error "노드가 리스트에 없습니다"
     newNode.prev  := node.prev
     atAddress(newNode.prev)  := newNode
     newNode.next  := node
     node.prev = addressOf(newNode.next)

 function insertAfter(Node node, Node newNode)
     newNode.next  := node.next
     if newNode.next != null
         newNode.next.prev = addressOf(newNode.next)
     node.next  := newNode
     newNode.prev  := addressOf(node.next)

노드 삭제
노드를 제거하려면, 노드가 리스트의 첫 번째 노드였는지 여부에 관계없이 이전이 가리키는 링크를 단순히 수정한다.

 function remove(Node node)
     atAddress(node.prev)  := node.next
     if node.next != null
         node.next.prev = node.prev
     destroy node

 같이 보기 
 XOR 연결 리스트
 SLIP (프로그래밍 언어)

 각주 

분류:연결 리스트