[APS] 003 : 자료구조 개론

자료구조

---

자료구조(data structure)

- 효율적인 관리를 위해 특성이나 상호 관계 등에 따라 구조화시킨 데이터, 혹은 그의 집합체

- 대부분의 프로그래밍 언어는 자료형(data type) 을 통해 자료구조를 정의

• 원시 자료형 : 자료를 특성에 따라 효율적으로 메모리에 저장하기 위한 단순한 자료구조
• 추상 자료형(ADT : Abstract Data Structure)
• 다수의 원시형 자료들을 용도 등에 따라 효율적으로 관리하기 위해 정의된 자료구조
• 구성하는 원시 자료형과 필요한 연산 등을 수학적/논리적으로 정의해놓은 집합체

※ 자료구조가 실제적으로 정의된 용어라면, 자료형은 각 프로그래밍 언어에서 정의된 형식이다. 예를 들어 Java 는 인터페이스(혹은 추상클래스)를 통해 특정 자료구조에 대응되는 자료형을 정의하고, 구체적인 대입을 통해 실체화된 자료구조인 클래스(객체) 를 만든다. 다만 두 단어는 혼용되는 경우가 많다.

---

자료구조의 분류

- 데이터 간 관계에 따라 단순 구조, 선형 구조, 비선형 구조, 파일 구조와 그 외로 분류

출처 : 네이버 지식백과

1. 단순구조: 각 구조를 이루는 기본이 되는 원소 ≒ 원시 자료형
2. 선형(linear)구조 : 원소간의 관계가 선형적으로 배치됨 : 배열, 리스트, 스택, 큐, 덱 등...
3. 비선형(non-linear)구조 : 원소간의 관계가 비선형적으로 배치됨 : 트리, 그래프 등...
4. 파일구조 : 파일의 데이터 저장방식에 대한 자료구조
5. 그 외 : 딕셔너리, 집합, 구조체, 클래스 등 ...

※ 자료구조는 정의에 따라 수없이 많고, 분류에 대한 관점도 다양하며, 프로그래밍 언어마다 관점이나 구현방식이 상이하여 위의 분류법에 명확히 합치하지 않는 경우도 있다. 따라서 이러한 분류법이 있다는 정도만 염두에 두고, 자료구조의 분류에 너무 얽매이지 않도록 하자.

---

자료구조 별 복잡도

- 각 동작의 시간 복잡도는 O(1) ~ O(logN) 을 "빠른 속도"로 볼 수 있고, O(N) 이하를 "느린 속도"로 볼 수 있음

- 공간 복잡도는 기본적으로 자료의 갯수(N)과 비례하지만, 일부 자료구조는 그 이상(overhead)을 필요로 하기도 함

---

- 최종 수정일 : 23-04-10

- 이 글은 지속적으로 수정되고 있으며, 오타나 잘못된 정보에 대한 사항은 댓글로 남겨주시면 감사하겠습니다.