추상 자료형 (Abstract Data Type)

한 줄 정의: 자료구조를 내부 구현 방식이 아니라 "어떤 연산을 지원하는가"라는 관점에서 정의한 개념적 자료형입니다.

쉽게 풀면

자동차를 운전할 때 우리는 핸들을 돌리고 페달을 밟을 뿐, 엔진 내부에서 실린더가 어떻게 움직이는지는 몰라도 운전할 수 있습니다. "가속한다", "멈춘다", "방향을 바꾼다"는 조작(연산)만 알면 되고, 그 안이 가솔린 엔진이든 전기 모터든 상관없습니다. 추상 자료형(ADT)도 마찬가지입니다. 예를 들어 "스택"이라는 추상 자료형은 "데이터를 넣는다(push)"와 "가장 최근에 넣은 데이터를 꺼낸다(pop)"라는 연산만 정의할 뿐, 그 안을 배열로 구현했는지 연결 리스트로 구현했는지는 규정하지 않습니다. 즉 ADT는 "무엇을 할 수 있는가"에 대한 설계도이고, 실제 자료구조는 그 설계도를 코드로 구현한 결과물입니다.

왜 중요한가

ADT는 소프트웨어를 "무엇을 하는가"와 "어떻게 구현하는가"로 분리해 주기 때문에, 대규모 시스템 설계나 알고리즘 논문에서 구현 세부사항 없이도 알고리즘의 정확성과 복잡도를 논의할 수 있게 해 줍니다. 특히 시스템 소프트웨어, 컴파일러, 분산 시스템 분야의 논문에서는 새로운 자료구조를 제안할 때 먼저 그 ADT의 연산 인터페이스를 정의하고, 이후 구현을 다양한 방식으로 비교하는 서술 방식이 흔히 쓰입니다. 이런 관점은 모듈 간 결합도를 낮추는 소프트웨어 공학의 원칙과도 직접 연결되며, 형식적 명세(specification)와 검증(verification) 연구의 기초 개념이기도 합니다.

핵심 정리

추상 자료형(ADT)은 값의 집합과 연산, 그 연산이 만족해야 하는 규칙으로 자료형을 정의합니다. 내부 표현은 정의의 일부가 아닙니다.
1974년 리스코프와 질레스가 프로그래밍 맥락에서 제안했고, 정의와 구현을 분리해 구현을 바꿔도 사용하는 코드가 영향을 받지 않게 하는 것이 목적입니다.
ADT 정의는 인터페이스(어떤 연산이 있는가)와 행동 규칙(연산들 사이의 관계)으로 이루어집니다. 규칙의 예: 스택에서 push 뒤에 top을 하면 방금 넣은 값이 나옵니다.
자료구조(배열, 연결 리스트 등)는 ADT를 실제로 만드는 구현입니다. 하나의 ADT에 여러 구현이 있을 수 있습니다.

예시로 보기

스택과 큐는 연산 이름이 비슷하지만 규칙이 달라 서로 다른 ADT입니다.

ADT	핵심 연산	규칙	구현 후보
스택	push, pop, top	마지막에 넣은 것이 먼저 나옴(LIFO)	배열, 연결 리스트
큐	enqueue, dequeue, front	먼저 넣은 것이 먼저 나옴(FIFO)	원형 배열, 연결 리스트

사용하는 쪽은 규칙만 알면 되고, 내부가 배열인지 연결 리스트인지는 몰라도 됩니다.

자주 하는 오해

오해	바로잡기
ADT와 자료구조는 같은 말이다.	ADT는 행동의 명세이고 자료구조는 구체적 표현입니다.
ADT는 클래스나 인터페이스와 똑같다.	언어의 인터페이스는 연산 이름과 형만 정하는 경우가 많고, ADT는 연산 사이의 규칙까지 포함합니다.
같은 ADT면 성능도 같다.	구현에 따라 연산의 시간 복잡도가 달라집니다.
ADT는 객체지향에서만 쓴다.	개념은 언어와 무관하며, 대수적 명세로 수학적으로 다루기도 합니다.

논문에서는 이렇게 쓰입니다

실제 논문에서

이 용어를 직접 쓴 국내 논문 문장을 아직 수집하지 못했습니다. 수집되는 대로 출처와 함께 싣겠습니다.

예시 문장

아래는 용어의 쓰임을 보여 주려고 만든 예시로, 실제 논문에서 가져온 문장이 아닙니다.

