[자료구조] 이중 연결 리스트(Doubly Linked List)의 삭제연산과 소멸연산

이중 연결 리스트의 연산

단순 연결 리스트와 크게 다를 것이 없으니 단순 연결 리스트를 충분히 이해했다면 쉽게 이해할 수 있다.

아래 글을 통해 확인하고 오는 것도 좋을 것이다.

https://zldn.tistory.com/4

[자료구조] 단순 연결 리스트(LinkedList)의 삭제연산

 

이중 연결 리스트의 삭제연산

 

이중 연결 리스트의 삭제연산을 하기 위해서는 삭제하려는 노드의 양쪽 포인터 2개와 이전 노드의 rightLink 포인터와 다음 노드의 leftLink 포인터를 다뤄야한다.

 

이중 연결 리스트에서 노드를 삭제하는 방법은 다음과 같다.

1. 삭제할 노드의 오른쪽 노드의 주소를 삭제할 노드의 왼쪽 노드의 오른쪽 링크 필드에 저장한다.

2. 삭제할 노드의 왼쪽 노드의 주소를 삭제할 노드의 오른쪽 노드의 왼쪽 링크 필드에 저장한다.

3. 노드를 순서대로 연결한다.

 

다음 이중 연결 리스트에서 포인터 remove가 가리키는 노드를 삭제하는 과정을 예로 들어보자.

이중 연결 리스트의 삭제 예시

 

 

1. remove 노드의 왼쪽 노드의 rightLink에 remove 노드의 다음 노드의 주소값을 저장한다.

1. remove 노드의 이전 노드가 remove 노드 다음 노드를 가리키도록 한다.

 

 

2. remove 노드 다음 노드의 leftLink에 remove 노드 이전 노드의 주소값을 저장한다.

2. remove 노드 다음노드 앞에 remove노드 이전노드가 연결되도록 한다.

 

 

코드로 표현해 보자.

void deleteNode(Node** Head, Node* remove) {
    if (*Head == NULL) return;
    else if (remove == NULL) return;
    else {
        remove->leftLink->rightLink = remove->rightLink;
        remove->rightLink->leftLink = remove->leftLink;
        free(remove);
    }
}

 

2  // Head 노드가 비어있다면, 즉 공백리스트라면 삭제할 노드도 없으니 연산을 중단한다.

3  // remove 노드가 비어있다면 연산을 중단한다.

4  // 그렇지않다면

5  // remove 노드의 왼쪽 노드(remove->leftLink)의 오른쪽 링크 필드(->rightLink)에 remove 노드의 오른쪽 링크 필드값(remove->rightLink)을 저장한다.

6  // remove 노드의 오른쪽 노드(remove->rightLink)의 왼쪽 링크 필드(->leftLink)에 remove 노드의 왼쪽 링크 필드값(remove->leftLink)을 저장한다.4-

7  // 삭제할 remove 노드의 메모리를 해제한다.

 

이중 연결 리스트의 소멸연산

이중 연결 리스트의 소멸연산은 단순 연결 리스트의 소멸연산과 완전히 동일하다.

free()함수를 호출하는 것 뿐이니 당연하다.

void destoryNode(Node* node) {
    free(node);
}