ADT vs Data Structure

요즘 자료구조와 알고리즘을 다시 공부하고 있다. 남들에게 쉽게 설명하기 위해 내 스스로 개념을 정리하고, 스터디에 참여하는 서로가 서로를 위한 질문 리스트를 만들어오기로 했기에 조금 더 깊게 생각하던 중 헷갈릴 수 있는 부분을 발견했다. 그걸 이 포스팅에서 한 번 짚고 넘어가볼까 한다.

통상적인 자료구조의 목차는 다음과 같다. (윤성우의 열혈 자료구조를 참고)

  1. 자료구조 + ADT
  2. 연결 리스트
  3. 스택
  4. 큐 (+ 덱)
  5. 트리
  6. 힙 (= 우선순위 큐)
  7. 정렬
  8. 탐색
  9. 해시
  10. 그래프

위 목차는 학생이 순서상으로 이해할 수 있는 순서로 구성되어 있는 것이지 모두 같은 Dimension의 내용이 아니다. 이 Dimension을 “내가 임의로” 나눠보자면 개념적 자료구조와 구현적 자료구조 두 가지다. 개념적인 자료구조는 List, Stack, Queue, Deque, Set, Map 등이 있고, 구현적 자료구조는 Array, Linked List, Tree, Graph, HashTable 등이 있다. 실제로 자료구조를 지칭할 때 이 둘을 크게 구분짓지 않고 사용하는데 왜 굳이 이렇게 나눠본걸까?

그저 당신이 알던 “ADT”를 “개념적 자료구조”로 바꿔 말한 것일 뿐인데?

예를 들어보자. 가장 기본적인 ADT인 Stack의 push와 pop은 각각 O(1)의 시간복잡도를 갖는다. 보통, Array 또는 Linked List로 구현한다. 하지만, 내부적으로 구현이 Array든, Linked List든, Tree든, Stack의 unit-test를 통과한다면 그것은Stack이다. 그저 이성적인 사고를 할 수 있는 개발자들이기에 그렇게 하지 않을뿐이다.

LeetCode를 풀다 보면, Stack을 써서 Queue를 구현하는 문제가 있다. (이하 스포) 풀어보면 알겠지만 두 개의 Stack을 이용해서 Queue를 구현하는 것이다. 그냥 간단한 Linked List를 사용하지 않았지만 그것은 Queue다.

이번엔 조금 더 코드레벨로 예를 들어보자. 우리가 Java에서 매우 자주 사용하는 Map, Set의 내부 구현이 어떤걸까? 정답은 당신이 사용한 클래스에 따라 다르다. 당신이 주로 HashSet을 사용한다면 내부 구현은 HashTable이다. 당신이 주로 TreeSet을 사용한다면 내부 구현은 Tree다. ADT와 (implementation-level) Data Structure는 다르다. 심지어 간단한 List도 LinkedList, ArrayList 두 가지 구현체가 존재하니까. Graph는? Adjacent Array 또는 Adjacent List 두 가지로 표현한다는 것을 이미 배웠는데 결국에 내부 구현이 이차원 배열이냐, 이차원 링크드 리스트냐의 차이다.

그래서 Java의 컨벤션은 가장 일반적인 인터페이스 (= ADT로써의 인터페이스) 를 변수 앞 타입에 쓰고, 구현 클래스 (= 자료구조로써의 클래스) 를 new 연산자에 붙인다. ADT는 이름 그대로 추상화 되어있는 개념이니까. Set<Integer> s = new HashSet<>();

그래서 가장 기본적인 자료구조가 뭐냐고 내게 묻는다면 Linked List라고 대답한다. 노드를 동적으로 생성하고, 그 노드를 다음 노드로 가리킨다는 개념을 처음 소개하기 때문이다. 가장 기본적인 ADT가 뭐냐고 내게 묻는다면 List다. 크다면 큰 차이고 미묘하다면 미묘한 차이다.

Leave a Reply