C/C++ 자료 구조

단일 연결 리스트

각 node는 value와 다음 node의 link를 가집니다.

단일 연결 리스트이란?

각 node는 value와 다음 node의 link를 가집니다.

Linked list를 생성, 순회, 해제합니다.

중요한 점

연산 전에 invariant를 정의하세요.
비어 있음, 가득 참, 할당 실패를 처리하세요.
시간 복잡도와 ownership을 함께 평가하세요.

C와 C++ 코드 예제

실행 →

main.c

#include <stdio.h>
#include <stdlib.h>

typedef struct Node {
    int value;
    struct Node *next;
} Node;

int main(void) {
    Node *head = NULL;
    for (int value = 3; value >= 1; --value) {
        Node *node = malloc(sizeof *node);
        if (!node) return 1;
        *node = (Node){value, head};
        head = node;
    }
    while (head) {
        Node *next = head->next;
        printf("%d ", head->value);
        free(head);
        head = next;
    }
    puts("");
    return 0;
}

예상 출력

1 2 3

C++

실행 →

main.cpp

#include <iostream>
#include <memory>

struct Node {
    int value;
    std::unique_ptr<Node> next;
};

int main() {
    std::unique_ptr<Node> head;
    for (int value = 3; value >= 1; --value) {
        head = std::make_unique<Node>(Node{value, std::move(head)});
    }
    for (Node *node = head.get(); node; node = node->next.get()) {
        std::cout << node->value << ' ';
    }
    std::cout << '\n';
}

예상 출력

1 2 3

C와 C++ 비교

C는 malloc한 각 node를 free합니다. C++ unique_ptr는 head 파괴 시 전체 chain을 자동 해제합니다.

구조체와 연산이 분리되고 할당이 명시적입니다.

C++

Class와 container가 invariant와 resource를 관리합니다.

연습 문제

두 버전을 실행하고 수정하여 각 언어의 보장을 관찰하세요.

빈 상태와 용량 경계를 테스트하세요.
Cleanup을 구현하고 leak을 확인하세요.
Standard container와 비교하세요.