이중 연계 리스트
Doubly linked list |
컴퓨터 과학에서 이중 연계 목록은 노드라고 불리는 순차적으로 연결된 기록들의 집합으로 구성된 연계된 데이터 구조다.각 노드에는 2개의 링크 필드(노드 순서에서 이전 노드와 다음 노드에 대한 참조)와 1개의 데이터 필드가 있다.시작 노드와 종료 노드의 이전 및 다음 링크는 각각 목록의 통과를 용이하게 하기 위해 일반적으로 송신 노드 또는 null인 어떤 종류의 터미네이터를 가리킨다.Sentinel 노드가 하나만 있는 경우, 목록은 Sentinel 노드를 통해 순환적으로 연결된다.동일한 데이터 항목에서 두 개의 단일 연결 리스트가 생성되지만, 정반대 순차적인 순서로 개념화할 수 있다.
두 노드 링크는 어느 방향으로든 목록을 통과시킬 수 있다.이중으로 연결된 목록에서 노드를 추가하거나 제거하려면 단일 링크 목록의 동일한 작업보다 더 많은 링크를 변경해야 하지만, 트래버설 중에 이전 노드를 추적할 필요가 없거나 검색하기 위해 목록을 이동할 필요가 없기 때문에 작업은 더 간단하고 잠재적으로 더 효율적이다(첫 번째 노드 이외의 노드의 경우).링크를 수정할 수 있도록 이전 노드.
명명 및 구현
이중으로 연결된 목록의 첫 번째 노드와 마지막 노드는 즉시 액세스할 수 있으므로(즉, 통과 없이 액세스할 수 있으며 일반적으로 머리와 꼬리라고 함) 목록 시작 또는 끝에서 끝까지(예: 고개를 끄덕이기 위해 목록을 검색하는 경우) 목록 통과를 허용한다.e 특정 데이터 값.이중으로 연결된 목록의 어떤 노드는 일단 얻으면, 주어진 노드로부터 어느 방향(시작 또는 끝의 방향)으로든 목록의 새로운 횡단을 시작하는 데 사용될 수 있다.
이중으로 연결된 목록 노드의 링크 필드는 종종 다음 및 이전 또는 앞뒤로 호출된다.링크 필드에 저장된 참조는 일반적으로 포인터로 구현되지만 (연결된 데이터 구조에서와 마찬가지로) 노드가 상주하는 배열로 어드레스 오프셋 또는 인덱스가 될 수도 있다.
기본 알고리즘
Ada로 작성된 다음과 같은 기본 알고리즘을 고려하십시오.
이중으로 연결된 목록 열기
DoublyLinkedNode {다음 // 다음 노드에 대한 참조 // 이전 노드 데이터에 대한 참조 // 이전 노드 데이터에 대한 참조 또는 데이터 참조 } 기록 DoublyLinkedList {DoublyLinkedNode 1차 노드 // 목록의 첫 번째 노드를 가리키며 //는 목록의 마지막 노드를 가리킴} 목록 통과
이중으로 연결된 목록의 통과는 어느 방향으로든 가능하다.사실, 통과 방향은 원한다면 여러 번 바뀔 수 있다.트래버설(Traversal)은 종종 반복이라고 불리지만, 그러한 용어의 선택은 불행하다. 왜냐하면, 반복은 트래버설과 유사하지 않은 의미론(예를 들어 수학에서)이 잘 정의되어 있기 때문이다.
앞으로
노드 := list.node가 null인 동안 firstNode(node.data) 노드 :=node.next.
거꾸로
node := list.lastNode, node ≠ null <node.data> 노드 := node.prev
노드 삽입
이러한 대칭 함수는 지정된 노드 뒤에 또는 앞에 노드를 삽입한다.
insertAfter(list list, Node node node, Node node newNode) newNode.prev := next=next :=null -- (항상 필요한 것은 아님) list.lastNode := newnode.next.next.prev :=newNode.next.next :=next.next :=next.next :=next.next :=node new new new node.node.next :=next.node
함수 insertBefore(목록, 노드 노드 노드, 노드 newNode) newNode.next :=node if null.prev == null newNode := null -- (항상 필요한 것은 아님) 목록firstNode := newNode other newNode.prev :=node.prev node.prev.next :=newNode.prev :=newNode.prev :=newNode
우리는 또한 빈 리스트의 시작 부분에 노드를 삽입하는 기능이 필요하다.
insertBeginning(list list, Node newNode) 함수(list) if list.firstNode == null list.firstNode := newNode list.lastNode :=newNode newNode.prev :=null newNode.next :=null nother insertBefore(list, list)firstNode, newNode)
대칭 함수는 끝에 삽입:
insertEnd(list list, Node newNode) 함수 if list.lastNode == null insertBeginning(list, newNode) 또는 insertAfter(list, list.lastNode, newNode)
노드 제거
노드 제거는 삽입보다 쉽지만 제거할 노드가 firstNode 또는 lastNode인 경우 특별한 처리가 필요하다.
node.prev == null list인 경우 함수 제거(List list, Node node)firstNode :=node.next.prev.next.next:=node.next:=null list.lastNode :=node.prev next.next.prev :=node.prev.prev.prev.frev.frev
위의 절차의 한 가지 미묘한 결과는 목록의 마지막 노드를 삭제하면 firstNode와 lastNode가 모두 null로 설정되므로, 단일 요소 목록에서 마지막 노드를 제거하는 작업을 올바르게 처리한다는 것이다.이중으로 연결된 목록에서 "removeBefore"(node.prev) 또는 "remove(node.node.node.next)"가 유효한 "remove(node.node.node.next)"를 사용하면 되기 때문에 별도의 "removeBefore" 또는 "remove next"(node.node.node.next) 메서드도 필요하지 않다.이는 또한 제거되는 노드가 존재한다고 가정한다.노드가 이 목록에 없으면 일부 오류 처리가 필요할 것이다.
이중으로 연결된 순환 목록
목록 통과
someNode가 비어 있지 않은 목록의 일부 노드라고 가정하면, 이 코드는 someNode(모든 노드가 할 수 있음
앞으로
노드 := someNode는 node.value node :=node.node.node.node.next를 사용하여 작업을 수행함
거꾸로
노드 :=일부 노드에서는 node.value 노드 :=node.prev로 작업을 수행하지만 노드 에서는 일부 노드.prev로 작업을 수행함
시험이 끝날 때까지 연기되는 것을 주목하라.이것은 목록에 단일 노드 someNode만 포함된 경우에 중요하다.
노드 삽입
이 간단한 기능은 지정된 요소 뒤에 두 배로 연결된 순환 링크 목록에 노드를 삽입한다.
함수 insertAfter(노드 노드, node newNode) newNode.next :=next.next node.prev :=next.prev :=newNode.next :=next :=newNode
"InsertBefore"를 실행하기 위해 간단히 "insertAfter(node.prev, newNode)"를 수행하면 된다.
빈 목록에 요소를 삽입하려면 다음과 같은 특수 기능이 필요하다.
list.lastNode == null node.prev :=node.next := node other node others insertAfter(list.lastNode, 노드) list.lastNode := node
처음에 삽입하려면 "insertAfter(list.lastNode, node)"만 사용하십시오.
마지막으로, 노드 제거는 목록이 비어 있는 경우를 처리해야 한다.
함수 제거(List, Node node); next.next ==node list.lastNode :=null node.next.prev :=node.prev.next :=node==list.lastNode list.lastNode; deletev.
노드 삭제
이중으로 연결된 리스트에서처럼 "removeAfter"와 "removeBefore"는 "remove"(list, node.prev)와 "remove(list, node.next)"로 구현할 수 있다.
고급 개념
비대칭 이중 연계 리스트
비대칭 이중 연계 리스트는 단일 연계 리스트와 일반 이중 연계 리스트 사이에 있다.단일 연결 목록(단방향 통과)과 일부 기능을 공유하고 이중 연결 목록의 다른 기능(수정)을 공유한다.
각 노드의 이전 링크가 이전 노드가 아닌 자체로 연결되는 링크를 가리키는 목록이다.이렇게 하면 노드 간에 차이가 거의 없지만(이전 노드 내의 오프셋만 가리킬 뿐), 목록 헤드는 다음과 같이 변경된다.그것은 첫 번째 노드가 첫 번째 노드 링크를 쉽게 수정할 수 있도록 한다.[1][2]
노드가 목록에 있는 한 이전 링크는 절대 null이 아니다.
노드 삽입
노드를 다른 노드에 삽입하려면 이전 링크를 사용하여 이전 노드를 가리키는 링크를 변경한 후 새 노드의 다음 링크를 이전 노드를 가리키도록 설정하고 그에 따라 해당 노드의 이전 링크를 변경하십시오.
node.prev == null 오류인 경우 insertBefore(노드 노드, 노드 newNode) 함수 "node가 목록에 없음" newNode.prev := node.prev atAdddress(newNode.prev) :=node.prev = addressOf(ndress.next).
insertAfter(노드 노드, 노드 newNode) newNode.next :=next.next if newNode.next!=null newNode.next.prev = addressOf(newNode.next) 노드.next : newNode.prev := addressOf(next).
노드 삭제
노드를 제거하기 위해서는 노드가 목록의 첫 번째 노드인지 여부에 관계없이 사전이 가리키는 링크를 수정하기만 하면 된다.
함수 제거(노드 노드) atAddress(node.prev) :=next.next인 경우 node.next!=null node.next.prev = node.prev 제거 노드
