추상 자료형

추상 자료형은 스택 같은 자료형으로 무엇을 할 수 있는지만 정해 둡니다. 넣은 값을 안에 어떻게 늘어놓을지는 감춥니다. 스택이라면 넣고 빼는 규칙만 정하고 안쪽 모양은 정하지 않습니다. 그래서 쓰는 코드를 고치지 않고 안쪽을 바꿔 끼울 수 있습니다.

상세

자동차를 몰 때 손발이 닿는 것은 운전대와 페달뿐입니다. 보닛 아래에 휘발유 엔진이 있든 전기 모터가 있든 가속 페달을 밟으면 차가 나갑니다. 브레이크를 밟으면 섭니다. 차를 바꿔 타도 운전을 새로 배우지 않습니다.

추상 자료형에서 운전대와 페달은 연산입니다. 보닛 아래는 값을 담는 방식입니다.

이 절은 추상 자료형이 무엇을 정하고 무엇을 비워 두는지부터 봅니다. 그다음 스택과 큐를 견주어 규칙이 자료형을 가른다는 것을 봅니다. 이어서 값을 담는 방식(자료구조)과 어떻게 갈리는지 따라갑니다. 끝으로 자바 컬렉션에서 이 구분이 코드로 어떻게 보이는지 확인합니다.

자료형과 추상 자료형

자료형은 값의 종류와 그 값에 할 수 있는 일을 묶어 부르는 이름입니다. 정수형의 값은 정수입니다. 정수형으로 할 수 있는 일은 더하기, 빼기, 크기 비교 같은 것입니다. 프로그래밍 언어는 자료형을 보고 어떤 일이 허용되는지 가립니다.

추상 자료형은 이 둘 가운데 「할 수 있는 일」만 정해 둔 자료형입니다. 영어 이름을 줄여 ADT(Abstract Data Type, 추상 자료형)라고도 적습니다. 넣은 값을 메모리에 어떻게 늘어놓을지는 정의에 들어 있지 않습니다.

할 수 있는 일 하나하나를 연산이라고 부릅니다. 추상 자료형의 정의에는 연산마다 이름과 받는 값, 돌려주는 값이 들어갑니다. 스택이라면 연산은 넣기, 빼기, 맨 위 보기, 비었나 묻기 넷입니다.

정의에는 연산이 지킬 규칙도 들어갑니다. 스택의 규칙은 「빼기는 가장 나중에 넣은 값을 돌려준다」입니다. 1, 2, 3을 차례로 넣고 세 번 빼면 3, 2, 1 순서로 나옵니다.

연산과 규칙을 합친 것을 계약이라고 부릅니다. 자료형을 쓰는 쪽과 만드는 쪽은 이 계약만 보고 일을 나눕니다.

규칙이 가르는 스택과 큐

연산의 이름만으로는 추상 자료형이 정해지지 않습니다. 이름이 같아도 규칙이 다르면 다른 자료형입니다. 스택과 큐를 나란히 놓으면 이것이 보입니다.

큐는 먼저 넣은 값이 먼저 나오는 추상 자료형입니다. 요청을 도착한 순서대로 처리하는 작업 대기열이 큐의 흔한 쓰임입니다. 스택과 큐는 연산의 생김새가 거의 같습니다.

표에서 두 자료형이 갈리는 줄은 빼기 하나입니다. 받는 값과 돌려주는 값의 타입은 같습니다. 어느 값을 돌려주느냐는 규칙만 다릅니다. 그래서 추상 자료형을 정의할 때 규칙은 연산 목록만큼 무겁게 적습니다.

안쪽을 감추는 이유

추상 자료형 없이 스택을 쓴다고 해 봅시다. 배열은 값을 한 줄로 붙여 두고 칸 번호로 찾는 모양입니다. 쓰는 코드가 이 칸 번호를 직접 만지며 스택을 흉내 냅니다. 그러면 스택이 곧 그 배열입니다. 나중에 안쪽을 다른 모양으로 바꾸려면 칸 번호를 만지던 줄을 모두 찾아 고쳐야 합니다.

안쪽을 감추면 이 일이 한 곳의 코드 안에서 끝납니다. 쓰는 코드는 연산만 부르므로 안쪽이 무엇으로 바뀌었는지 모릅니다. 안쪽을 밖에서 못 만지게 막는 이 방식을 정보 은닉이라고 부릅니다.

