[자료구조] Doubly Linked List의 삭제

 

이중 연결 리스트는 각 노드가 이전 노드와 다음 노드를 가리키는 포인터를 가지고 있어서, 양방향으로 탐색이 가능하며, 삭제 시 양쪽의 연결을 수정해야 한다. Doublely Linked List에서 노드의 삭제는 다음과 같은 순서로 이루어진다.

 

1) 삭제할 노드의 오른쪽 노드와 왼쪽 노드를 탐색한다.

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

3) 삭제할 노드의 왼쪽 노드 주소를 삭제할 노드의 오른쪽 노드의 llink에 저장한다. 

4) 삭제할 노드를 삭제한다.

 

 

[코드로 구현하기]

#include <stdio.h>
#include <stdlib.h>

// 이중 연결 리스트의 노드 구조체 정의
struct Node {
    int data;
    struct Node* llink; // 왼쪽 노드를 가리키는 포인터
    struct Node* rlink; // 오른쪽 노드를 가리키는 포인터
};

// 이중 연결 리스트 관리를 위한 구조체 정의
struct DoublyLinkedList {
    struct Node* head;
};

// 노드 삭제 함수 정의
void deleteNode(struct DoublyLinkedList* list, struct Node* target) {
    // 예외 처리: 빈 리스트이거나 삭제할 노드가 없을 경우
    if (!list->head || !target)
        return;

    // 삭제할 노드의 오른쪽 노드를 삭제할 노드의 왼쪽 노드의 rlink에 저장
    if (target->llink)
        target->llink->rlink = target->rlink;

    // 삭제할 노드의 왼쪽 노드를 삭제할 노드의 오른쪽 노드의 llink에 저장
    if (target->rlink)
        target->rlink->llink = target->llink;

    // 노드를 삭제하고 메모리에서 해제
    free(target);
}

int main() {
    // 이중 연결 리스트 생성
    struct DoublyLinkedList myList;
    myList.head = NULL;

    // 리스트에 노드 추가 (생략)

    // 삭제할 노드를 어떻게 찾든지 한다고 가정
    struct Node* nodeToDelete = /*...*/;

    // 노드 삭제
    deleteNode(&myList, nodeToDelete);

    return 0;
}