데이터 구조와 ADT

Abstract Data Type과 Data Structure의 차이

ADT(Abstract Data Type, 추상 데이터 타입)은 데이터를 사용자의 관점에서 보는 것이고, 데이터 구조 (Data Structure)는 데이터가 처리되는 관점에서 보는 것이다.

 

부동 소수점 변수 데이터가 있을 때 사용자는 그 데이터를 부동 소수점 변수로만 생각한다. 하지만, 실제 이러한 변수는 컴퓨터 내부에서 이진수의 데이터로 구성된다. 사용자는 부동 소수점이 어떻게 구현되는지 알 필요 없이 사용하면 된다. 여기서, 사용자가 보는 부동 소수점 변수를 ADT이라고 하고, 내부에서 실제 구현되는 데이터를 데이터 구조라고 한다.

 

스택(Stack)이 있을 때 사용자는 Push 또는 Pop을 이용하여 스택을 사용한다. 스택의 내부에서는 사용자의 명령을 받아 데이터의 LIFO(Last-In First-Out) 동작을 수행한다. 여기서, 스택을 ADT로 볼 수 있고, 내부에서 동작하는 LIFO를 데이터 구조라고 한다.

 

프로그램 개발 시 ADT와 데이터 구조를 분리하여 프로그래밍 하면 유연한 구조의 프로그램을 만들 수 있다. 예를 들면, 사용자는 스택의 Push/Pop 만을 사용하고 스택이 실체 처리되는 부분을 따로 만들면 스택 처리부를 차후 더 효율적인 알고리즘으로 수정해도 전체 프로그램을 수정할 필요가 없다.

 

추상 데이터 타입의 종류

 

    ● Container

    ● List

    ● Set

    ● Multiset

    ● Graph

    ● Stack

    ● Queue

    ● Map

    ● Multimap

 

 

추상 데이터 타입 Map

추상 데이터 타입 Map을 Associative Array 또는 Symbol Table 또는 Dictionary 라고도 한다. Map은 Key와 Value로 구성된 한 쌍의 데이터로 이루어진 데이터 타입이다. 

 

Map 데이터를 C++에서 std::map<Key, Value> 또는 std::unordered_map<Key, Value>로 구현하고 C#에서는 

SortedDictionary<TKey, TValue> 또는 Dictionary<TKey, TValue>로 구현한다.

 

 

추상 데이터 타입 Set

추상 데이터 타입 Set은 중복되지 않는 데이터를 순서를 무시하고 저장하는 것이다. 수학의 유한 집합 (Finite Set)과 유사하다. 유한 집합에 원소를 추가하거나 삭제할 때 같은 값을 가지는 원소는 하나 이고 원소의 순서는 무시된다.

 

Java에서는 Set 데이터 타입을 지원하고 내부 구현 방법에 따라 HashSet와 TreeSet와 LinkedHashSet를 사용할 수 있다.