[DS] Linked List 구현(2) - Single Linked List(with Dummy)

1. 그림

  이번에 구현한 Single Linked List는 Head가 Dummy Node를 가리킨다. 이로인해 삭제코드를 짤때 삭제할 노드가 Head Node인지 아닌지 구분해야하는 부분이 불필요해지기 때문에 일관성 있는 코드를 짤 수 있게 된다.

  또한 Single Linked List에서 Tail과 후방삽입 구현은 생략하는데 이는 Single Linked List구조 특성상 후방삽입이 적합하지 않기 때문이다. 후방삽입을 위해서는 Tail 바로 직전 Node에 접근을 해야하는데 Single Linked List에서는 Tail Node를 구현하여도 Tail 바로 직전 Node에 접근하기 위해서 후방삽입을 할때마다 시간복잡도 O(N-1)을 소비하여 순차탐색으로 접근하던지, Head, Tail, 추가적으로 Tail바로직전 Node 이렇게 3가지를 가리키는 포인터변수를 처음부터 두고 관리를 하던지 해야하기에 비효율적이다.

[그림1] Single Linked List(with dummy) - 초기상태

[그림2] Single Linked List(with dummy) - data삽입후 상태

 

 

 

2. 전체 코드

Single Linked List(without dummy)와 비교했을때 다른 부분은 "// *다른 부분" 으로 표시하였다.

SingleLinkedList_withDummy.h

#ifndef SINGLE_LINKED_LIST
#define SINGLE_LINKED_LIST
#include<malloc.h>

struct Node {
    int data;
    Node* next;
};

class SingleLinkedList {
private:
    Node* head;
public:
    SingleLinkedList() { head = createNode(0); }	// *다른 부분
    Node* getHead() { return head; }
    Node* createNode(int data);
    
    void pushFront(int data);
    void removeNode(int data);
    void removeAllNodes();
};

#endif // SINGLE_LINKED_LIST

 

SingleLinkedList_withDummy.cpp

#include "SingleLinkedList.h"

Node* SingleLinkedList::createNode(int data) {
    Node* newNode = (Node*)malloc(sizeof(Node));
    newNode->data = data;
    newNode->next = NULL;

    return newNode;
}

void SingleLinkedList::pushFront(int data) {
    Node* newNode = createNode(data);
    newNode->next = head->next;             // *다른 부분
    head->next = newNode;                   // *다른 부분
}

void SingleLinkedList::removeNode(int data) {
    Node* pre = head;                       // *다른 부분
    Node* cur = head->next;                 // *다른 부분

    while (cur != NULL) {
        if (cur->data == data) {
            Node* deleteNode = cur;
            // *다른 부분(cur == head 분기문 삭제)
            pre->next = cur->next;
            cur = cur->next;
            free(deleteNode);
        }
        else {
            pre = cur;
            cur = cur->next;
        }
    }
}

void SingleLinkedList::removeAllNodes() {
    Node* cur = head;
    while (cur != NULL) {
        Node* temp = cur;
        cur = cur->next;
        free(temp);
    }
    head = NULL;
}

 

main.cpp

#include<iostream>
#include "SingleLinkedList.h"
using namespace std;

void printLinkedList(SingleLinkedList* linkedList) {
    printf("[dmy head]->");
    Node* cur = linkedList->getHead()->next;
    for (; cur != NULL; cur = cur->next)
        printf("%d->", cur->data);
    printf("NULL\n");
}

int main() {
    SingleLinkedList singleLinkedList;
    printLinkedList(&singleLinkedList);	// [dmy head]->NULL

    singleLinkedList.pushFront(1);
    singleLinkedList.pushFront(2);
    singleLinkedList.pushFront(3);
    singleLinkedList.pushFront(1);
    singleLinkedList.pushFront(1);
    printLinkedList(&singleLinkedList);	// [dmy head]->1->1->3->2->1->NULL

    singleLinkedList.removeNode(1);
    printLinkedList(&singleLinkedList);	// [dmy head]->3->2->NULL

    singleLinkedList.removeNode(2);
    printLinkedList(&singleLinkedList);	// [dmy head]->3->NULL

    singleLinkedList.removeNode(3);
    printLinkedList(&singleLinkedList);	// [dmy head]->NULL

    singleLinkedList.removeAllNodes();

    return 0;
}