연결 리스트(LinkedList) 구현하기 (C++)

연결 리스트(LinkedList) 구현하기 (C++)

연결 리스트란?

연결 리스트는 데이터의 집합을 담는 자료구조로, 각 데이터를 노드(Node)라는 객체로 표현하고 노드들을 연결하여 데이터를 관리하는 방식이다.

연결 리스트의 구성 요소

연결 리스트는 다음과 같은 구성 요소로 이루어져 있다.

1. 노드(Node): 데이터와 다음 노드를 가리키는 포인터로 구성된 객체이다.
2. 헤더(Header): 연결 리스트의 첫 번째 노드를 가리키는 포인터이다.
3. 크기(Size): 연결 리스트의 크기, 즉 포함된 노드의 개수를 나타낸다.

연결 리스트의 종류

연결 리스트에는 다음과 같은 종류가 있다.

1. 단일 연결 리스트(Singly Linked List): 각 노드가 다음 노드를 가리키는 방식이며, 이는 단방향으로의 연결을 허용한다.
2. 이중 연결 리스트(Doubly Linked List): 각 노드가 이전 노드와 다음 노드를 가리키는 방식이며, 양방향으로의 연결을 허용한다.
3. 원형 연결 리스트(Circular Linked List): 단일 연결 리스트나 이중 연결 리스트에서 마지막 노드가 첫 번째 노드를 가리키는 형태로 연결된 리스트이다.

연결 리스트 구현하기

#include <iostream>

using namespace std;

// 노드 클래스 정의
class Node {
public:
    int data;
    Node* next;

    Node(int data) {
        this->data = data;
        next = nullptr;
    }
};

// 연결 리스트 클래스 정의
class LinkedList {
private:
    Node* header;
    int size;

public:
    LinkedList() {
        header = nullptr;
        size = 0;
    }

    void push(int data) {
        Node* newNode = new Node(data);

        if (header == nullptr) {
            header = newNode;
        } else {
            Node* currentNode = header;
            while (currentNode->next != nullptr) {
                currentNode = currentNode->next;
            }
            currentNode->next = newNode;
        }

        size++;
    }

    void pop() {
        if (header == nullptr) {
            cout << "연결 리스트가 비어있습니다." << endl;
            return;
        }

        Node* currentNode = header;
        while (currentNode->next->next != nullptr) {
            currentNode = currentNode->next;
        }
        delete currentNode->next;
        currentNode->next = nullptr;

        size--;
    }

    void print() {
        if (header == nullptr) {
            cout << "연결 리스트가 비어있습니다." << endl;
            return;
        }

        Node* currentNode = header;
        while (currentNode != nullptr) {
            cout << currentNode->data << " ";
            currentNode = currentNode->next;
        }
        cout << endl;
    }

    int getSize() {
        return size;
    }
};

int main() {
    LinkedList list;

    list.push(1);
    list.push(2);
    list.push(3);
    list.push(4);

    list.print(); // 1 2 3 4

    list.pop();
    list.pop();

    list.print(); // 1 2

    return 0;
}

위 코드는 C++로 단일 연결 리스트를 구현한 예시이다. 헤더 변수로 첫 번째 노드를 가리키는 포인터를 사용하고, 노드를 추가하는 push 함수, 노드를 제거하는 pop 함수, 연결 리스트를 출력하는 print 함수 등을 구현하였다.

결론

연결 리스트는 포인터를 이용하여 각 노드들을 연결하여 데이터를 관리하는 유용한 자료구조이다. 여러 종류의 연결 리스트 중에서도 단일 연결 리스트, 이중 연결 리스트, 원형 연결 리스트 등 다양한 변형을 사용할 수 있다. 이를 통해 다양한 데이터 구조와 알고리즘을 구현할 수 있으며, 필요에 따라 연결 리스트를 직접 구현하여 활용할 수 있다.