자료구조에 대한 자잘한 노트

ADT(Abstract Data Type)

ADT(Abstract Data Type)은 추상자료형, 구현방법을 명시하지 않고 자료구조의 특성들과 어떤 Operation이 있는지를 설명하는 자료구조의 한 형태이다. 대표적으로 스택과 큐가 있다. 어떻게 구현되는지가 추가되면 DS로써의 스택과 큐가 된다.

자바 기준으로는 interface가 ADT, class가 DS이다.

스택이 어쩌고 저쩌고 -> ADT 관점, 그래서 스택을 어떤 구현체를 써서 구현했어 -> DS 관점이다.

 

선형(Linear) 자료구조, 비선형(Nonlinear) 자료구조

선형 자료구조는 하나의 자료 뒤에 하나의 자료가 존재하는 것이다. 자료간의 1:1 관계가 유지되는 것이다. 스택, 큐, 배열 등이 이에 해당한다.

비선형 자료구조는 하나의 자료 뒤에 여러개의 자료가 존재하는 것이다. 자료들 간의 관계가 1:n, n:n이 되는 것이다. 트리, 그래프 등이 이에 해당한다. 계층적 구조를 나타내는데 적합하다.