[DS] Linked List 구현(1) - Single Linked List

1. 그림

 여기서 구현한 Single Linked List는 dummy Node와 Tail Node가 없이 오직 Head Node만 있는 가장 기본적이고 간단한 Linked List이다! 도식화 하면 아래와 같다.

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

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

 

 

 

2. 코드 구성

Node 구성

struct Node {
    int data;	// 저장하고자 하는 data
    Node* next;	// 다음 Node의 주소
};

[그림3] Node 구성

 

SingleLinkedList 구성

 SingleLinkedList 클래스는 링크드 리스트 구현을 캡슐화한 클래스로, 실질적인 Node 삽입, 삭제 기능을 하는 멤버함수를 가진다. SingleLinkedList 디폴트 생성자를 호출할때 [그림4]와 같이 초기화가 필요하다.

class SingleLinkedList {
private:
    Node* head;
public:
    SingleLinkedList() { head = NULL; }
    ...
    void pushFront(int data);
    void removeNode(int data);
};

[그림4] SingleLinkedList 초기화

 

Node 생성 및 전방삽입

  SingleLinkedList::pushFront(int)는 전달받은 parameter값으로 Node를 생성한 뒤 해당 Node를SingleLinkedList의 head가 가리키는 전방에 삽입시킨다. 해당 SingleLinkedList에는 tail이 없기에 후방삽입 시간복잡도는 O(N)이 되며 별도로 구현하지 않았다.

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);	// ① Node 생성 및 초기화
    newNode->next = head;				// ② 생성된 Node의 next로 head Node를 가리키게함
    head = newNode;						// ③ 생성된 Node를 head Node로 만듬
}

최초 Node 삽입시,

 

그 이후 Node 삽입시,

 

Node 삭제

  SingleLinkedList::removeNode(int)는 parameter로 받은 data값을 가진 Node를 모두 삭제한다. dummy Node를 사용하고 있지 않기때문에 cur가 head인지 아닌지에 따라 코드가 분기된다. (dummy node가 없어 코드의 일관성이 떨어진다)

void SingleLinkedList::removeNode(int data) {
    Node* pre = NULL;
    Node* cur = head;

    while (cur != NULL) {
        if (cur->data == data) {
            Node* deleteNode = cur;
            if (cur == head)        // dummy node가 없어, cur가 head인지 아닌지에 따라 삭제 방법이 다르다
                head = cur->next;
            else
                pre->next = cur->next;
            cur = cur->next;
            free(deleteNode);
        }
        else {
            pre = cur;
            cur = cur->next;
        }
    }
}

 

모든 Node 삭제

  SingleLinkedList::removeAllNodes()는 head를 포함해 모든 Node를 삭제한다. while문이 끝나면 head에 쓰래기값이 저장되어 있기 때문에 마지막줄처럼 head에 NULL을 반드시 대입시켜 주어야한다.

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

 

 

 

3. 전체 코드

SingleLinkedList.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 = NULL; }
    Node* getHead() { return head; }
    Node* createNode(int data);
    
    void pushFront(int data);
    void removeNode(int data);
    void removeAllNodes();
};

#endif // SINGLE_LINKED_LIST

 

SingleLinkedList.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;
    head = newNode;
}

void SingleLinkedList::removeNode(int data) {
    Node* pre = NULL;
    Node* cur = head;

    while (cur != NULL) {
        if (cur->data == data) {
            Node* deleteNode = cur;
            if (cur == head)
                head = cur->next;
            else
                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) {
    for (Node* cur = linkedList->getHead(); cur != NULL; cur = cur->next)
        printf("%d->", cur->data);
    printf("NULL\n");
}

int main() {
    SingleLinkedList singleLinkedList;
    printLinkedList(&singleLinkedList);	// NULL

    singleLinkedList.pushFront(1);
    singleLinkedList.pushFront(2);
    singleLinkedList.pushFront(3);
    singleLinkedList.pushFront(1);
    singleLinkedList.pushFront(1);
    printLinkedList(&singleLinkedList);	// 1->1->3->2->1->NULL

    singleLinkedList.removeNode(1);
    printLinkedList(&singleLinkedList);	// 3->2->NULL

    singleLinkedList.removeNode(2);
    printLinkedList(&singleLinkedList);	// 3->NULL

    singleLinkedList.removeNode(3);
    printLinkedList(&singleLinkedList);	// NULL

    singleLinkedList.removeAllNodes();

    return 0;
}