감춤은 규칙도 지켜 줍니다. 밖에서 배열 한가운데 칸을 고칠 수 있으면 「가장 나중에 넣은 값을 돌려준다」는 규칙이 쉽게 깨집니다. 연산으로만 들어올 수 있게 하면 규칙을 깰 수 있는 코드가 연산의 안쪽으로 좁혀집니다.

추상 자료형과 자료구조

추상 자료형은 「무엇을 할 수 있나」를 정합니다. 「어떻게 담나」는 자료구조가 정합니다. 자료구조는 값을 메모리에 늘어놓는 방식입니다.

자료구조 둘을 예로 듭니다. 배열은 값을 빈틈없이 한 줄로 붙여 둡니다. 연결 리스트는 값마다 다음 값의 위치를 적어 두고 사슬처럼 잇습니다.

추상 자료형 하나를 여러 자료구조로 만들 수 있습니다. 스택을 배열로 만들면 맨 끝 칸을 맨 위로 씁니다. 연결 리스트로 만들면 사슬의 첫 칸을 맨 위로 씁니다. 쓰는 코드에서 보면 두 스택은 똑같이 움직입니다.

flowchart TD
    U["쓰는 코드"] --> S["스택의 계약 · 넣기 · 빼기 · 맨 위 보기"]
    S --> A["배열로 만든 스택"]
    S --> L["연결 리스트로 만든 스택"]

쓰는 코드에서 나간 화살표는 계약까지만 닿습니다. 그 아래에 두 구현 중 무엇이 붙어 있든 쓰는 코드는 같은 연산을 부릅니다.

거꾸로 자료구조 하나가 여러 추상 자료형을 받치기도 합니다. 배열 하나로 스택도 만들고 큐도 만듭니다. 그래서 「스택을 쓴다」와 「배열을 쓴다」는 다른 선택을 말합니다. 앞은 계약을 고른 말입니다. 뒤는 구현을 고른 말입니다.

자주 만나는 추상 자료형과 그 계약의 요점은 이렇습니다.

어느 줄에도 배열이나 연결 리스트 같은 모양이 나오지 않습니다. 각 자료형을 무엇으로 만드는지는 그 자료형의 항목이 다룹니다.

같은 계약과 다른 비용

추상 자료형은 연산이 무엇을 하는지는 정합니다. 연산 한 번에 시간이 얼마나 걸리는지는 대개 정하지 않습니다. 걸리는 시간은 어느 자료구조로 만들었느냐가 정합니다.

걸리는 시간은 흔히 빅오 표기법으로 적습니다. 값이 n 개 들어 있을 때, 연산 한 번의 시간이 n 에 따라 어떻게 늘어나는지를 적는 방법입니다. O(1)은 n 이 늘어도 시간이 거의 일정하다는 뜻입니다. O(n)은 n 에 비례해 늘어난다는 뜻입니다.

리스트를 배열로 만든 것과 연결 리스트로 만든 것을 견주면 이렇습니다.

몇 번째 값을 꺼낼 때 배열은 칸 번호로 위치를 바로 계산합니다. 연결 리스트는 첫 칸부터 사슬을 따라 하나씩 세어 가야 합니다. 맨 앞에 넣을 때는 반대입니다. 배열은 뒤의 값을 한 칸씩 밀어야 합니다. 연결 리스트는 새 칸을 사슬 앞에 걸기만 합니다.

그래서 추상 자료형을 고르는 일과 구현을 고르는 일은 따로입니다. 필요한 연산으로 추상 자료형을 먼저 고릅니다. 그 연산 가운데 무엇을 자주 부르는지로 구현을 고릅니다. 표준 라이브러리 문서가 구현마다 연산의 시간을 따로 적어 두는 까닭이 이것입니다.

자바 컬렉션에서 보는 추상 자료형

백엔드 코드에서 추상 자료형을 가장 자주 만나는 곳은 언어의 컬렉션 라이브러리입니다. 자바에서는 추상 자료형이 interface 로 나옵니다. 자료구조는 그 인터페이스를 구현한 클래스로 나옵니다.

List 는 리스트의 계약입니다. ArrayList 는 그 계약을 배열로 지킨 구현입니다. LinkedList 는 같은 계약을 연결 리스트로 지킨 구현입니다.

List<String> names = new ArrayList<>();
names.add("kim");
names.add("lee");
String s = names.get(1);  // "lee"

변수 names 의 타입을 List 로 적었습니다. 그래서 뒤의 코드는 ArrayList 에만 있는 기능을 못 씁니다. 구현을 바꾸고 싶으면 첫 줄의 new ArrayList<>() 를 new LinkedList<>() 로 고치면 됩니다. 나머지 줄은 손대지 않아도 같은 값을 냅니다.

