[자료구조] 이중 연결 리스트(Doubly Linked List) 구현

이중 연결 리스트(Doubly Linked List)

---

• 링크드 리스트의 탐색 기능을 개선한 자료구조
• 양방향 탐색이 가능함 (vs 싱글의 단방향)
  • 자신 앞에 있는 노드를 가리키는 포인터를 가짐으로써 양방향 탐색이 가능함
• 구조체

typedef int ElementType;

typedef struct tagNode
{
    ElementType data;             // 저장할 데이터
    struct tagNode* prevNode;     // 앞 노드의 주소와 데이터
    struct tagNode* nextNode;     // 뒤 노드의 주소와 데이터
} Node;

 

더블 링크드 리스트의 주요 연산

• 기존 링크드 리스트의 연산과 동일(명세는 구현방식과 상관없이 동일함)

노드의 생성/소멸 연산

• 노드의 생성

Node* DLL_CreateNode(ElementType newData)
{
    Node* newNode = (Node*)malloc(sizeof(Node));

    newNode->data = newData;      // 저장할 데이터
    newNode->prevNode = NULL;     // 앞 노드의 정보
    newNode->nextNode = NULL;     // 뒤 노드의 정보

    return newNode;
}

• 노드의 소멸

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

 

• 노드 추가 연산
  • SLL과 다르게 새로운 테일의 PrevNode 포인터가 기존 테일 주소를 가리키도록 해야함

void DLL_AppendNode(Node** head, Node* newNode)
{
    // 헤드의 노드가 NULL일 경우 새로운 노드가 헤드가 됨
    if((*head) == NULL) {
        *head = newNode;
    }
    // 헤드의 노드가 NULL이 아닐 경우 테일을 찾아 NewNode를 연결
    else {
        // 테일에 연결
        Node* tail = (*head);

        while(tail->nextNode != NULL) {
            tail = tail->nextNode;
        }

        tail->nextNode = newNode;
        newNode->prevNode = tail;   // 기존의 테일을 새로운 테일의 prevNode가 가리킴
    }
}

* 다음과 같이 사용함

Node* list = NULL;

DLL_AppendNode(&list, DLL_CreateNode(117));
DLL_AppendNode(&list, DLL_CreateNode(119));

• 노드 탐색 연산
  • 기존 SLL과 같은 방식으로 동작

Node* DLL_GetNodeAt(Node* head, int location)
{
    Node* current = head;

    while(current != NULL && (--location) >= 0) {
        current = current->nextNode;
    }

    return current;
}

 

• 노드 삭제 연산
  • 삭제할 노드의 NextNode 포인터가 가리키던 노드를, 이전 노드의 nextNode 포인터가 가리키게 바꿈
  • 삭제할 prevNode 포인터가 가리키던 노드를 다음 노드의 prevNode 포인터가 가리키게 바꿈
  • 삭제할 노드의 nextNode와 PrevNode는 NULL로 깨끗히 초기화

void DLL_RemoveNode(Node** head, Node* remove)
{
    if(*head == removeNode) {
        *head = removeNode->nextNode;

        if((*head) != NULL) {
            (*head)->prevNode = NULL;
        }

        // 삭제할 노드의 가리키고 있는 값 초기화
        removeNode->prevNode = NULL;
        removeNode->nextNode = NULL;
    }
    else {
        Node* temp = removeNode;

        // 삭제할 노드의 prevNode 포인터가 가리키던 노드를 이전 노드의 nextNode 포인터가 가리키게 변경
        if(removeNode->prevNode != NULL) {
            removeNode->prevNode->nextNode = temp->nextNode;
        }

        // 삭제할 노드의 nextNode 포인터가 가리키던 노드를 이전 노드의 nextNode 포인터가 가리키게 변경
        if(removeNode->nextNode != NULL) {
            removeNode->nextNode->prevNode = temp->prevNode;
        }

        // 삭제할 노드의 가리키고 있는 값 초기화
        removeNode->prevNode = NULL;
        removeNode->nextNode = NULL;
    }
}

 

• 노드 삽입 연산
  • 새로운 노드를 삽입할 때 prevNode 포인터로는 이전 노드를 가리키게 하고, nextNode 포인터로는 다음 노드를 가리키게 한다.
  • 이전 노드의 NextNode 포인터와 다음 노드의 PrevNode 포인터는 새 노드를 가리키게 한다.

void DLL_InsertAfter(Node* current, Node* newNode)
{
    newNode->nextNode = current->nextNode;
    newNode->prevNode = current;

    if(current->nextNode != NULL) {
        current->nextNode->prevNode = newNode;
        current->nextNode = newNode;
    }
}

• 노드 개수 세기
  • SLL과 동일

int DLL_GetNodeCount(Node* head)
{
    int count = 0;
    Node* current = head;

    while(current != NULL) {  
        current = current->nextNode;
        count++;
    }

    return count++;
}

더블 링크드 리스트 예제 프로그램

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

typedef int ElementType;

// 노드 구조체 정의

