더블 링크드 리스트(Double Linked List)개념 및 구현

June 25, 2024

Intro

이 글은 더블 링크드 리스트에 대한 설명과 구현에 대한 정보를 담은 글입니다.

더블 링크드 리스트(Double Linked List)란?

더블 링크드 리스트란 링크드 리스트의 탐색 기능을 개선한 자료구조이다.

단방향으로 노드를 연결한 링크드 리스트와 다르게(일반 링크드 리스트에 대한 정보는 여기를 참고)

더블 링크드 리스트는 일반적인 링크드 리스트와 다르게 양방향으로 탐색이 가능하다.

그 이유는 더블 링크드 리스트가 이전 노드를 가리키는 포인터와 다음 노드를 가리키는 포인터를 모두 가지고 있기 때문이다.

더블 링크드 리스트의 주요 연산은 일반적인 링크드 리스트와 다른 것이 없다. 이전 노드를 처리하기 위한 과정이 추가될 뿐이다.

더블 링크드 리스트의 구현 과정은 아래와 같다.

더블 링크드 리스트 구현 과정

더블 링크드 리스트를 구현하기 위해서는 다음의 연산이 필요하다.

노드 생성(DLL_CreateNode)
노드 소멸(DLL_DestroyNode)
노드 추가(DLL_AppendNode)
노드 탐색(DLL_GetNodeAt)
노드 삭제(DLL_RemoveNode)
노드 삽입(DLL_InsertAfter)
노드 개수 세기(DLL_GetNodeCount)

일단 연산 구현하기에 앞서서 더블 링크드 리스트의 노드 구조는 다음과 같다.

// Node
typedef struct tagNode{
    int data; //숫자 자료형 저장
    struct tagNode* PreNode; //이전 노드를 카리켜서 구조체 포인터로 정의
    struct tagNode* NextNode;//다음 노드를 가리켜서 구조체 포인터로 정의
} Node;

더블 링크드 리스트는 양방향으로 탐색이 이루어지기에 PreNode와 NextNode에 대한 부분이 필요하다.

구조체를 PreNode와 NextNode로 가리키면서 서로 이어지게 하는 것이라 볼 수 있다.

1. 노드 생성(DLL_CreateNode) 연산 구현

// DLL_CreateNode
Node* DLL_CreateNode(int new_data){
    Node* NewNode = (Node*)malloc(sizeof(Node));
    NewNode->data = new_data;
    NewNode->PreNode = NULL;
    NewNode->NextNode = NULL;

    return NewNode;
}

DLL_CreateNode연산은 malloc을 통해서 공간을 할당하고 newdata를 data에, 이전노드와 다음노드를 가리키는 포인터는 NULL로 초기화를 한다.

2. 노드 소멸(DLL_DestroyNode) 연산 구현

// DLL_DestroyNode
void DLL_DestroyNode(Node* Node){
    free(Node);
}

노드 소멸은 free를 통해 메모지 할당 해제를 수행함으로써 실행한다.

3. 노드 추가(DLL_AppendNode) 연산 구현

// DLL_AppendNode
void DLL_AppendNode(Node** Head, Node* NewNode){
    if ((*Head) == NULL){ //Head가 가리키는 게 없으면 NewNode = Head
        (*Head) = NewNode;
    }
    else{ // Head가 있으면
        Node* Current = (*Head); //Current에 Head가 가리키는 주소 할당
        while(Current->NextNode != NULL){ //Current의 다음 노드가 NULL이 아닐때까지
            Current = Current->NextNode; //Current는 Current의 다음노드 지시
        }
        Current->NextNode = NewNode; //반복 완료하면 Current의 다음노드에 NewNode 담기
        NewNode->PreNode = Current; //NewNode의 이전 노드에 Current 할당(이중연결이라서)
    }
}

DLL_AppendNode는 노드를 기존의 리스트 끝(Tail) 바로 다음에 연결하는 연산을 수행한다.

리스트의 시작(Head)에 아무것도 없을 때는 추가하려는 노드가 Head가 되고,

기존에 추가된 노드가 있을 경우에는 반복을 통해 Tail에 도달해서 Tail의 NextNode에 추가할 노드를 연결하는 방식이다. 그리고 여기서 중요한 것은 추가한 노드의 PreNode에 기존의 Tail 노드(위 코드 상에선 Current)를 연결해야 한다는 것이다.

4. 노드 탐색(DLL_GetNodeAt) 연산 구현

//DLL_GetNodeAt
Node* DLL_GetNodeAt(Node* Head, int Location){
    
    Node* Current = Head; //Current에 Head 주소 할당
    while(Current != NULL && Location > 0){ //Current가 NULL이 아닐때까지 && Location이 0 이하인 동안 반복
        Current = Current->NextNode; //Current는 Current의 다음노드로 이동
        Location--; //Location에서 1씩 감소
    }
    return Current;
}