바뀌지 않는 것은 결과뿐입니다. get(1) 은 ArrayList 에서 바로 끝납니다. LinkedList 에서는 앞에서부터 사슬을 따라갑니다. 값이 수십만 개인 리스트를 반복문으로 돌며 get(i) 를 부르면 이 차이가 크게 벌어집니다.

계약에 없는 성질

계약에 적히지 않은 성질은 구현마다 다를 수 있습니다. Map 은 키로 값을 찾는 계약입니다. 키를 어떤 순서로 돌려줄지는 계약에 넣지 않습니다.

HashMap 은 해시테이블로 만든 구현입니다. 해시테이블은 키를 숫자로 바꾸고 그 숫자로 칸을 바로 찾는 자료구조입니다. 칸의 순서가 키의 순서와 무관하므로 HashMap 은 키 순서를 보장하지 않습니다.

TreeMap 은 키를 늘 정렬된 상태로 붙들어 두는 자료구조로 만든 구현입니다. 그래서 작은 키부터 돌려줍니다.

Map<String, Integer> m = new TreeMap<>();
m.put("b", 2);
m.put("a", 1);
m.keySet();  // [a, b]

b 를 먼저 넣었는데도 a 가 먼저 나왔습니다. 같은 코드를 HashMap 으로 돌리면 어느 키가 먼저 나올지 정해져 있지 않습니다. 순서에 기대는 코드는 HashMap 위에서 우연히 맞게 돌기도 합니다. 그런 코드가 값이 늘어난 뒤에 어긋나는 일이 이 틈에서 생깁니다.

인터페이스가 검사하지 못하는 규칙

자바의 interface 는 연산의 이름과 받는 값, 돌려주는 값만 적습니다. 컴파일러는 구현 클래스가 이 모양을 갖췄는지만 확인합니다. 「빼기는 가장 나중에 넣은 값을 돌려준다」 같은 규칙은 타입으로 적을 수 없습니다.

그래서 규칙은 문서와 테스트가 지킵니다. 인터페이스의 설명 글이 규칙을 적습니다. 구현마다 같은 테스트를 돌려 그 규칙을 지키는지 확인합니다. 모양만 맞추고 규칙을 어긴 구현은 컴파일은 되지만, 쓰는 코드에 틀린 결과를 돌려줍니다.

계약으로 적을 때와 구현을 드러낼 때

변수와 필드, 매개변수, 반환 타입은 추상 자료형으로 적는 것이 흔한 습관입니다. 구현은 new 로 새로 만드는 줄에서 한 번만 고릅니다. 그러면 구현을 바꿀 때 고칠 줄이 한 곳으로 모입니다.

구현에만 있는 성질에 기대야 할 때는 그 성질을 타입에 드러냅니다. 키 순서가 필요한 코드라면 Map 대신 순서까지 계약에 넣은 SortedMap 같은 인터페이스를 적습니다. 계약에 없는 성질을 조용히 믿으면, 읽는 사람은 그 코드가 순서에 기댄다는 것을 모릅니다.

걸리는 시간이 중요한 경로에서는 구현을 알고 씁니다. 추상 자료형은 결과를 가려 주지만 비용까지 가려 주지는 않습니다. 앞에서 본 get(i) 처럼, 같은 호출 한 줄이 구현에 따라 전혀 다른 시간을 씁니다.

관련 항목

추상 자료형의 하위 종류

스택 · 큐 · 리스트 · 집합 · 맵 · 우선순위 큐 · 덱 · 멀티셋 · 시퀀스 · 그래프

추상 자료형을 구현하는 자료구조

자료구조 · 배열 · 동적 배열 · 연결 리스트 · 해시테이블 · 이진 탐색 트리 · 균형 이진 탐색 트리 · 힙 · 원형 버퍼

추상 자료형이 기대는 설계 원칙

정보 은닉 · 캡슐화 · 추상화 · 불변식 · 계약에 의한 설계 · 새는 추상화

추상 자료형을 코드로 적는 언어 장치

인터페이스 · 추상 클래스 · 제네릭 · 타입 클래스 · 모듈 시스템 · Java 컬렉션 프레임워크

추상 자료형이 속하는 상위 분류

데이터 타입 · 타입 시스템 · 컬렉션 · 컨테이너 (자료구조)

추상 자료형 구현의 비용을 재는 지표

시간 복잡도 · 공간 복잡도 · 빅오 표기법 · 상각 분석