[자료구조] 추상 자료형(Abstract Data Type)과 자료구조(data structure)

📌 추상 자료형 ( ADT )

---

추상 자료형은 객체지향 언어( C++, JAVA )의 클래스와 유사하다. 추상 자료형은 기능 구현 부분은 명세하지 않고, 데이터의 형태를 선언하고, 기능을 정의한다.

구현 방법을 명세하지 않았기 때문에 추상 자료형으로 자료구조의 성능은 알 수 없습니다.

📌 자료구조 ( Data structure )

---

자료구조는 추상 자료형에서 정의된 기능들을 구현한 함수나 명령, 데이터들의 관계를 나타낸다.

자료구조는 구현 방법이 명시되어 있지 않은 추상 자료형과는 다릅니다.

선형 구조를 갖는 큐(Queue)의 경우, 삽입과 삭제 기능이 정의된다. 삽입은 한 끝 ( rear or back )에서, 삭제는 다른 끝 ( front ) 에서 발생한다. 따라서 큐는 FIFO( first in, first out ) 값들의 모임이다. 그러나 큐가 내부적으로 배열로 구현되어 있는 지, 연결 리스트로 구현되어 있는 지는 알 수 없다. 이것이 앞서 나온 추상자료형과 자료구조의 차이점이고, 내부 연산의 구현방법이 정의된다면 그 때부터는 자료구조로 볼 수 있다.

따라서 추상 자료형과 자료구조는 구분하여 쓰는 것이 맞지만, 자료구조의 범위가 워낙 광범위하기 때문에 추상 자료형과 혼동되거나 아니면 추상 자료형과 그것의 구현방법을 정의한 자료구조의 이름이 같아서 혼란되는 경우가 많이 있다. 이것을 구분하기 위해서는 추상 자료형과 자료구조의 차이점을 알아야 한다.

구현 방법의 여부에 따라 구분 가능합니다.

예시로는 스택이나 큐, 트리의 경우는 구현 방법이 명시되어 있지 않으므로 추상 자료형에 해당하며, 배열이나 연결 리스트의 경우 다음 데이터의 위치 저장 방식이 명확하게 정해져 있으므로 자료구조에 해당된다.

📌 추상 자료형과 자료구조의 예

---

추상적 자료구조

• 연결 리스트 (Linked List)
• 스택 (Stack)
• 큐 (Queue)
• 트리 (Tree)
• 그래프 (Graph)

선형 자료구조

• 배열 (Array)
• 가변 길이 배열 (Vector)
• 연결 리스트 (Linked List) ( 이름이 같은 경우 )

---

참고자료
자료구조.namuwiki