[자료구조] Singly Linked List/단일 연결 리스트 & 단일 연결 리스트 구현 :: C++

1. 단일 연결 리스트란?

• 각 요소들이 데이터부분과 다음 값 주소를 포인팅하는 노드라는 형태로 이루어져 있으며 체인 형태로 선형으로 이루어진 자료구조이다.
• 값을 추가할 때 배열은 정해진 사이즈를 넘으면 Overflow가 발생하지만 Linked List는 동적으로 할당해서 노드들을 이어주면 되기 때문에 메모리 사이즈 문제에서 벗어날 수 있다.

하지만 노드들이 서로 체인형태로 이어져 있어 배열처럼 인덱스 개념으로 접근이 불가하기 때문에 순회하여 값을 찾아야 하으로 탐색에 있어서는 배열보다 느리다. 하지만 값을 중간에 넣는 경우 배열은 중간에 값을 삽입하고 한칸씩 뒤로 미뤄줘야 하기 때문에 원소의 갯수에 따라 시간이 차이가 나는 방면, 연결 리스트의 경우 단지 노드의 포인팅만 바꿔주면 되기 때문에 최악의 경우 접근하는데 최대 O(n) + 삽입에 O(1)이 소요된다.

출처 https://medium.com/wasd/c-c-%EC%9E%90%EB%A3%8C%EA%B5%AC%EC%A1%B0-%EC%97%B0%EA%B2%B0-%EB%A6%AC%EC%8A%A4%ED%8A%B8-1-41a312399a8f

 

2. 단일 연결 리스트 구현

원래는 내가 공부하고 있는 책인 "Fundamentals of Data Structures in C++"에서 나온 함수만 구현하려 했는데 궁금해서 기본 단일 연결 리스트에 없는거도 그냥 막 구현해봤다. ex> sortAdd

코드를 보기 전에 단일 연결 리스트의 첫 시작부분은 Head, 마지막 부분은 Tail이며 Tail이 포인팅하는 주소는 nullptr이다. 노드가 nullptr을 포인팅 하게 되면 리스트의 마지막임을 알기 위해서 이다.

1. 노드 정보

각 노드들은 데이터를 저장하는 data부분과 다음 노드를 포인팅하는 next부분을 가지고 있다.

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

2. 단일 연결 리스트 클래스

단일 연결 리스트는 시작부분인 head와 마지막 부분인 tail로 이루어져 있다. 생성자로 초기에는 head와 tail모두 nullprt을 포인팅하고있다.

class SinglyLinkedList{
private:
    Node* head;
    Node* tail;
    int size = 0;

public:
    SinglyLinkedList() : head(nullptr), tail(nullptr) {}
    ~SinglyLinkedList() {}
    void AddNodeFront(int value);
    void AddNodeEnd(int value);
    void AddNodeOnAnywhere(int idx, int value);
    void SortAdd(int value);
    void DeleteEndNode();
    void DeleteNode(int idx);
    void PrintAll();
};

3. AddNodeFront

항상 Head부분에 삽입하는 함수이다. 노드가 하나도 없을 때는 자기 자신이 head이자 tail이고 노드가 이미 존재할 때는 삽입할 노드가 원래의 head부분을 포인팅하고 이후 head를 노드가 담당한다.

void SinglyLinkedList::AddNodeFront(int value) {
    Node* node = new Node;

    size++;
    node->data = value;
    node->next = nullptr;

    //노드가 하나도 없을 때
    if(head == nullptr) {
        head = node;
        tail = node;
    }
    //노드가 1개 이상일 떄
    else { 
        node->next = head;
        head = node;
    }
}

 

4. AddNodeEnd

3번 함수와 반대로 마지막 tail부분에만 데이터를 삽입하는 함수이다. 원래 tail이었던 노드는 삽입될 노드를 포인팅하고 삽입될 노드가 tail을 맡게된다.

void SinglyLinkedList::AddNodeEnd(int value) {
    Node* node = new Node;

    size++;
    node->data = value;
    node->next = nullptr;

    //노드가 하나도 없을 때
    if(head == nullptr) {
        head == node;
        tail == node;
    }
    else {
        tail->next = node;
        tail = node;
    }
}

5. AddNodeOnAnywhere

링크드리스트는 삽입이 자유롭기 때문에 구현해봤다. 정석인지는 모르겠지만 작동은 잘 된다.

1 4 7 8 이렇게 노드가 있다고 했을 때 1 < value > 4 사이에 넣고싶으면 2번 인덱스를 입력하면 된다.2번인덱스인 4를 밀고 그 사이에 넣어야 하지만 단일 연결 리스트는 주소를 참조하기 때문에 삽입할 노드를 node라고 하면

1. idx-1번째 노드를 찾아서 node는 원래 idx-1번째 노드가 포인팅하는 노드를 포인팅하도록 변경하고

2. idx-1번째 노드는 node를 포인팅하도록 변경해준다.

