자료구조
자료구조란?
자료구조란 데이터를 효율적으로 저장하고 관리하는 방법을 의미합니다. 즉, 여러 데이터를 컴퓨터 메모리에서 어떻게 배치하고, 빠르게 찾거나 수정할 수 있도록 설계하는 기술입니다. 자료구조를 잘 이해하면 프로그램의 성능과 안정성을 크게 높일 수 있습니다.
예를 들어, 학생 명단을 저장할 때 단순 배열, 연결 리스트, 트리 등 다양한 자료구조를 사용할 수 있습니다. 각각의 자료구조는 장단점과 용도가 다릅니다.
리스트와 노드
리스트는 여러 데이터를 순서대로 저장하는 자료구조입니다. 대표적으로 연결 리스트(Linked List)가 있습니다. 연결 리스트는 각각의 데이터를 노드(Node)라는 단위로 저장하며, 각 노드는 자신의 데이터와 다음 노드의 주소(포인터)를 가지고 있습니다.
노드 구조와 연결
struct Node {
int data;
struct Node* next;
};
struct Node n1 = {10, NULL};
struct Node n2 = {20, NULL};
n1.next = &n2; // n1 뒤에 n2 연결
이렇게 하면 10 → 20 순서로 데이터가 저장됩니다.
리스트의 순회(Traversal)
리스트의 모든 데이터를 차례대로 접근하려면, 첫 번째 노드부터 시작해 next 포인터를 따라가면 됩니다.
struct Node* cur = &n1;
while(cur != NULL) {
printf("%d ", cur->data);
cur = cur->next;
}
// 출력: 10 20
리스트의 삽입
새로운 노드를 중간에 삽입하려면 포인터 연결을 조정해야 합니다.
struct Node n3 = {15, NULL};
n3.next = n1.next; // n3의 다음을 n2로
n1.next = &n3; // n1의 다음을 n3로
// 결과: 10 → 15 → 20
리스트의 삭제
노드를 삭제할 때는 이전 노드의 next를 건너뛰게 연결합니다.
n1.next = n3.next; // n1의 다음을 n3의 다음(즉, n2)로
// n3는 리스트에서 빠짐
리스트의 탐색
특정 값을 가진 노드를 찾으려면 순회하면서 비교합니다.
int target = 20;
struct Node* cur = &n1;
while(cur != NULL) {
if(cur->data == target) {
printf("찾음: %d\n", cur->data);
break;
}
cur = cur->next;
}
이처럼 연결 리스트는 동적으로 크기를 늘릴 수 있고, 삽입/삭제가 빠르지만, 특정 위치에 접근하려면 처음부터 순회해야 하므로 느릴 수 있습니다.
이중 연결 리스트(더블 링크드 리스트)
단일 연결 리스트는 한 방향(다음 노드)으로만 이동할 수 있지만, 이중 연결 리스트(Doubly Linked List)는 앞뒤로 이동이 가능합니다. 각 노드는 데이터, 다음 노드 포인터(next), 이전 노드 포인터(prev)를 가집니다.
구조와 연결
struct DNode {
int data;
struct DNode* prev;
struct DNode* next;
};
struct DNode n1 = {10, NULL, NULL};
struct DNode n2 = {20, &n1, NULL};
n1.next = &n2;
이렇게 하면 10 ↔ 20 양방향으로 연결됩니다.
삽입 예시
중간에 새 노드 n3(값 15)를 삽입하려면:
struct DNode n3 = {15, &n1, &n2};
n1.next = &n3;
n2.prev = &n3;
결과: 10 ↔ 15 ↔ 20
삭제 예시
n3를 삭제하려면:
n1.next = &n2;
n2.prev = &n1;
// n3는 리스트에서 빠짐
양방향 순회
앞에서 뒤로, 뒤에서 앞으로 모두 접근할 수 있습니다.
// 앞에서 뒤로
struct DNode* cur = &n1;
while(cur) {
printf("%d ", cur->data);
cur = cur->next;
}
// 뒤에서 앞으로
cur = &n2;
while(cur) {
printf("%d ", cur->data);
cur = cur->prev;
}
이중 연결 리스트는 양방향 탐색, 삭제/삽입이 더 유연하게 가능하지만, 포인터 관리가 더 복잡해집니다.
시간복잡도
자료구조의 연산(삽입, 삭제, 탐색 등)이 얼마나 빠른지 나타내는 척도입니다. 예를 들어, 배열에서 특정 위치의 값을 읽는 것은 O(1), 연결 리스트에서 값을 찾는 것은 O(n)입니다.
| 연산 | 배열(Array) | 연결 리스트(Linked List) |
|---|---|---|
| 접근 | O(1) | O(n) |
| 삽입/삭제 | O(n) | O(1) (앞/중간에 한정) |
스택(Stack)
스택은 “접시 쌓기”처럼 마지막에 넣은 데이터가 가장 먼저 나오는(LIFO) 자료구조입니다.
- push: 데이터를 스택에 넣는 동작
- pop: 데이터를 스택에서 꺼내는 동작
예시:
#define MAX 10
int stack[MAX];
int top = -1;
void push(int x) {
if(top < MAX-1) stack[++top] = x;
}
int pop() {
if(top >= 0) return stack[top--];
return -1; // 비어있을 때
}
괄호 맞추기 예시 문자열에서 괄호가 올바르게 짝지어졌는지 확인할 때 스택을 사용합니다.
char* s = "(()())";
int top = -1;
for(int i=0; s[i]; i++) {
if(s[i] == '(') stack[++top] = '(';
else if(s[i] == ')') {
if(top < 0) { puts("NO"); return; }
top--;
}
}
if(top == -1) puts("YES"); else puts("NO");
큐(Queue)
큐는 “줄 서기”처럼 먼저 들어온 데이터가 먼저 나오는(FIFO) 자료구조입니다.
- enqueue: 데이터를 큐에 넣는 동작
- dequeue: 데이터를 큐에서 꺼내는 동작
예시:
#define MAX 10
int queue[MAX];
int front = 0, rear = 0;
void enqueue(int x) {
queue[rear++] = x;
}
int dequeue() {
if(front < rear) return queue[front++];
return -1; // 비어있을 때
}
동적 배열: 벡터(Vector)
배열은 크기가 고정되어 있지만, 동적 배열(벡터)은 필요에 따라 크기를 늘릴 수 있습니다. C에서는 직접 구현하거나, C++에서는 std::vector를 사용합니다.
예시(C에서 동적 배열):
#include <stdlib.h>
int* arr = malloc(sizeof(int) * 2); // 처음 2개 크기
int size = 2, count = 0;
// 값 추가
if(count == size) {
size *= 2;
arr = realloc(arr, sizeof(int) * size); // 크기 2배로 늘림
}
arr[count++] = 10;
이렇게 하면 데이터가 늘어날 때마다 배열 크기를 자동으로 늘릴 수 있습니다.