[자료구조] 선형 연결 리스트(Singly Linked List)란?

안녕하세요, IT디자이너입니다.

 

이번에는 링크드 리스트(Linked ListSingly Linked List)에 대하여 포스팅하도록 하겠습니다. 

 

 

- 리스트(List)란 무엇인가?

 

리스트(List)는 데이터를 순서대로 나열한(줄지어 늘어놓은) 자료구조입니다. 대표적으로 스택과 큐가 리스트 형태의 자료구조입니다. 

 

하지만, 배열로 구현된 선형 리스트는 다음과 같은 문제를 가지고 있습니다. 

 

단점)

• 쌓이는 데이터의 크기를 미리 알아야합니다. 
• 데이터를 중간에 삽입, 삭제에 따라 데이터를 모두 옮겨야 하기 때문에 효율이 좋지 않습니다. 

 

이러한 단점들을 보안하기 위해 "노드(Node)"라는 개념과 포인터를 사용하여 연결 리스트(Linked List)를 구현할 수 있습니다.

 

 

 

싱글 연결 리스트 

 

사진 처럼 Node라는 객체에 저장할 데이터와 다음 노드의 위치를 가리키는 포인터 정보를 저장합니다. 

 

포인터로 연결된 방식이므로 데이터를 중간에 삽입하거나 삭제한다 하더라도 배열로된 리스트 보다는 큰 작업이 필요 없습니다. 

 

또한 첫번재 노드는 머리(head)노드로서 데이터를 저장하지 않고 오로지 다음 노드를 가리키기만 하는 노드입니다. 

헤더 노드가 가리키는 노드부터 데이터를 저장하여 연결 리스트를 구현하시면 됩니다.

 

- 선형 연결 리스트(Singly Linked List)에서 사용하는 함수

• insertFront() : 헤더 노드가 가리키는 노드에 값을 추가합니다. 
• insertRear() : 꼬리 노드에 삽입합니다.
• removeFront() : 머리노드가 가리키는 노드를 삭제합니다.
• removeRear() : 꼬리 노드를 삭제합니다.
• showAll() : 모든 노드를 보여줍니다.
• deleteAll() : 모든 노드를 삭제합니다.
• isEmpty() : 노드가 비어있는지 확인합니다.
• inputData() : 원하는 위치에 데이터를 삽입합니다.
• printfNode() : 노드를 출력합니다.

 

- 선형 연결 리스트(Singly Linked List) 구현

#include <iostream>

using namespace std;

struct Node {
    Node* next; // 자기 참조 구조체 
    //자기참조 구조체란 자신과 같은 자료형의 객체를 가리키는 포인터를 멤버로 가지고 있다라는 뜻
    int data;
};

bool insertFront(Node *head, int data); // 헤더 노드가 가리키는 노드에 값을 추가합니다. 

bool insertRear(Node *head, int data); // 꼬리 노드를 삭제합니다. 

bool removeFront(Node *head); // 헤더 노드가 가리키는 노드를를 삭제합니다.

bool removeRear(Node *head); // 꼬리 노드를 삭제합니다.

bool showAll(Node *head); // 모든 노드를 보여줍니다.

bool deleteAll(Node *head); // 모든 노드를 삭제합니다.

bool isEmpty(Node *head); // 노드가 비어있는지 확인합니다.

bool inputData(Node* head,int num, int data); // 원하는 위치에 데이터를 삽입한다.

bool printfNode(Node* node); // 노드를 출력합니다.

void showMenu(); // 메뉴를 출력합니다. 

int main()
{
    int sel;

    int data;

    Node *head = (Node*)malloc(sizeof(Node));
    head->next = nullptr;
    
    while (1) {
        showMenu();
        
        cin >> sel;


        switch (sel) {
        case 1:
            cout << "데이터 입력 : ";
            cin >> data;
           
            if (insertFront(head, data) == true)
                cout << "입력 완료" << endl;
            else
                cout << "입력 실패" << endl;
            
            break;
        case 2:
            cout << "데이터 입력 : ";
            cin >> data;

            if (insertRear(head, data) == true)
                cout << "입력 완료" << endl;
            else
                cout << "입력 실패" << endl;

            break;
        case 3:

            if (removeFront(head) == true)
                cout << "삭제 완료" << endl;
            else
                cout << "삭제 실패" << endl;

            break;
        case 4:
            if (removeRear(head) == true)
                cout << "삭제 완료" << endl;
            else
                cout << "삭제 실패" << endl;
            break;
        case 5:
            if (showAll(head) != true)
                cout << "노드 출력 실패" << endl;
            break;
        case 6:
            if (deleteAll(head) == true)
                cout << "모든 노드 삭제 완료" << endl;
            else
                cout << "삭제 실패" << endl;
            break;
        case 7:
            cout << "데이터를 입력 : ";
            cin >> data;
            cout << "저장할 노드 인덱스 : ";
            cin >> sel;
            if(inputData(head, sel, data) == true)
                cout << "입력 완료" << endl;
            else
                cout << "입력 실패" << endl;

            break;
        case 8:
            cout << endl;
            free(head); // 머리 노드를 해제합니다.
            cout << "프로그램을 종료합니다." << endl;

        }
        cout << endl;

        if (sel == 8)
            break;
    }

}



