[C#]자료구조

1. 자료구조

1.1 자료구조(Data Structure)

데이터를 효율적으로 엑세스하고 조작할 수 있도록 데이터의 구조를 만들어 데이터를 저장하고 관리하는 것을 말함

자신의 목적에 맞는 자료구조를 잘 선택하는 작업이 중요함

1.2 추상적 자료형과 자료구조

• 추상적 자료형(Abstract Data Type, ADT) : 특별한 구현방법을 지정하지 않은 자료형
  ** 일반적으로 알고리즘이 문제를 해결하는데 필요한 자료의 형태와 그 자료를 사용한 연산들을 수학적으로 정의한 모델임

추상적 자료형 VS 자료구조

추상적 자료형 : 무엇(What)이 구현되어져야 하는지를 정의한 것. 자료형의 논리적형태 정의
자료구조 : 이것을 어떻게(How) 구현할 지를 파악해서 물리적형태로 구현한 것

ex: 스택(Stack)은 추상적 자료형, 자료구조 구현 측면에서 배열형태로 구현될 수도 있고 연결 리스트(Linked List)형태로 구현될 수도 있다

일반적으로 잘 알려진 추상적 자료형을 예로 들면...

Stack, Queue, 우선순위 큐, 데크, Tree, Graph, Map, Associative Array, Set, List, Container 등을 들 수 있다

자료구조의 종류

• 단순 구조(Primitive Data Structure) : 프로그래밍에서 사용되는 기본적인 데이터 타입으로, 정수, 실수, 문자, 부울린 등의 기초 타입들이 여기에 속한다.
• 선형 구조(Linear Data Structure) : 자료 요소가 선형적으로 연결되어 있는 구조로서 앞 자료와 뒤 자료가 1대 1인 구조를 갖는다. 배열, 연결 리스트, 스택, Queue 같은 자료구조가 이에 해당
• 비선형 구조(Non-linear Data Structure) : 자료 간 관계가 1대 다 혹은 다 대 다 구조로서 계층구조 혹은 네트워크 망 구조를 갖는다. 트리와 그래프가 있음
• 파일 구조 : 레코드의 집합인 파일에 대한 자료구조로서 순차파일, 색인파일, 직접파일 등이 이에 해당함