이중 연결 리스트(Doubly Linked List) - C언어 구현

이중 연결 리스트: 단일 연결 리스트의 탐색 기능을 개선한 자료구조

• 앞 노드를 가리키는 포인터 추가 -> 양방향 탐색 가능
  
  

0. 노드 구조체

typedef struct Node {
    int data;
    struct Node* prevNode;
    struct Node* nextNode;
} Node;

1. 노드 생성

Node* CreateNode(int data) {
    Node* newNode = (Node*)malloc(sizeof(Node));
    newNode->data = data;
    newNode->prevNode = NULL;
    newNode->nextNode = NULL;
    return newNode;
}

2. 노드 추가

void AppendNode(Node** head, Node* newNode) {
    if(*head == NULL) *head = newNode;
    else {
        Node* tail = *head;
        while(tail->nextNode != NULL) tail = tail->nextNode;
        tail->nextNode = newNode;
        newNode->prevNode = tail;
    }
}

3. 노드 검색

Node* SearchNode(Node* current, int data) {
    if(current == NULL) return NULL;
    while(current != NULL) {
        if(current->data == data) return current;
        current = current->nextNode;
    }
    return NULL;
}

4. 노드 삭제

Node* RemoveNode(Node** head, int data) {
    Node* target = SearchNode(*head, data);
    if(target != NULL) {
	if(*head == target) {
	    *head = target->nextNode;
	    if(*head != NULL) (*head)->prevNode = NULL;
	}
        else {
	    if(target->nextNode != NULL) target->nextNode->prevNode = target->prevNode;
	    target->prevNode->nextNode = target->nextNode;	
	}
	target->prevNode = NULL;
	target->nextNode = NULL;
    }
    return target;
}

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

5. 리스트 출력

void PrintList(Node* current) {
    if(current == NULL) printf("빈 리스트\n");
    else {
        while(current != NULL) {
            printf("[%p] %p %d %p\n", current, current->prevNode, current->data, current->nextNode);
            current = current->nextNode;
        }
    }
}

6. 리스트 삭제

void DestroyList(Node* current) {
    Node* remove = current;
    while(remove != NULL) {
        current = current->nextNode;
        free(remove);
        remove = current;
    }
}

7. 예시

int main(void)
{
    Node* head = NULL;
    Node* newNode = NULL;

    newNode = CreateNode(10);
    AppendNode(&head, newNode);
    newNode = CreateNode(20);
    AppendNode(&head, newNode);
    newNode = CreateNode(30);
    AppendNode(&head, newNode);
    PrintList(head);

    DestroyNode(RemoveNode(&head, 30));
    PrintList(head);
    DestroyNode(RemoveNode(&head, 10));
    PrintList(head);
    DestroyNode(RemoveNode(&head, 20));
    PrintList(head);

    newNode = CreateNode(30);
    AppendNode(&head, newNode);
    DestroyNode(head);
    return 0;
}