추상 자료형 (Abstract Data Type)

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

쉽게 풀면

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

왜 중요한가

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

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

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

이 문장은 "스케줄러가 '우선순위대로 꺼낸다'는 기능(연산)에만 의존하도록 만들었기 때문에, 그 기능을 실제로 구현하는 내부 방식이 바뀌어도 스케줄러 코드는 그대로 쓸 수 있다"는 뜻입니다. 이처럼 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)"라는 연산 규칙을 정의한 ADT이고, 이를 배열로 구현하든 연결 리스트로 구현하든 그 결과물이 구체적인 자료구조입니다. 하나의 ADT가 여러 가지 자료구조로 구현될 수 있다는 점이 핵심입니다.