void SinglyLinkedList::AddNodeOnAnywhere(int idx, int value) {
    Node* node = new Node;
    if(idx <= 1) {
        AddNodeFront(value);
    }
    else {
        Node* prev = head;
        
        int cnt = 1;
        while(cnt != idx-1) {
            prev = head->next;
            cnt++;
        }

        Node* node = new Node;
        node->data = value;
        node->next = prev->next;
        prev->next = node;
    }
    size++;
}

 

6. SortAdd

연결되어 있기 때문에 오름차순으로 정렬해서 넣으면 좋겠어서 구현해봤다. size==0일 때는 그냥 삽입했고 그 이외는 오름차순으로 정렬해서 삽입하는 로직이다.

while문은 마지막 노드가 아니 && 삽입하려는 값이 temp가 포인팅하는 다음 노드의 값보다 작을 때 temp뒤에 노드를 삽입하는 로직으로 구현했다.

다만 노드의 갯수가 1개일때 또는 오름차순 결과 Head에 위치해야할 때는 while문에 들어가지 못하고 그냥 Head뒤에 삽입되게 되어 오름차순이 깨지는 문제가 발생해서 삽입할 위치를 찾은 뒤 한번 더 value값을 검사해줘서 value가 temp보다 더 작으면 앞에 삽입할 수 있도록 해줬다.

void SinglyLinkedList::SortAdd(int value) {
    if(size == 0) {
        AddNodeFront(value);
    }
    else {
        Node* temp = head;
        while(temp->next != nullptr && (value > temp->next->data)) {
            temp = temp->next;
        }
        

        Node* node = new Node;
        node->data = value;

        if(value < temp->data) {
            node->next = temp;
            head = node;
        }
        else {
            node->next = temp->next;
            temp->next = node;
        }

    }
    size++;
}

7. DeleteEndNode

가장 뒤에있는 tail노드를 삭제한다. 구현하다보니 이러면 exception발생할 것 같은데?라는 생각이 들어서 계속 코드가 추가됐다ㅋㅋㅋㅋ

기본적으로 tail노드를 삭제하는 연산의 순서는

1. tail이전의 노드까지 순회를 해서 prev노드를 찾고

2. 기존 tail노드의 메모리를 삭제해주고(메모리 누수 방지)

3. tail을 기존 tail노드를 포인팅하던 prev노드로 변경해준다음(원래 tail이었던 target 메모리만 삭제하고 3번 연산을 안해주면 tail은 null상태이므로 다시 삽입연산을 할 때 tail쪽에 삽입을 하게 되면 null참조가 발생할 수 있다.)

4. prev가 포인팅하는 주소를 nullptr로 설정해준다.

void SinglyLinkedList::DeleteEndNode() {
    if(size == 0) {
        cout << "삭제할 노드가 없습니다." << "\n";
        exit(EXIT_FAILURE);
    }

    if(size == 1) {
        delete(tail);
        tail = nullptr;
        head = nullptr;
    }
    else {
        Node* prev = head;
        Node* target = head->next;
        
        while(target != tail) {
            prev = target;
            target = target->next;
        }

        delete(target);
        tail = prev;
        prev->next = nullptr;
    }
    size--;
}

8. DeleteNode

void SinglyLinkedList::DeleteNode(int idx) {
    if(size == 0) {
        cout << "삭제할 노드가 없습니다." << "\n";
        exit(EXIT_FAILURE);
    }
    
    if(size == 1) {
        delete(tail);
        tail = nullptr;
        head = nullptr;
    }
    else {
        Node* prev = head;
        
        int cnt = 1;
        while(cnt != idx-1) {
            prev = prev->next;
            cnt++;
        }

        prev->next = prev->next->next;
        delete(prev->next);
    }
    size--;
}

9. PrintAll

순회하면서 노드에 담긴 데이터를 출력한다.

void SinglyLinkedList::PrintAll() {
    cout << "Head";
    Node* node = head;
    while(node != nullptr) {
        cout << " - " << node->data;
        node = node->next;
    }
    cout << " - Tail" << "\n";
}

10. 전체 코드

#include <iostream>
#include <cstdlib>

using namespace std;

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

class SinglyLinkedList{
private:
    Node* head;
    Node* tail;
    int size = 0;

public:
    SinglyLinkedList() : head(nullptr), tail(nullptr) {}
    ~SinglyLinkedList() {}
    void AddNodeFront(int value);
    void AddNodeEnd(int value);
    void AddNodeOnAnywhere(int idx, int value);
    void SortAdd(int value);
    void DeleteEndNode();
    void DeleteNode(int idx);
    void PrintAll();
};

void SinglyLinkedList::AddNodeFront(int value) {
    Node* node = new Node;

    size++;
    node->data = value;
    node->next = nullptr;

    //노드가 하나도 없을 때
    if(head == nullptr) {
        head = node;
        tail = node;
    }
    //노드가 1개 이상일 떄
    else { 
        node->next = head;
        head = node;
    }
}