DLL_GetNodeAt 연산은 노드가 전체 리스트에서 몇 번째에 위치하는지 알아내는 기능을 수행한다. 0부터 셈을 시작하며 Location에 수를 입력하면 그 입력한 n번째 위치의 노드를 반환한다.

Current에 Head의 주소를 할당하고, Current가 NULL이 아닐 때까지, 그리고 Location이 0보다 클 때까지 반복을 수행한다. 결국 Location이 0이 되면 그만큼 다음 노드로 이동한 Current를 반환하는 것이다.

5. 노드 삭제(DLL_RemoveNode) 연산 구현

//DLL_RemoveNode
Node* DLL_RemoveNode(Node** Head, Node* Remove){
    if((*Head) == Remove){ //Head와 Remove가 같을 때
        *Head = Remove->NextNode; //Head는 Remove의 다음 노드 지시
        if ((*Head) != NULL) //만약 Head가 NULL이 아니라면
            (*Head)->PreNode = NULL; //Head의 이전 노드는 NULL
        Remove->PreNode = NULL; //Remove의 이전 노드는 NULL
        Remove->NextNode = NULL; //Remove의 다음 노드는 NULL
    }
    else{
        Node* Temp = Remove; // Temp에 Remove 할당
        Remove->PreNode->NextNode = Temp->NextNode; //Remove의 이전노드의 다음노드는 Temp의 다음 노드
        Remove->NextNode->PreNode = Temp->PreNode; //Remove의 다음노드의 이전노드는 Temp의 이전노드
    }
    Remove->PreNode = NULL; //Remove의 이전 노드는 NULL
    Remove->NextNode = NULL; //Remove의 다음 노드는 NULL
}

DLL_RemoveNode 연산은 노드를 삭제하는 연산을 수행한다. 여기서 노드를 삭제한다는 것은 기존에 리스트의 일부로서 다른 노드와 연결되어 있던 특정 노드의 연결을 해제하고, 그 노드를 제외한 다른 노드끼리 연결하도록 수정하는 작업을 의미한다.

이 작업을 수행하기 위해서, 일단 리스트의 시작점(Head)이 제거할 노드일 경우에 제거할 노드의 다음 노드를 Head로 재설정하고, 이렇게 재설정된 Head가 NULL이 아니라면 Head의 이전노드를 NULL로 선언함으로써, 새로운 Head를 온전한 Head로 만드는 과정을 수행한다.(시작점이기에 앞에 연결된 노드는 없기 때문이다.)

그리고 제거할 노드인 Remove의 앞 뒤 연결을 해제함으로써, Remove를 전체 리스트의 구성에서 제외해버린다.

만약 Remove가 Head가 아닐 경우엔 Temp에 Remove를 임시 할당하고, Remove 이전노드가 가리키는 다음 노드의 위치에 Remove의 다음 노드를 연결하고, Remove의 다음 노드가 가리키는 이전 노드의 위치에 Remove의 이전 노드를 연결한다. 이 과정을 그림으로 표현하면 다음과 같다.

더블링크드리스트_제거
간단히 표현하면 기존 연결 관계를 해제하고 새로운 연결을 만드는 과정이다.

6. 노드 삽입(DLL_InsertAfter) 연산 구현

//DLL_InsertAfter
Node* DLL_InsertAfter(Node* Current, Node* NewNode){
    NewNode->NextNode = Current->NextNode; // 새로운 노드의 다음 노드로 현재 노드의 다음 노드를 지시하기
    NewNode->PreNode = Current; // 새로운 노드의 이전 노드는 현재 노드

    if(Current->NextNode != NULL){ // 만약 현재 노드의 다음 노드가 존재하지 않는다면,
        Current->NextNode->PreNode = NewNode; // 현재 노드의 다음 노드가 지시하는 이전 노드로 새로운 노드를 지시하기
        Current->NextNode = NewNode; // 그리고 현재 노드의 다음 노드로 새로운 노드를 지시하기
    }
}
// 더블 링크드라서 두 방향 모두 작업이 필요하다.

DLL_InsertAfter 연산은 DLL_AppendNode 연산과는 다르게 현재 노드를 지정한 후, 그 노드의 다음에 새로운 노드를 삽입하는 연산을 수행한다.

즉 리스트의 처음, 중간, 마지막 등 순서 상관 없이 원하는 위치에 새로운 노드를 삽입하는 연산을 의미한다.

이 연산을 수행하기 위해서 우선 기존의 노드 연결을 재정의할 필요가 있다.

기존의 노드 연결이 “이전 노드”<->“현재 노드”<->“다음 노드”라면 DLL_InsertAfter연산을 수행한 후에는

“이전 노드”<->“현재 노드”<->“새로운 노드”<->“다음 노드” 이라는 새로운 연결 관계로 재구성 되는 것이다.

그래서 새로운 노드의 다음 노드엔 기존 현재 노드의 다음 노드가 위치하게 바꾸고, 새로운 노드의 이전 노드로는 현재 노드가 들어와야 한다.

