자료구조의 개념

Introduction

자료구조란 무엇일까요? 이 글에서는 PDT(Primitive Data Type), UDT(User-Defined Type), 그리고 ADT(Abstract Data Type)가 무엇이며, 이 세 가지가 어떻게 자료구조Data Structure라는 개념을 구성하는지 알아봅니다.

PDT — 원시 자료형

PDT(Primitive Data Type)는 프로그래밍 언어 수준에서 데이터를 담기 위한 가장 기본적인 형태의 자료형을 말한다. C를 예시로 들자면, int, char, double, float 등이 PDT에 속한다. PDT는 프로그래밍 언어를 구성하는 여러 요소 중 하나이며, 제거될 수 없다.

PDT의 핵심적인 특징은 다음과 같다.

언어에 내장되어 있다. 사용자가 별도로 정의할 필요 없이 언어 자체가 제공한다.
하드웨어와 직접 대응한다. int는 CPU 레지스터 크기에, float는 IEEE 754 부동소수점 표준에 각각 대응된다¹.
크기가 고정되어 있다. 예를 들어 C의 int는 대부분의 플랫폼에서 4바이트다.

PDT만으로는 현실 세계의 복잡한 데이터를 표현하기 어렵다. 학생 한 명의 정보를 다루려면 이름(char[]), 학번(int), 학점(double)을 하나의 단위로 묶어야 하는데, PDT만으로는 이 묶음을 표현할 수 없다. 이 한계를 해결하는 것이 UDT다.

UDT — 사용자 정의 자료형

UDT(User-Defined Type)는 C의 struct²나 C++·Java·Python 등의 class처럼, 프로그래밍 언어의 문법적 지원을 통해 사용자가 임의로 만든 자료형을 의미한다. PDT와 달리 프로그래밍 언어의 필수 요소가 아니며, 프로그래밍 언어 위에 구현된 개념에 가깝다.

/* C의 UDT 예시: 학생 구조체 */
typedef struct {
    char name[50];
    int  student_id;
    double gpa;
} Student;

위 코드에서 Student는 PDT인 char, int, double을 조합하여 만든 UDT다. UDT는 PDT들을 조합해서 새로운 자료형을 구현하는 수단이다. 담겨지는 데이터의 규칙이나 그 데이터를 다루는 연산은 UDT의 관심사가 아니다. 이 설계를 담당하는 것은 바로 ADT다.

ADT — 추상 자료형

ADT(Abstract Data Type)는 프로그래밍 언어와 독립적인 개념으로, 자료들과 그 자료들에 대한 연산을 정의한 명세specification다. "무엇을what 할 수 있는가"는 정의하지만 "어떻게how 하는가"는 정의하지 않는다. 객체지향 프로그래밍의 추상 클래스abstract class나 인터페이스interface와 밀접한 개념이다.

스택Stack의 ADT를 예로 들어보자.

ADT Stack
  데이터: 원소들의 순서 있는 모음
  연산:
    push(x)    — 원소 x를 꼭대기에 추가
    pop()      — 꼭대기 원소를 제거하고 반환
    peek()     — 꼭대기 원소를 제거하지 않고 반환
    is_empty() — 스택이 비어 있으면 True
  제약: LIFO — 가장 나중에 들어간 원소가 가장 먼저 나옴

이 명세에는 배열을 쓸지, 연결 리스트를 쓸지에 대한 언급이 전혀 없다. ADT는 구현과 분리된 계약이다. 같은 ADT라도 구현 방법에 따라 성능이 달라지며, 이것이 자료구조를 공부하는 핵심 이유 중 하나다.

같은 방식으로, Queue의 ADT는 "FIFO 정책에 따라 enqueue와 dequeue를 지원한다"로, Priority Queue의 ADT는 "우선순위가 가장 높은 원소를 먼저 꺼내는 insert와 extract-min을 지원한다"로 각각 정의된다.

자료구조의 탄생 — PDT, ADT, UDT의 관계

세 개념의 관계를 정리하면 다음과 같다.

ADT로 설계한다. 어떤 문제를 해결하기 위해, 데이터의 모습과 필요한 연산을 추상적으로 정의한다. "LIFO 정책으로 동작하는 스택이 필요하다"는 것이 ADT 수준의 결정이다.
UDT로 구현한다. ADT의 명세를 특정 프로그래밍 언어의 문법을 사용하여 코드로 옮긴다. C에서는 struct와 함수 포인터로, Python에서는 class로 구현한다.
PDT가 기초를 이룬다. 아무리 복잡한 자료구조라도, 그것을 구성하는 가장 밑바닥의 재료는 프로그래밍 언어가 제공하는 원시 자료형이다.

이 관계를 하나의 흐름으로 표현하면, ADT(무엇을) → UDT(어떻게) → PDT(무엇으로) 라는 추상화 단계가 된다. 추상적인 아이디어에서 출발하여 구체적인 코드로 내려오는 과정이 곧 자료구조를 만드는 과정이다.

ADT와 구현의 분리가 중요한 이유

같은 ADT라도 구현 방법에 따라 각 연산의 시간 복잡도³가 달라진다. Priority Queue를 예로 들면 이 차이가 명확하게 드러난다.

구현 방법	`insert`	`extract-min`
비정렬 배열	$O(1)$	$O(n)$
정렬 배열	$O(n)$	$O(1)$
이진 힙	$O(\log n)$	$O(\log n)$

"우선순위가 가장 높은 원소를 먼저 꺼낸다"라는 ADT는 동일하지만, 이진 힙 구현은 삽입과 추출 모두 $O(\log n)$ 으로 균형 잡힌 성능을 제공한다. ADT와 구현을 분리해서 생각할 수 있어야 문제에 맞는 최적의 자료구조를 선택할 수 있다.

자료구조의 분류

자료구조는 데이터 간의 관계에 따라 크게 선형 자료구조와 비선형 자료구조로 나뉜다.

선형 자료구조는 원소들이 일렬로 나열되어 각 원소가 최대 하나의 이전 원소와 하나의 다음 원소를 가진다. 배열, 연결 리스트, Stack, Queue가 여기에 속한다.

비선형 자료구조는 원소들 사이에 계층적 또는 망상 관계가 존재한다. Tree는 하나의 부모에 여러 자식이 연결되는 계층 구조이고, Graph는 임의의 노드 쌍 사이에 간선이 존재할 수 있는 가장 일반적인 구조다.

자료구조
├── 선형 자료구조
│   ├── 배열
│   ├── 연결 리스트
│   ├── Stack (LIFO)
│   └── Queue (FIFO)
│       └── Priority Queue → Heap으로 구현
└── 비선형 자료구조
    ├── Tree
    │   ├── Binary Tree
    │   ├── Heap (완전 이진 트리 + 힙 속성)
    │   └── B+ Tree
    └── Graph
        └── Connected Component

이 분류는 절대적인 것이 아니라 관점에 따라 달라질 수 있다. 예를 들어 Heap은 트리 구조이지만 배열로 구현되며, 해시 테이블은 배열과 연결 리스트를 모두 사용한다. 중요한 것은 분류 자체가 아니라, 각 자료구조가 어떤 연산을 효율적으로 지원하는가를 이해하는 것이다.

참고 자료 & 더보기

참고 자료

Kamran, A. (2022) 전문가를 위한 C (박지윤, Trans.; 1st edn). 한빛미디어.
Cormen, T. H. et al. (2022) Introduction to Algorithms. 4th edn. Cambridge, MA: MIT Press.