"본 연구에서 제안한 작업 스케줄러는 우선순위 큐라는 추상 자료형의 인터페이스만을 사용하도록 설계되어, 내부 구현을 배열 기반 힙에서 피보나치 힙으로 교체하더라도 상위 모듈의 코드 변경 없이 동작한다."

이 문장은 "스케줄러가 '우선순위대로 꺼낸다'는 기능(연산)에만 의존하도록 만들었기 때문에, 그 기능을 실제로 구현하는 내부 방식이 바뀌어도 스케줄러 코드는 그대로 쓸 수 있다"는 뜻입니다. 이처럼 ADT는 구현과 사용을 분리해 소프트웨어를 유연하게 만드는 데 핵심적인 역할을 합니다.

"제안하는 분산 키-값 저장소는 맵이라는 추상 자료형을 노드 간 파티셔닝 방식과 무관하게 동일한 연산 집합(get, put, delete)으로 노출함으로써, 파티셔닝 전략을 실험적으로 교체해 가며 성능을 비교할 수 있도록 하였다."

여기서는 분산 시스템 연구에서 ADT가 어떻게 쓰이는지를 보여줍니다. 사용자나 상위 모듈이 보는 연산(get, put, delete)은 동일하게 유지하면서, 내부적으로 데이터를 여러 노드에 나누는 방식만 바꿔가며 실험할 수 있다는 뜻입니다.

"타입 시스템 관점에서 본 큐 ADT는 push와 pop 연산이 만족해야 하는 대수적 성질(예: 선입선출 순서 보존)을 공리로 명시하며, 본 논문의 정적 검증기는 이 공리를 이용해 구현 코드가 명세를 위반하지 않음을 자동으로 증명한다."

프로그래밍 언어·검증 분야 논문에서는 ADT를 단순한 인터페이스가 아니라 연산이 지켜야 할 규칙(공리)의 집합으로 다루기도 합니다. 이 문장은 그런 공리를 바탕으로 구현이 명세대로 동작하는지 자동으로 검증했다는 의미입니다.

조금 더 깊게 보면

ADT를 더 엄밀하게 다루는 논문에서는 연산의 동작을 자연어가 아니라 대수적 명세(algebraic specification)나 사전조건/사후조건(pre/postcondition) 형태로 정의합니다. 예를 들어 스택의 경우 "push한 직후 pop을 하면 방금 push한 값이 나온다"처럼 연산들 사이의 관계를 공리로 표현하는 방식입니다. 또한 같은 ADT라도 구현에 따라 각 연산의 시간 복잡도가 달라질 수 있기 때문에, 논문에서는 흔히 "이 ADT를 어떤 자료구조로 구현했을 때 각 연산이 상각(amortized) 또는 최악의 경우(worst-case) 기준으로 어느 정도의 시간이 걸리는가"를 함께 명시합니다. 이런 명세와 복잡도 분석이 갖춰져야 비로소 서로 다른 구현을 공정하게 비교할 수 있습니다.

주의할 점

추상 자료형과 자료구조를 같은 말로 혼동하기 쉽지만 엄밀히는 다른 층위의 개념입니다. 예를 들어 스택과 큐은 "넣고 꺼내는 순서(스택은 LIFO, 큐는 FIFO)"라는 연산 규칙을 정의한 ADT이고, 이를 배열로 구현하든 연결 리스트로 구현하든 그 결과물이 구체적인 자료구조입니다. 하나의 ADT가 여러 가지 자료구조로 구현될 수 있다는 점이 핵심입니다.

헷갈리기 쉬운 용어

용어	무엇을 말하나	예
추상 자료형	연산과 규칙으로 정한 행동 명세	스택
자료구조	메모리 위의 구체적 표현	배열, 연결 리스트
알고리즘	문제를 푸는 절차	정렬

참고 문헌

Liskov, B., & Zilles, S. (1974). Programming with abstract data types. ACM SIGPLAN Notices, 9(4), 50–59.
Cardelli, L., & Wegner, P. (1985). On understanding types, data abstraction, and polymorphism. ACM Computing Surveys, 17(4), 471–523.

표의 기준값은 위 문헌에 근거한 관례이며, 분야·학술지마다 다른 기준을 쓸 수 있습니다.

개념 계통

하위 개념

분야 전체 개념 지도 보기 →