💚 자료구조 - ADT와 DS의 차이

ADT

• 추상 자료형(Abstract Data Type)

• 자료구조의 특징, 속성, 연산 등으로 무엇을 할 수 있는지

• 데이터에 대한 타입과 해당 타입에 수행할 수 있는 연산들만을 정의함.

• How에 대해서는 다루지 않음 -> 구현에 대해서 다루지 않음

• 여기서 How까지 다룬다면 자료 구조(Data Structure)가 됨.

• 정의와 구현을 분리한다면 사용자는 굳이 어떻게 만들어지는지 몰라도 사용하는데 문제 없음.

• 사용자는 ADT에서 정의된 기능을 이용하면 되고 구현을 개발자가 한다.

ADT 목적 : 추상화를 통해 구현 세부 사항으로부터 사용자를 분리 시키는데 중점 -> 사용자는 복잡한 내부 구현에 신경 쓰지 않고 인터페이스만을 이용해 데이터를 다룰 수 있다.

설명

Stack으로 예시를 들겠다.

Stack이 무엇인지에 대해 질문했을 때?

답변으로 FILO(First In Last Out), 먼저 들어온 데이터가 나중에 나가고 늦게 들어온 데이터가 제일 먼저나가는 구조로 연산으로는 데이터를 저장하는 push, 데이터를 빼는 pop 등이 있다. 이렇게 설명한다면 이건 ADT를 설명한 거라고 생각할 수 있다.

여기서 구현에 대한 설명은 없기 때문에!

Stack을 어떻게 구현할 것인가? 에 다룬다면 이것은 Data Structure가 된다.

1. Array 사용

2. Linked List 사용

• 데이터가 메모리에 어떻게 저장되고 관리될지를 구체적으로 정의함.

DS 목적 : 데이터를 효율적으로 저장하고 처리하는 것. 적절한 데이터 구조의 선택은 알고리즘의 효율성을 크게 향상시킬 수 있음.

Java를 예시로 들면 Interface는 ADT, Interface를 구현한 Class는 DS같은 의미

• 인터페이스는 메서드의 시그니처(이름, 매개변수, 반환 타입)를 정의하지만 이 메서드들이 실제로 어떻게 구현될지는 정의하지 않음.

• 클래스는 데이터 구조의 구현을 위한 수단을 제공하고 데이터(필드)와 데이터를 조작하는 연산(메서드)을 묶어서 표현함. 클래스는 데이터 구조의 구체적인 구현체가 될 수 있지만 모든 클래스가 데이터 구조를 나타내는 것은 아님.

ADT와 DS의 차이점

• ADT는 데이터 구조의 논리적 특성을 정의하는데 초점을 두고 구현 세부 사항은 숨기지만 DS는 데이터가 실제로 어떻게 저장되고 관리되는 지에 대한 구체적인 세부 사항을 다룬다.

• ADT는 인터페이스에 중점을 두고 구현 세부 사항은 고려하지 않는다. DS는 실제 메모리 내에서 데이터가 어떻게 구현되는지를 포함한다.

• ADT는 설계 시 데이터의 타입과 연산에 대한 명세에 집중한다. 데이터 구조는 프로그램의 성능을 최적화하기 위해 적절한 저장 및 관리 방식으로 고려하는데 사용한다.

stack<Integer> stack = new Stack<>();

Stack<Integer> stack // 스택 ADT의 타입
new Stack<>(); // ADT를 실제로 구현하는 DS

결론

ADT와 DS는 밀접하게 연결되어 있다. ADT는 어떤 데이터 타입이 수행해야 할 연산을 정의하고 DS는 이러한 ADT가 실제 메모리 상에서 어떻게 구현될지를 정한다.

ADT는 무엇(What)을 할 것인지에 대해 정의하고 DS는 어떻게(How)할 것인지에 대해 정의함.