[자료구조] 더블 링크드 리스트(DoublyLinkedList/DLL) - 코딩밥상

더블 링크드 리스트란?

앞서 싱글 링크드 리스트에 대해서 포스팅했습니다. 텍스트 자체에서 알 수 있듯이 이번엔 양방향 노드에 대해서 연결되어있는 구조입니다.

즉 이전 노드를 가리키는 포인터를 포함해주면 되겠죠? 그림으로 이해하자면 다음과 같습니다.

 

SLL와의 성능적 차이점은 어떻게 될까요? SLL의 아픈손가락인 탐색 기능이 좀 더 유연해집니다. SLL은 한 방향으로만 탐색이 가능했었지만 이번에 배울 DLL은 양방향으로의 탐색이 가능합니다.

하지만 포인터 공간이 늘어나는만큼, 데이터 공간도 조금 더 필요하겠네요.

typedef struct tagNode{
    ElementType Data;
    struct tagNode* NextNode;
    struct tagNode* PrevNode;
} Node;

 

노드 구조체를 먼저 보자면, 앞 노드를 가리키는 PrevNode포인터만 추가해 주면 되겠네요.

그렇다면 ADT에 대해서도 SLL과의 차이점은 단지 앞 노드를 가리키는 포인터만 신경써주면 되겠습니다.

 

---

주요 연산(ADT)

• 노드 생성 연산

Node* DLL_CreateNode(ElementType NewData){  //노드 생성
    Node* NewNode = (Node*)malloc(sizeof(Node));
    
    NewNode->Data = NewData;
    NewNode->NextNode = NULL;
    NewNode->PrevNode = NULL;
    
    return NewNode;
}

---

• 노드 추가 연산

void DLL_AppendNode(Node** Head, Node* NewNode){    //노드 추가
    if((*Head) == NULL){    //헤드 노드가 NULL이면(노드가 없으면), 새로운 노드가 Head
        *Head = NewNode;
    }
    else{   //테일을 찾아 NewNode를 연결
        Node* Tail = (*Head);
        while(Tail->NextNode != NULL){
            Tail = Tail->NextNode;
        }
        
        Tail->NextNode = NewNode;
        NewNode->PrevNode = Tail;
    }
}

---

• 노드 소멸 연산

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

 

소멸 연산에서는 prev,next 포인터 상관 없이 생성 연산에서 할당한 Heap공간을 free()함수 처리만 하면 됩니다. 

---

• 노드 탐색 연산

Node* DLL_GetNodeAt(Node* Head, int Location){    //노드 탐색
    Node* Current = Head;
    
    while(Current != NULL && (--Location) >= 0){    //Head노드부터 하나씩 넘어가며 탐색
        Current = Current->NextNode;
    }
    
    return Current;
}

 

일단은 SLL과 동일하게 한 방향으로만 탐색이 가능하게 코드를 짰지만, 그와 다른점은

DLL이기 때문에 반대 방향으로도 탐색이 가능하게 코드를 짤 수 있습니다. 탐색 시작을 Tail로 설정하고 반복 조건을 (++Location <= 0)으로 설정하면 되겠습니다.

---

• 노드 삭제 연산

void DLL_RemoveNode(Node** Head, Node* Remove){     //노드 삭제
    if (*Head == Remove){   //Head를 삭제할 경우
        *Head = Remove->NextNode;
        if((*Head) != NULL){
            (*Head)->PrevNode = NULL;   //Head삭제 후에도 노드가 있을 경우
        }
        
        Remove->PrevNode = NULL;
        Remove->NextNode = NULL;
    }
    else{
        Node* Temp = Remove;      //Head부터 삭제할 노드를 탐색
        
        if(Remove->PrevNode != NULL){   //삭제할 노드의 다음 노드가 존재할경우
            Remove->PrevNode->NextNode = Temp->NextNode;
        }
        
        if(Remove->NextNode != NULL){   //삭제할 노드의 이전 노드가 존재할 경우
            Remove->NextNode->PrevNode = Temp->PrevNode;
        }
        
        Remove->NextNode = NULL;
        Remove->PrevNode = NULL;
    }
}

 

양방향 노드의 포인터를 관리해야하기 때문에 SLL보다 코드가 길어집니다.

삭제할 노드의 전,후의 연결을 끊고 그 연결을 다시 연결해주는 동작입니다. 이 또한 기차놀이를 생각하고 머리속으로 그리면 이해가 쉬워집니다.

---

• 노드 삽입 연산

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){ //Head부터 Tail까지 카운트 업
        Current = Current->NextNode;
        count++;
    }
    return count;
}

 

---

SLL 복습하기

2022.12.22 - [자료구조/리스트(List)] - [자료구조] 싱글 링크드 리스트(Singly Linked List / SLL) - 코딩밥상

[자료구조] 싱글 링크드 리스트(Singly Linked List / SLL) - 코딩밥상