자료구조 응용 (연결리스트/스택/큐)
배열은 정말 편리하지만 한 가지 아쉬운 점이 있습니다. 크기를 미리 정해야 하고, 중간에 원소를 넣거나 빼려면 나머지 원소들을 한 칸씩 밀거나 당겨야 한다는 점입니다. 이런 불편함을 해결하기 위해 등장한 것이 연결리스트이고, 연결리스트를 응용하면 스택과 큐라는 아주 유용한 자료구조도 쉽게 만들 수 있습니다. 오늘은 이 세 가지를 직접 코드로 구현하면서 개념을 익혀보겠습니다.
연결리스트란 무엇일까요
연결리스트(linked list)는 데이터를 담은 노드(node)들이 서로를 화살표처럼 가리키며 이어진 구조입니다. 배열처럼 메모리가 한 줄로 붙어 있는 게 아니라, 각 노드가 “다음 노드의 주소”를 들고 있어서 어디에 있든 서로 연결될 수 있습니다. 노드 하나는 보통 실제 값을 담는 필드와, 다음 노드를 가리키는 포인터 필드로 구성됩니다. 새로운 데이터를 추가할 때는 배열처럼 전체를 밀 필요 없이, 그냥 포인터 연결만 바꿔주면 되기 때문에 삽입과 삭제가 훨씬 가볍습니다.
#include <stdio.h>
#include <stdlib.h>
typedef struct Node {
int data;
struct Node *next;
} Node;
Node *createNode(int value) {
Node *newNode = (Node *)malloc(sizeof(Node));
newNode->data = value;
newNode->next = NULL;
return newNode;
}
void printList(Node *head) {
Node *cur = head;
while (cur != NULL) {
printf("%d -> ", cur->data);
cur = cur->next;
}
printf("NULL\n");
}
int main(void) {
Node *head = createNode(10);
head->next = createNode(20);
head->next->next = createNode(30);
printf("연결리스트 내용: ");
printList(head);
Node *cur = head;
while (cur != NULL) {
Node *temp = cur;
cur = cur->next;
free(temp);
}
return 0;
}
실행 결과는 다음과 같습니다.
연결리스트 내용: 10 -> 20 -> 30 -> NULL
createNode 함수는 malloc으로 노드 하나만큼의 메모리를 확보하고 값을 채운 뒤, 아직 다음 노드가 없으니 next를 NULL로 초기화해서 반환합니다. head->next = createNode(20) 처럼 이어 붙이면 10을 가리키던 노드가 20을 가리키는 노드를 가리키게 되고, 그다음 30까지 이어져서 하나의 사슬이 완성됩니다. printList는 head부터 시작해서 next가 NULL이 될 때까지 따라가며 값을 출력하는데, 이 패턴은 연결리스트를 다룰 때 가장 기본이 되는 순회 방식입니다. 마지막에는 동적으로 할당한 노드들을 하나씩 free로 해제해서 메모리 누수를 막아줍니다.
스택으로 후입선출 구조 만들기
스택(stack)은 “가장 나중에 넣은 것이 가장 먼저 나온다”는 후입선출(LIFO) 구조입니다. 접시를 쌓아 올렸다가 위에서부터 꺼내 쓰는 모습을 떠올리면 이해가 쉽습니다. 연결리스트를 활용하면 스택을 아주 간단하게 구현할 수 있는데, 항상 맨 앞(head) 쪽에서만 데이터를 넣고 빼면 됩니다.
#include <stdio.h>
#include <stdlib.h>
typedef struct StackNode {
int data;
struct StackNode *next;
} StackNode;
StackNode *top = NULL;
void push(int value) {
StackNode *newNode = (StackNode *)malloc(sizeof(StackNode));
newNode->data = value;
newNode->next = top;
top = newNode;
}
int pop(void) {
if (top == NULL) {
printf("스택이 비어 있습니다.\n");
return -1;
}
StackNode *temp = top;
int value = temp->data;
top = top->next;
free(temp);
return value;
}
int main(void) {
push(1);
push(2);
push(3);
printf("pop: %d\n", pop());
printf("pop: %d\n", pop());
printf("pop: %d\n", pop());
printf("pop: %d\n", pop());
return 0;
}
실행 결과는 다음과 같습니다.
pop: 3
pop: 2
pop: 1
스택이 비어 있습니다.
pop: -1
push는 새 노드를 만들어서 next가 현재 top을 가리키게 한 다음, top 자체를 새 노드로 바꿔치기합니다. 이렇게 하면 항상 맨 마지막에 넣은 값이 top이 되어 가장 먼저 꺼내지는 후입선출 구조가 만들어집니다. pop은 반대로 top이 가리키던 노드의 값을 꺼내고, top을 그다음 노드로 옮긴 뒤 원래 노드를 해제합니다. 1, 2, 3 순서로 넣었지만 꺼낼 때는 3, 2, 1 순서로 나오는 것이 바로 스택의 핵심 동작입니다.
큐로 선입선출 구조 만들기
큐(queue)는 스택과 반대로 “먼저 넣은 것이 먼저 나온다”는 선입선출(FIFO) 구조입니다. 은행 창구에서 줄을 서서 순서대로 처리되는 모습과 같습니다. 큐를 연결리스트로 구현할 때는 앞(front)과 뒤(rear)를 따로 관리해서, 넣는 쪽과 빼는 쪽을 분리하는 것이 포인트입니다.
#include <stdio.h>
#include <stdlib.h>
typedef struct QueueNode {
int data;
struct QueueNode *next;
} QueueNode;
QueueNode *front = NULL;
QueueNode *rear = NULL;
void enqueue(int value) {
QueueNode *newNode = (QueueNode *)malloc(sizeof(QueueNode));
newNode->data = value;
newNode->next = NULL;
if (rear == NULL) {
front = rear = newNode;
return;
}
rear->next = newNode;
rear = newNode;
}
int dequeue(void) {
if (front == NULL) {
printf("큐가 비어 있습니다.\n");
return -1;
}
QueueNode *temp = front;
int value = temp->data;
front = front->next;
if (front == NULL) {
rear = NULL;
}
free(temp);
return value;
}
int main(void) {
enqueue(100);
enqueue(200);
enqueue(300);
printf("dequeue: %d\n", dequeue());
printf("dequeue: %d\n", dequeue());
printf("dequeue: %d\n", dequeue());
printf("dequeue: %d\n", dequeue());
return 0;
}
실행 결과는 다음과 같습니다.
dequeue: 100
dequeue: 200
dequeue: 300
큐가 비어 있습니다.
dequeue: -1
enqueue는 새 노드를 항상 rear 뒤쪽에 붙이고 rear를 그 노드로 갱신합니다. 큐가 비어 있던 상태라면 front와 rear 모두 새 노드를 가리키게 초기화합니다. dequeue는 front가 가리키는 노드를 꺼내고 front를 다음 노드로 옮기는데, 만약 그 결과 front가 NULL이 되면 큐가 완전히 비었다는 뜻이므로 rear도 함께 NULL로 맞춰줘야 합니다. 100, 200, 300 순서로 넣은 그대로 100, 200, 300 순서로 나오는 것이 큐의 특징입니다.
핵심 요약
- 연결리스트는 노드들이 포인터로 서로를 가리키며 이어지는 구조로, 배열과 달리 크기를 미리 정하지 않아도 되고 중간 삽입/삭제가 가볍습니다.
- 스택은 후입선출(LIFO) 구조로, 항상 맨 앞(top)에서만 데이터를 넣고 빼면 연결리스트로 쉽게 구현할 수 있습니다.
- 큐는 선입선출(FIFO) 구조로, 넣는 쪽(rear)과 빼는 쪽(front)을 분리해서 관리하면 순서를 그대로 유지할 수 있습니다.
- 세 구조 모두
malloc으로 노드를 동적으로 생성하고, 사용이 끝난 노드는 반드시free로 해제해서 메모리 누수를 막아야 합니다. - 포인터 연결만 바꿔주면 되는 구조이기 때문에, 실제 데이터 이동 없이도 삽입과 삭제를 빠르게 처리할 수 있다는 점이 이 자료구조들의 가장 큰 장점입니다.
다음 편에서는 지금까지 배운 내용을 총정리해서 실제로 활용할 수 있는 “미니 프로젝트로 마무리” 시간을 가져보겠습니다.