void SinglyLinkedList::AddNodeEnd(int value) {
    Node* node = new Node;

    size++;
    node->data = value;
    node->next = nullptr;

    //노드가 하나도 없을 때
    if(head == nullptr) {
        head == node;
        tail == node;
    }
    else {
        tail->next = node;
        tail = node;
    }
}

void SinglyLinkedList::AddNodeOnAnywhere(int idx, int value) {
    Node* node = new Node;
    if(idx <= 1) {
        AddNodeFront(value);
    }
    else {
        Node* prev = head;
        
        int cnt = 1;
        while(cnt != idx-1) {
            prev = head->next;
            cnt++;
        }

        Node* node = new Node;
        node->data = value;
        node->next = prev->next;
        prev->next = node;
    }
    size++;
}

void SinglyLinkedList::SortAdd(int value) {
    if(size == 0) {
        AddNodeFront(value);
    }
    else {
        Node* temp = head;
        while(temp->next != nullptr && (value > temp->next->data)) {
            temp = temp->next;
        }
        

        Node* node = new Node;
        node->data = value;

        if(value < temp->data) {
            node->next = temp;
            head = node;
        }
        else {
            node->next = temp->next;
            temp->next = node;
        }

    }
    size++;
}

void SinglyLinkedList::DeleteEndNode() {
    if(size == 0) {
        cout << "삭제할 노드가 없습니다." << "\n";
        exit(EXIT_FAILURE);
    }

    if(size == 1) {
        delete(tail);
        tail = nullptr;
        head = nullptr;
    }
    else {
        Node* prev = head;
        Node* target = head->next;
        
        while(target != tail) {
            prev = target;
            target = target->next;
        }

        delete(target);
        tail = prev;
        prev->next = nullptr;
    }
    size--;
}

void SinglyLinkedList::DeleteNode(int idx) {
    if(size == 0) {
        cout << "삭제할 노드가 없습니다." << "\n";
        exit(EXIT_FAILURE);
    }
    
    if(size == 1) {
        delete(tail);
        tail = nullptr;
        head = nullptr;
    }
    else {
        Node* prev = head;
        
        int cnt = 1;
        while(cnt != idx-1) {
            prev = prev->next;
            cnt++;
        }

        prev->next = prev->next->next;
        delete(prev->next);
    }
    size--;
}

void SinglyLinkedList::PrintAll() {
    cout << "Head";
    Node* node = head;
    while(node != nullptr) {
        cout << " - " << node->data;
        node = node->next;
    }
    cout << " - Tail" << "\n";
}

void menuPrint() {
    cout << "==============SinglyLinkedList===============" << "\n";
    cout << "[1] AddNodeFront" << "\n";
    cout << "[2] AddNodeEnd" << "\n";
    cout << "[3] AddNodeOnAnywhere" << "\n";
    cout << "[4] SortAdd" << "\n";
    cout << "[5] DeleteEndNode" << "\n";
    cout << "[6] DeleteNode" << "\n";
    cout << "[7] PrintAll" << "\n";
    cout << "[Exit] Exit(1~6제외 아무키나 누르세요)" << "\n";
}

int main() {
    SinglyLinkedList SSL;

    while(true) {
        menuPrint();
        char cmd;
        cin >> cmd;
        if(cmd == '1') {
            int value;
            cout << "제일 처음에 삽입 할 값 입력 : ";
            cin >> value;
            SSL.AddNodeFront(value);
        }
        else if(cmd == '2') {
            int value;
            cout << "제일 끝에 삽입 할 값 입력 : ";
            cin >> value;
            SSL.AddNodeEnd(value);
        }
        else if(cmd == '3') {
            int value, idx;
            
            cout << "원하는 인덱스 : " ;
            cin >> idx;
            cout << "\n";
            cout << "삽입 할 값 입력 : ";
            cin >> value;
            SSL.AddNodeOnAnywhere(idx, value);
        }
        else if(cmd == '4') {
            int value;
            cout << "정렬하여 삽입할 값 입력 : ";
            cin >> value;
            SSL.SortAdd(value);
        }        
        else if(cmd == '5') {
            SSL.DeleteEndNode();
        }
        else if(cmd == '6') {
            int idx;            
            cout << "삭제를 원하는 인덱스 : " ;
            cin >> idx;
            SSL.DeleteNode(idx);
        }
        else if(cmd == '7') {
            SSL.PrintAll();
        }
        else {
            exit(0);
        }
    }
}

3. 느낀점?

단일 연결 리스트를 구현해보니까 쓸게 못된다는 생각이 들었다ㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋ 뭘 할래도 이전 노드 or 다음 노드가 필요한데 뒤로는 못가니 앞에서부터 순회해야하고 이 과정이 복잡하고 낭비가 심하다는 생각이 들었다. 단일 연결 리스트를 업그레이드 시킨 이중 연결 리스트를 얼른 구현해봐야겠다

CS 지식을 공부하고 기록하는 개인 공부 블로그입니다.
내용 중 틀린 부분 피드백 혹은 궁금한 점이 있으면 댓글로 남겨주시면 참고 및 답변 달아드리겠습니다🧐