C++로 단일 연결 리스트(Singly Linked List) 구현하는 방법

단일 연결 리스트(Singly Linked List)는 자기 참조 구조체(self-referential structure)를 사용해 만든 노드들이 연결된 형태의 자료구조입니다. 각 노드는 데이터(data)와 다음 노드를 가리키는 참조(next) 두 부분으로 구성됩니다. 연결 리스트 전체에 접근하려면 첫 번째 노드에 대한 참조만 있으면 되는데, 이를 헤드(head)라고 부릅니다. 리스트의 마지막 노드는 다음 노드가 없기 때문에 해당 부분에 NULL을 저장합니다.

다음은 단일 연결 리스트를 구현하는 C++ 프로그램입니다.

예제 코드

#include <iostream>
using namespace std;
struct Node {
    int data;
    struct Node *next;
};
struct Node* head = NULL;
void insert(int new_data) {
    struct Node* new_node = (struct Node*) malloc(sizeof(struct Node));
    new_node->data = new_data;
    new_node->next = head;
    head = new_node;
}
void display() {
    struct Node* ptr;
    ptr = head;
    while (ptr != NULL) {
        cout<< ptr->data <<" ";
        ptr = ptr->next;
    }
}
int main() {
    insert(3);
    insert(1);
    insert(7);
    insert(2);
    insert(9);
    cout<<"연결 리스트: ";
    display();
    return 0;
}

출력 결과

연결 리스트: 9 2 7 1 3

코드 상세 설명

1. 노드 구조체 정의

위 프로그램에서 구조체 Node가 연결 리스트의 개별 노드 역할을 합니다. 이 구조체는 정수형 데이터와 다음 노드를 가리키는 포인터 next로 이루어져 있습니다.

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

2. insert() 함수 — 노드 삽입

insert() 함수는 연결 리스트의 맨 앞에 새로운 데이터를 삽입합니다. 먼저 malloc()으로 new_node를 생성하고, 전달받은 값을 new_node의 data 필드에 저장합니다. 그다음 new_node의 next가 기존의 head를 가리키도록 설정하고, 마지막으로 head를 new_node로 갱신합니다. 즉, 새로 삽입된 노드가 곧 리스트의 시작점이 됩니다.

void insert(int new_data) {
    struct Node* new_node = (struct Node*) malloc(sizeof(struct Node));
    new_node->data = new_data;
    new_node->next = head;
    head = new_node;
}

3. display() 함수 — 리스트 출력

display() 함수는 연결 리스트 전체를 화면에 출력합니다. 포인터 ptr이 head를 가리키게 만든 후, ptr이 NULL이 될 때까지 계속 다음 노드로 이동하면서 각 노드의 데이터 값을 순서대로 출력합니다.

void display() {
    struct Node* ptr;
    ptr = head;
    while (ptr != NULL) {
        cout<< ptr->data <<" ";
        ptr = ptr->next;
    }
}

4. main() 함수 — 실행 흐름

main() 함수에서는 insert() 함수를 여러 번 호출해 연결 리스트에 값들을 차례로 삽입한 뒤, display() 함수를 호출하여 리스트 전체를 출력합니다. 삽입이 항상 맨 앞에서 이루어지므로, 가장 나중에 삽입한 9가 가장 먼저 출력되는 것을 확인할 수 있습니다.

int main() {
    insert(3);
    insert(1);
    insert(7);
    insert(2);
    insert(9);
    cout<<"연결 리스트: ";
    display();
    return 0;
}

참고 사항

맨 앞에 노드를 삽입하는 작업은 포인터 조작만으로 처리되므로 시간 복잡도가 O(1)이며, 리스트 전체를 순회하는 데에는 O(n)이 소요됩니다. 또한 C++에서는 malloc() 대신 new 연산자를 사용하는 것이 메모리 관리 측면에서 더 안전하고 관용적인 방법입니다.