bool insertFront(Node *head, int data) {

    if (head == nullptr || data == NULL)
        return false;

    Node* node = (Node*)malloc(sizeof(Node));
    node->data = data;
    node->next = head->next;
    head->next = node;

    return true;
}

bool insertRear(Node *head, int data) {

    if (head->next == nullptr || data == NULL)
        return false;

    Node* cur = head;

    while (1) {
        cur = cur->next;

        if (cur->next == nullptr) {
            Node* node = (Node*)malloc(sizeof(Node));
            cur->next = node;
            node->next = nullptr;
            node->data = data;
            return true;
        }
    }
}

bool removeFront(Node* head) {

    if (head->next == nullptr) // 헤더 노드가 가리키는 값이 없으면 false를 return
        return false;

    Node* front = head->next;
    head->next = front->next;
    free(front);

    return true;
}


bool removeRear(Node *head) { 

    if (head->next == nullptr) //헤더 노드가 가리키는 값이 없으면 false를 return
        return false;

    Node* pre = head;

    Node* cur;

    while (1) {
        cur = pre->next;

        if (cur->next == nullptr) {
            free(cur);
            pre->next = nullptr;
            return true;
        }
        pre = pre->next;
    }

}

bool printfNode(Node* node) {
    
    if (node != nullptr) {
        cout << "데이터 : " << node->data << endl;
        return true;
    }
    else
        return false;
}


bool showAll(Node *head) {

    if (head->next == nullptr)
        return false;
    
    Node* cur = head->next; 
    while (cur != nullptr) { // cur이 nullptr이 되기 전까지 반복하며 출력합니다.
        printfNode(cur);
        cur = cur->next;
    }
    return true;
}

bool deleteAll(Node *head) {

    if (head->next == nullptr)
        return false;

    Node* cur = head->next;
    while (cur != NULL) {
        Node* next = cur->next; // cur이 가리키는 다음 노드를 next 노드에 저장합니다.
        free(cur); // cur 노드를 삭제합니다.
        
        cur = next; // 값을 저장해놓은 next 노드의 값을 cur에 저장합니다.
    }
    head->next = nullptr;
    return true;
}

bool inputData(Node* head, int num, int data) { 

    if (head == nullptr || num == NULL || data == NULL)
        return false;

    int checkNum = 0;
    Node* ptr;

    ptr = head; // 헤더의 값을 ptr에 삽입

    while (1) {
        if (checkNum == num) {

            Node* node = (Node*)malloc(sizeof(Node));
            Node* pre = ptr->next;  // pre에 ptr next 노드의 대입합니다.
            ptr->next = node; // 새로 할당할 노드를 ptr이 가리키는 위치에 노드를 넣습니다. 
            node->next = pre; // 새로 할당한 노드에 pre->next 값을 대입합니다. 
            node->data = data;
        }
        else if (checkNum > num)
            return false;

        ptr = ptr->next;

        checkNum++;
    }

}
bool isEmpty(Node *head) {

    if (head->next == nullptr) // 노드가 비어있는지 확인합니다.
        return true;
    else
        return false;

}


void showMenu() {

    cout << "---------- 메뉴 ----------" << endl;
    cout << "1. 첫번째 노드에 데이터 삽입" << endl;
    cout << "2. 꼬리 노드에 데이터 삽입" << endl;
    cout << "3. 첫 번째 노드 삭제" << endl;
    cout << "4. 꼬리 노드 삭제" << endl;
    cout << "5. 모든 노드 출력" << endl;
    cout << "6. 모든 노드 삭제" << endl;

    cout << "7. 원하는 위치에 데이터 삽입 "<< endl;

    cout << "8, 종료" << endl;
    cout << "번호 입력 : ";

}

 

Node를 활용한 싱글 연결 리스트를 구현해보았습니다.  하지만, 연결리스트도 단점이 있습니다. 

 

배열로된 리스트는 원하는 인덱스에 바로 접근이 가능합니다. 연결리스트는 처음 노드부터 하나 하나 확인하여 탐색하여야합니다. 

 

 

---

이상 IT디자이너였습니다. 

 

감사합니다.