C와 C++의 단일 연결 리스트
이 레슨에서는 C와 C++로 단일 연결 리스트를 만들고, 돌아보고, 해제합니다.
소개
단일 연결 리스트(singly linked list)는 노드(nodes)로 이루어지며, 각 노드에는 값과 다음 노드를 가리키는 포인터가 있습니다. 배열과 달리 노드가 메모리에서 나란히 있을 필요가 없으므로, 다른 요소를 옮기지 않고도 요소를 추가할 수 있습니다.
핵심 정리
- 연산을 작성하기 전에 항상 참이어야 하는 조건(불변식)을 정하세요.
- 구조가 비어 있을 때, 가득 찼을 때, 메모리 할당에 실패했을 때를 처리하세요.
- 각 연산의 복잡도와 메모리 관리를 함께 따져 보세요.
동작 원리 보기
앞이나 뒤에 노드를 추가하고, 노드를 클릭하면 삭제할 수 있습니다. 재생을 누르면 head부터 NULL까지 next 포인터를 따라갑니다.
C와 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 3C++
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 3C와 C++ 비교
C 버전에서는 각 노드를 malloc으로 할당하고, 마지막에 리스트 전체를 돌면서 노드마다 free를 호출해야 합니다. C++ 버전에서는 노드를 std::unique_ptr로 연결하므로, 첫 번째 노드가 소멸하면 그 뒤의 사슬 전체가 자동으로 해제됩니다.
C
데이터(struct)와 연산이 분리되어 있고, 메모리는 직접 할당하고 해제합니다.
C++
클래스와 컨테이너가 데이터의 일관성을 지키고 자원을 스스로 관리합니다.
연습 문제
두 버전을 모두 실행한 다음 코드를 바꿔 보면서 각 언어가 주는 안전성의 차이를 살펴보세요.
- 비어 있는 상태와 최대 용량에 이른 순간에 대한 테스트를 추가해 보세요.
- 메모리 해제 코드를 작성하고 누수가 없는지 확인해 보세요.
- 표준 라이브러리의 같은 역할을 하는 컨테이너와 복잡도를 비교해 보세요.
챌린지로 연습하기
이 레슨에서 배운 내용으로 실제 문제를 풀어 보세요. 모든 챌린지는 브라우저에서 실행되며 즉시 테스트와 AI 리뷰를 받을 수 있습니다.
모든 챌린지