0.1 자료구조

자료구조(Data Structure)는 아래와 같은 특징을 갖는다.

• 컴퓨터가 데이터를 효율적으로 다룰 수 있게 도와주는 데이터 보관 방법
• 컴퓨터가 데이터를 효율적으로 다룰 수 있게 도와주는 데이터에 관한 연산의 총체

---

우리가 흔히 알고 있는 INT는 32비트의 메모리 공간 안에 수를 할당하고 첫 비트를 부호 표현에 사용하는 등의 '보관 방법'을 정의하고 있고, 덧셈/뺄셈/나눗셈/곱셈/논리/시프트 등 다양한 '연산' 또한 정의하고 있다.

 

자료구조는 아래와 같이 단순 자료구조(Primitive Data Structure)와 복합 자료구조(Non-Primitive Data Structre)로 나뉜다. 단순 자료 구조는 이전의 INT와 같은 통상적으로 제공하는 기본 데이터 형식을 말한다.

 

자료구조
단순 자료구조(Primitive)		복합 자료구조(Non-Primitive)
INT		선형(Linear)	비선형(Non-Linear)
LONG		배열	트리
DOUBLE		링크드 리스트	그래프
....		스택
		큐
		힙

복합 자료구조는 선형 자료구조(Linear Data Structure)와 비선형 자료구조(Non-Linear Data Structure)로 나뉜다.

• 선형 자료구조는 데이터 요소를 순차적으로 연결하는 자료구조이고, 구현하기 쉽고 사용하기 쉽다. 
• 비선형 자료구조는 배열(Array), 링크드 리스트(Linked List), 스택(Stack), 큐(Queue) 등이 해당된다.

비선형 자료구조는 선형 자료구조와 달리 데이터 요소를 비순차적으로 연결한다. 한 데이터 요소에서 여러 데이터 요소로 연결되기도 하고, 여러 데이터 요소가 하나의 데이터 요소로 연결되기도 한다. 이는 트리와 그래프로 불리운다.

---

※ 중요 개념

추상 형식(ADT - Abstract Data Types)은 자료구조의 동작 방법을 표현하는 데이터 형식이다. 정리하면 추상 형식은 자료구조가 갖춰야 할 일련의 연산이라고 할 수 있다. 이 연산을 C 언어로 표현하면 함수가 된다.

리스트를 예로 들어보면 리스트는 데이터에 순차적으로 접근해서 그 리스트를 다룰 수 있도록 기능을 제공해야 한다. 특정 위치에 있는 노드에 접근(Get)하거나, 목록의 마지막에 데이터를 추가(Append)하거나, 목록의 중간에 삽입(Insert)하거나, 삭제(Delete)하는 기능들이다.

 

ADT는 정의하기 나름이다. 어떤 ADT가 특정 연산을 반드시 제공해야 된다는 법은 없다.

추상 형식이 구조를 제시하면 자료구조는 이를 구현한다. 배열로 리스트를 구현한다고 가정해보면, 배열의 길이가 곧 리스트의 길이가 되고 배열의 첫 요소는 시작 노드, 배열의 마지막 요소는 마지막 노드가 된다. 현재 다루고 있는 요소의 첨자(Index)가 노드가 된다. 여기에 탐색/추가/삽입/수정/삭제와 같은 기능을 구현하면 하나의 자료구조가 완성된다.

 

ADT	자료구조
리스트	링크드 리스트 더블 링크드 리스트 환형 리스트
스택	배열 기반 스택 링크드 리스트 기반 스택
큐	환형 큐 링크드 큐
트리	이진 트리 LCRS 트리 레드 블랙 트리
그래프	방향성 그래프 무방향성 그래프
힙	배열 기반 힙 링크드 리스트 기반 힙

---

자료 구조는 왜 공부해야 하는가?

• 첫째로, 자료구조의 내부를 이해하면 라이브러리에서 엉뚱한 자료구조를 선택하는 일을 피할 수 있다. 동일한 ADT를 사용하더라도 자료구조에 따라 프로그램의 성능이 크게 달라질 수 있다. 예로, 네트워크 프로그램에의 입출력 버퍼에는 링크드 큐보다 환형 큐를 사용하는 것이 처리 속도 면에서 유리하고 메모리의 효율이 더 중요한 프로그램에서는 링크드 큐가 환형 큐보다 낫다. 자료구조 지식이 있는 프로그래머는 그 이유를 이해하고 라이브러리 문서를 통해 적절한 자료구조를 선택할 수 있다.
• 둘째로, 자료구조는 알고리즘에 데이터를 효율적으로 사용할 수 있게 도와주는 핵심 부품 역할을 하기 때문이다. 즉, 자료구조를 모르면 알고리즘을 공부하는 데 어려움이 따른다.