만약 현재 노드의 다음 노드가 NULL이 아니라면(즉, 존재한다면), 현재 노드의 다음 노드가 지시하는 이전 노드가 원래는 Current이지만, 그 노드를 NewNode로 변경하고, 반대로 Current의 다음 노드를 NewNode로 변경하는 과정도 수행한다. (더블 링크드 리스트이기 때문에 역방향의 작업도 수행해야 하기 때문이다.)

7. 노드 개수 세기(DLL_GetNodeCount) 연산 구현

//DLL_GetNodeCount
int DLL_GetNodeCount(Node* Head){
    unsigned int count = 0;
    Node* Current = Head;
    while(Current != NULL){
        Current = Current->NextNode;
        count++;
    }
    return count;    
}

노드 개수 세기 연산인 DLL_GetNodeCount 연산은 앞의 연산보다 구현이 간단하다.

Current에 리스트의 시작점(Head)의 위치를 할당한 후, NULL이 나오지 않는 동안만 Current를 다음 노드로 이동하는 반복을 수행해 전체 노드의 개수를 파악하는 식으로 연산을 구현할 수 있다.

전체 구현 코드

전체를 구현한 코드는 아래와 같다.

// Node
typedef struct tagNode{
    int data; //숫자 자료형 저장
    struct tagNode* PreNode; //이전 노드를 카리켜서 구조체포인터로 정의
    struct tagNode* NextNode;//다음 노드를 가리켜서 구조체포인터로 정의
} Node;

// DLL_CreateNode
Node* DLL_CreateNode(int new_data){
    Node* NewNode = (Node*)malloc(sizeof(Node));
    NewNode->data = new_data;
    NewNode->PreNode = NULL;
    NewNode->NextNode = NULL;

    return NewNode;
}

// DLL_DestroyNode
void DLL_DestroyNode(Node* Node){
    free(Node);
}

// DLL_AppendNode
void DLL_AppendNode(Node** Head, Node* NewNode){
    if ((*Head) == NULL){ //Head가 가리키는 게 없으면 NewNode = Head
        (*Head) = NewNode;
    }
    else{ // Head가 있으면
        Node* Current = (*Head); //Current에 Head가 가리키는 주소 할당
        while(Current->NextNode != NULL){ //Current의 다음 노드가 NULL이 아닐때까지
            Current = Current->NextNode; //Current는 Current의 다음노드 지시
        }
        Current->NextNode = NewNode; //반복 완료하면 Current의 다음노드에 NewNode 담기
        NewNode->PreNode = Current; //NewNode의 이전 노드에 Current 할당(이중연결이라서)
    }
}

//DLL_GetNodeAt
Node* DLL_GetNodeAt(Node* Head, int Location){
    
    Node* Current = Head; //Current에 Head 주소 할당
    while(Current != NULL && Location > 0){ //Current가 NULL이 아닐때까지 && Location이 0 이하인 동안 반복
        Current = Current->NextNode; //Current는 Current의 다음노드로 이동
        Location--; //Location에서 1씩 감소
    }
    return Current;
}

//DLL_RemoveNode
Node* DLL_RemoveNode(Node** Head, Node* Remove){
    if((*Head) == Remove){ //Head와 Remove가 같을 때
        *Head = Remove->NextNode; //Head는 Remove의 다음 노드 지시
        if ((*Head) != NULL) //만약 Head가 NULL이 아니라면
            (*Head)->PreNode = NULL; //Head의 이전 노드는 NULL
        Remove->PreNode = NULL; //Remove의 이전 노드는 NULL
        Remove->NextNode = NULL; //Remove의 다음 노드는 NULL
    }
    else{
        Node* Temp = Remove; // Temp에 Remove 할당
        Remove->PreNode->NextNode = Temp->NextNode; //Remove의 이전노드의 다음노드는 Temp의 다음 노드
        Remove->NextNode->PreNode = Temp->PreNode; //Remove의 다음노드의 이전노드는 Temp의 이전노드
    }
    Remove->PreNode = NULL; //Remove의 이전 노드는 NULL
    Remove->NextNode = NULL; //Remove의 다음 노드는 NULL
}

//DLL_InsertAfter
Node* DLL_InsertAfter(Node* Current, Node* NewNode){
    NewNode->NextNode = Current->NextNode;
    NewNode->PreNode = Current;

    if(Current->NextNode != NULL){
        Current->NextNode->PreNode = NewNode;
        Current->NextNode = NewNode;
    }
}

//DLL_GetNodeCount
int DLL_GetNodeCount(Node* Head){
    unsigned int count = 0;
    Node* Current = Head;
    while(Current != NULL){
        Current = Current->NextNode;
        count++;
    }
    return count;    
}

int main(void){

    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);
    }
}

Twitter Facebook LinkedIn

sk-choi