[자료구조] 01_자료구조 개요와 분류

자료구조는 데이터를 아무렇게나 저장하는 방법이 아니라, 처리 목적에 맞게 데이터를 배치하고 관리하는 방식이다. 같은 데이터라도 어떤 구조에 넣느냐에 따라 탐색, 삽입, 삭제의 비용이 달라진다.

이 과목에서는 어려운 용어를 앞세우기보다, 다음 흐름으로 보는 편이 이해하기 쉽다.

1. 이 구조가 어떤 상황에 필요한지 본다.
2. C언어로 내부 동작을 직접 구현한다.
3. C++에서는 같은 구조를 직접 구현하거나 STL로 어떻게 쓰는지 비교한다.

---

1. 자료구조의 기본 분류

분류	관계	대표 구조
단순 구조	하나의 값	정수, 실수, 문자
선형 구조	1:1 관계	배열, 연결 리스트, 스택, 큐
비선형 구조	1:N 또는 N:M 관계	트리, 그래프
파일 구조	보조기억장치 저장	순차 파일, 색인 파일

 

선형 구조는 데이터가 한 줄로 이어지는 구조다. 배열과 연결 리스트는 일반적인 선형 리스트이고, 스택과 큐는 삽입/삭제 위치에 제한을 둔 선형 구조다.

비선형 구조는 데이터가 가지처럼 갈라지거나 서로 복잡하게 연결된다. 트리는 계층 구조를 표현하고, 그래프는 정점 사이의 자유로운 연결 관계를 표현한다.

---

2. 자료구조를 볼 때의 기준

자료구조를 고를 때는 이름보다 연산을 먼저 봐야 한다.

질문	관련 구조
인덱스로 바로 접근해야 하는가?	배열, vector
중간 삽입과 삭제가 잦은가?	연결 리스트, list
최근에 넣은 데이터를 먼저 꺼내는가?	스택, stack
먼저 넣은 데이터를 먼저 꺼내는가?	큐, queue
부모-자식 관계가 필요한가?	트리
여러 정점의 연결 관계가 필요한가?	그래프

 

즉, 자료구조 선택은 "어떤 구조가 제일 좋은가"가 아니라 내 프로그램에서 어떤 연산이 가장 자주 일어나는가를 기준으로 판단한다.

---

3. 주요 연산과 비용

구조	접근/탐색	삽입/삭제	특징
배열 리스트	인덱스 접근 O(1)	중간 삽입/삭제 O(n)	연속 저장, 크기 관리 필요
연결 리스트	순차 접근 O(n)	위치를 알고 있으면 O(1)	포인터 연결, 동적 크기
스택	top만 접근	push/pop O(1)	LIFO
큐	front/rear 접근	enqueue/dequeue O(1)	FIFO
이진 탐색 트리	평균 O(log n)	평균 O(log n)	균형이 깨지면 O(n)
그래프	표현 방식에 따라 다름	표현 방식에 따라 다름	정점과 간선 관계

---

4. C 구현과 C++ 구현을 같이 보기

C로 내부 구조를 직접 구현하는 것이 중요하다. 배열 크기, 현재 개수, 포인터, 노드 연결을 직접 다루면서 자료구조가 실제로 어떻게 움직이는지 확인할 수 있기 때문이다.

반면 C++에서는 같은 구조를 직접 클래스로 구현할 수도 있고, 표준 라이브러리인 STL을 사용할 수도 있다. 블로그에서는 두 관점을 같이 보여주는 방향으로 정리한다.

자료구조	C 구현 핵심	C++ 직접 구현 또는 STL
배열 리스트	배열 + 현재 개수 iCount	vector
연결 리스트	struct Node, malloc, free, pNext	list, forward_list, 클래스 구현
스택	배열 + iTop	stack, 클래스 구현
큐	배열 + iFront, iRear, iCount	queue, deque, 클래스 구현
트리	노드 + 왼쪽/오른쪽 포인터	노드 클래스, set, map
그래프	인접 행렬, 인접 리스트	vector, queue, set, map 조합

 

C로 보는 스택의 뼈대

#define MAX_SIZE 100

int iStack[MAX_SIZE];
int iTop;

iTop = -1;

 

C++ STL로 보는 스택의 사용

#include <iostream>
#include <stack>
using namespace std;

int main()
{
    stack<int> stNumbers;

    stNumbers.push(10);
    stNumbers.push(20);
    stNumbers.push(30);

    cout << stNumbers.top() << endl;
    stNumbers.pop();

    cout << stNumbers.top() << endl;

    return 0;
}

 

C 구현은 내부 원리를 보기 좋고, C++ STL은 실전 코드에서 안정적으로 쓰기 좋다. 이후 문서들도 이 방식으로 C 구현과 C++ 예제를 함께 비교한다.

---

5. 자료구조 선택 예시

 

상황	자주 하는 연산	적합한 구조
학생 100명의 37번째 자료 바로 보기	인덱스 접근	배열
중간에 자료를 자주 넣고 빼는 목록	삽입/삭제	연결 리스트
되돌리기 기능	최근 작업 처리	스택
주문 대기열	먼저 들어온 순서 처리	큐
폴더 구조	부모-자식 관계	트리
지하철 노선도	여러 정점의 연결	그래프

---

오늘 정리

• 자료구조는 데이터 저장 방식과 연산 비용을 함께 보는 과목이다.
• C 구현은 배열, 포인터, 노드 연결처럼 내부 동작을 직접 확인하기 좋다.
• C++ 구현은 직접 클래스로 만들 수도 있고, STL 컨테이너로 사용할 수도 있다.
• 앞으로는 각 자료구조를 C 코드와 C++ 코드로 나란히 비교하면서 정리한다.

---