typedef struct tagNode
{
    ElementType data;             // 저장할 데이터
    struct tagNode* prevNode;     // 앞 노드의 주소와 데이터
    struct tagNode* nextNode;     // 뒤 노드의 주소와 데이터
} Node;

// 함수 원형
Node* DLL_CreateNode(ElementType newData);          // 노드 생성
void DLL_DestroyNode(Node* node);                   // 노드 소멸
void DLL_AppendNode(Node** head, Node* newHead);    // 노드 추가
void DLL_InsertAfter(Node* current, Node* newNode); // 노드 삽입
void DLL_InsertNewHead(Node** head, Node* newHead); // 헤드 삽입
void DLL_RemoveNode(Node** head, Node* removeNode);     // 노드 삭제
Node* DLL_GetNodeAt(Node* head, int location);      // 노드 탐색
int DLL_GetNodeCount(Node* head);                   // 노드 개수

int main()
{
    int i = 0;
    int count = 0;
    Node* list = NULL;
    Node* newNode = NULL;
    Node* current = NULL;

    for(i = 0; i < 5; i++) {
        newNode = DLL_CreateNode(i);
        DLL_AppendNode(&list, newNode);
    }

    // 노드 개수 출력
    count = DLL_GetNodeCount(list);

    for(i = 0; i < count; i++) {
        current = DLL_GetNodeAt(list, i);
        printf("List[%d] : %d\n", i, current->data);
    }

    // 리스트의 세 번째 칸 뒤에 노드 삽입
    printf("\nInserting 3000 After [2]\n\n");

    count = DLL_GetNodeCount(list);

    for(i = 0; i < count; i++) {
        current = DLL_GetNodeAt(list, i);
        printf("List[%d] : %d\n", i, current->data);
    }

    // 모든 노드 소멸
    printf("Destroying List\n\n");

    count = DLL_GetNodeCount(list);

    for(i = 0; i < count; i++) {
        current = DLL_GetNodeAt(list, 0);

        if(current != NULL) {
            DLL_RemoveNode(&list, current);
            DLL_DestroyNode(current);
        }
    }

    return 0;
}

// 노드 생성
Node* DLL_CreateNode(ElementType newData)
{
    Node* newNode = (Node*)malloc(sizeof(Node));

    newNode->data = newData;      // 저장할 데이터
    newNode->prevNode = NULL;     // 앞 노드의 정보
    newNode->nextNode = NULL;     // 뒤 노드의 정보

    return newNode;
}

// 노드 소멸
void DLL_DestroyNode(Node* node)
{
    free(node);
}

// 노드 추가
void DLL_AppendNode(Node** head, Node* newNode)
{
    // 헤드의 노드가 NULL일 경우 새로운 노드가 헤드가 됨
    if((*head) == NULL) {
        *head = newNode;
    }
    // 헤드의 노드가 NULL이 아닐 경우 테일을 찾아 NewNode를 연결
    else {
        // 테일에 연결
        Node* tail = (*head);

        while(tail->nextNode != NULL) {
            tail = tail->nextNode;
        }

        tail->nextNode = newNode;
        newNode->prevNode = tail;   // 기존의 테일을 새로운 테일의 prevNode가 가리킴
    }
}

// 노드 탐색
Node* DLL_GetNodeAt(Node* head, int location)
{
    Node* current = head;

    while(current != NULL && (--location) >= 0) {
        current = current->nextNode;
    }

    return current;

}

// 노드Node
void DLL_RemoveNode(Node** head, Node* removeNode)
{
    if(*head == removeNode) {
        *head = removeNode->nextNode;

        if((*head) != NULL) {
            (*head)->prevNode = NULL;
        }

        // 삭제할 노드의 가리키고 있는 값 초기화
        removeNode->prevNode = NULL;
        removeNode->nextNode = NULL;
    }
    else {
        Node* temp = removeNode;

        // 삭제할 노드의 prevNode 포인터가 가리키던 노드를 이전 노드의 nextNode 포인터가 가리키게 변경
        if(removeNode->prevNode != NULL) {
            removeNode->prevNode->nextNode = temp->nextNode;
        }

        // 삭제할 노드의 nextNode 포인터가 가리키던 노드를 이전 노드의 nextNode 포인터가 가리키게 변경
        if(removeNode->nextNode != NULL) {
            removeNode->nextNode->prevNode = temp->prevNode;
        }

        // 삭제할 노드의 가리키고 있는 값 초기화
        removeNode->prevNode = NULL;
        removeNode->nextNode = NULL;
    }
}

// 노드 삽입
void DLL_InsertAfter(Node* current, Node* newNode)
{
    newNode->nextNode = current->nextNode;
    newNode->prevNode = current;

    if(current->nextNode != NULL) {
        current->nextNode->prevNode = newNode;
        current->nextNode = newNode;
    }
}

// 노드 개수
int DLL_GetNodeCount(Node* head)
{
    int count = 0;
    Node* current = head;

    while(current != NULL) {  
        current = current->nextNode;
        count++;
    }

    return count++;
}

참조) 박상현, 『이것이 자료구조+알고리즘이다 with C언어』, 한빛미디어(2022)