자료구조(Data Structure)와 추상자료형(Abstract Data Type)

배경
파이썬으로 자료구조를 공부하는 와중에 배열을 접했다.
상당 수의 강의에서 자료구조를 설명할 때 배열의 정의를 실컷 설명하고는 리스트로 결과물을 보여준다.
이어서 파이썬 리스트의 특징을 설명하는데
배열을 설명하는 건지 리스트를 설명하는 건지 애매해서 답답했다.

단순히 리스트가 배열로 사용된다고 얼버무리고 넘어가기에는
배열의 정의와 파이썬 리스트는 안 어울렸다.
매끄럽지 못한 설명을 듣다 보니 무언가를 놓치고 있는 것 같았다.
간단한 개념으로 여겨지지만 명확한 것을 좋아하는 나로서는 깔끔한 정리가 필요했다.
그렇게 점점 파고들며 이렇게 자료구조와 추상 자료형을 정리한다.

자료구조 정의
일반적으로 데이터 값의 모임, 또 데이터 간의 관계, 그리고 데이터에 적용할 수 있는 함수나 명령으로
실제로 데이터를 연산하고 저장하는 구조를 의미한다.

추상 자료형 정의
컴퓨터 과학에서 자료들과 그 자료들에 대한 연산들을 명기한 것으로
어떤 개념에 대해서 어떠한 기능이 있다를 표기하거나 정해놨을 뿐 구체적으로 데이터가
어떻게 연산되고 저장되는지에 대해서는 언급하지 않는다.

차이
추상 자료형은 구현 방법을 명시하고 있지 않다는 점에서 자료 구조와 다르다.

잘 알려진 추상 자료형에는 복소수, 리스트, 스택, 큐, 맵, 우선순위 큐, 집합 등이 있다.
추상자료형(Abstract Data Type:ADT)은 다음을 명세한다.

• 저장된 데이터
• 데이터에 대한 작업들
• 작업 중 발생 가능한 에러 상황들

그러나 구체적으로 이러한 작업과 데이터를 어떻게 프로그램적으로 정의할 지는 명세하지 않는다.

정리
우리가 자료구조를 접하면서 배우는 것(스택, 큐 등)을 엄밀히 따지자면 
개념을 배우는 것이므로 추상 자료형을 배우는 것이고,
여기에 시간복잡도나 연산의 세부사항들을 고려하면 추상 자료구조가 되며
배열과 포인터 같이 실제 메모리를 할당 적재하는 과정을 통해 구현하면 자료구조로 인정한다.

결론
모든 추상자료형의 구현 시 배열과 포인터가 사용되며, 모든 자료구조는 배열과 포인터를 이용해 구현된다.
그러므로 원초적인 자료구조는 배열과 (포인터를 이용한) 연결 노드라고 할 수 있다. 
배열(Array) 또는 연결노드(Linked Node) 통해 구현된 추상 자료형은 비로소 자료구조라고 할 수 있다.
그렇기 때문에 자료구조의 개념인 추상자료형은 언어와 구현의 제약이 없다. 

예를 들면 배열로 구현된 스택, 연결 노드로 구현된 스택 둘 다 스택 자료구조로 불리게 되는 것이다.
엄밀히 말해 추상자료형 스택을 자료구조인 배열과 연결 노드로 각각 구현하여 스택 자료구조로 실체화시킨다고 결론 지을 수 있다.

referrence
https://ko.wikipedia.org/wiki/%EC%B6%94%EC%83%81_%EC%9E%90%EB%A3%8C%ED%98%95
https://gbsb.tistory.com/306