#자료구조의 개요, 특징, 분류

##1.자료, 정보, 자료구조

###(1) 자료와 정보

자료(Data)란 현실 세계로부터 수집한 사실이나 개념의 값 또는 이들의 집합을 의미한다. 흔히 가공되지 않은 형태의 데이터를 자료라고 하며 특정한 용도로 사용하기 위하여 자료를 처리/가공한 형태의 데이터를 정보(Information)라고 한다.

###(2) 자료 구조

자료구조(data structure)란 자료의 집합을 의미하며 각 원소들 사이의 관계가 논리적으로 정의된 일정한 규칙에 의하여 나열되며 자료에 대한 처리를 효율적으로 수행할 수 있도록 자료를 조직적, 체계적으로 구분하여 표현한 것을 말한다.

###(3) 자료 구조의 선택 기준

작업의 효율성, 추상화, 재사용성을 증가시키기 위하여 상황에 따른 적절한 자료구조를 선택하여 사용해야 한다. 자료의 처리를 좀 더 효율적으로 하기 위하여 아래의 사항을 고려해야 한다.

• 자료의 처리 시간
• 자료의 크기
• 자료의 활용 빈도
• 자료의 갱신 정도
• 프로그램의 용이성

##2. 자료구조의 특징

###(1) 효율성(Efficiency)

상황에 맞는 알고리즘을 사용하여 자료를 구조화 시키기 때문에 효율적으로 동작한다. 예를 들어 모든 사원에 대해 사번과 이름의 쌍을 배열이라는 자료구조로 만들었을 때 사번을 가지고 이름을 찾을 경우 배열은 인덱스를 이용하여 데이터를 저장하기 때문에 찾으려는 사번이 첫번째 인덱스에 저장되어 있을 경우 한번의 검색으로 찾을 수 있지만 최악의 경우 제일 마지막 인덱스에 위치할 수 있으므로 데이터의 수만큼 검색을 해야 한다.

평균적으로 자료수/2 만큼의 검색을 해야 하므로 데이터를 찾는 작업이 빈번하고 데이터가 많을 경우 그다지 효율적이지 못하다. 이럴 때에는 해시 테이블과 같은 자료구조를 이용하여 좀 더 빠르게 검색 작업을 할 수 있다.

이처럼 상황에 맞는 적절한 자료구조를 이용하게 되면 데이터 처리의 효율을 높일 수 있다.

###(2) 추상화(Abstraction)

추상화란 복잡한 자료, 모듈, 시스템 등으로부터 핵심적인 개념 또는 기능을 간추려내는 것을 말한다.

자료구조를 이용하여 데이터를 처리할 경우 처리할 데이터를 어떻게 삽입하고 어떻게 추출할 것인가에 중점을 두지 않는다. 즉, 자료구조 자체를 구현하는 알고리즘에 중점을 두지 않고 어느 시점에 데이터를 삽입할 것이며 어느 시점에 데이터를 추출하고 이러한 데이터를 어떻게 사용할 것인지에 초점을 맞출 수 있기 때문에 프로그램의 비즈니스적인 요소에 좀 더 시간을 할애할 수 있다.

데이터를 처리하는 관점에서 보면 특정 자료구조 자체의 내부 구현은 그리 중요하지 않기 때문에 어떻게 구현했는지 보다 어떻게 사용하는지에 대해서 알고 있으면 된다.

예를 들어 스택(Stack)의 경우 가장 마지막에 삽입한 데이터를 가장 먼저 꺼내는 자료구조이고 push(), pop() 메소드를 통해서 데이터를 삽입하고 꺼낼 수 있다. 그리고 이러한 자료구조의 추상화는 실제 구현한 언어가 무엇인지에 따라 실제 그 코드는 다르지만 추상적인 개념에 대해서만 알고 있으면 되기 때문에 언어에 종속적이지 않다는 특징을 가진다.

###(3) 재사용성(Reusability)

자료구조를 이용하여 데이터를 처리할 경우 해당 자료구조의 인터페이스만 이용하여 데이터를 처리하도록 하므로 모듈화가 가능하다. 이는 자료구조를 설계할 때 특정 프로그램에 맞추어 설계하지 않고 다양한 프로그램에서 사용될 수 있도록 범용화하여 설계함으로써 가능하다.

##3. 자료구조의 분류

자료구조는 크게 선형 구조와 비선형 구조로 나눌 수 있다. 선형 구조는 자료가 일렬로 연결되어 있는 형태로 구성하는 방법이고 비선형 구조는 자료의 구성이 일렬이 아닌 특별한 형태를 띠는 구조이다.

###(1) 구현에 따라

• 배열

가장 일반적인 구조이다. 메모리 상에 같은 타입의 자료가 연속적으로 저장된다. 자료값을 나타내는 가장 작은 단위가 자료를 다루는 단위이다.

• 튜플

둘 이상의 자료형을 묶음으로 다루는 구조이다.

• 연결 리스트

노드를 단위로 한다. 노드는 자료와 다음 노드를 가리키는 참조값으로 구성되어 있다. 노드가 다음 노드로 아무것도 가리키지 않으면 리스트의 끝이다.

• 환형 연결 리스트

각 노드는 다음 노드를 가리키고, 마지막 노드가 처음 노드를 가리키는 연결 리스트이다.

• 이중 연결 리스트

각 노드는 이전 노드와 다음 노드를 가리키는 참조값으로 구성된다. 처음 노드의 이전 노드와 마지막 노드의 다음 노드는 없다.

• 환형 이중 연결 리스트

처음 노드가 이전 노드로 마지막 노드를 가리키고, 마지막 노드가 다음 노드로 처음 노드를 가리키는 이중 연결 리스트이다.

• 해시테이블

개체가 해시값에 따라 인덱싱된다.

###(1) 선형 구조

• 스택 ex) 택시안에 있는 동전 꼽이 형태

스택 자료구조에 먼저 저장된 것이 꺼내어 쓸 때는 제일 나중에 나온다. 반대로, 가장 최근에 저장된 것이 꺼내어 쓸 때는 제일 먼저 나온다. 만약, 자료들의 나열 순서를 바꾸고 싶다면 스택에 집어 넣었다가 꺼내면 역순으로 바뀐다.

• 큐

스택과 반대로 큐 자료 구조에 먼저 저장된 것이 제일 먼저 나온다. 반대로, 가장 나중에 저장된 것이 꺼내어 쓸 때는 가장 나중에 나온다.

• 환형 큐

한정된 길이 안에서 부수적인 작업 없이 읽고 쓰기를 할 수 있는 큐이다.

• 데크(덱)

양쪽에서 넣기와 빼기를 할 수 있는 일반화된 선형 구조이다.

###(2) 비선형 구조

• 트리

뿌리와, 뿌리 또는 다른 꼭짓점을 단 하나의 부모로 갖는 꼭짓점들로 이루어진 구조. 부모 자식 관계는 변으로 표현된다. 무향 그래프의 경우, 순환이 없는 연결 그래프를 뜻한다. 유향 그래프의 경우 변의 방향은 보통 부모를 가리키도록 구현된다.

• 이진 트리

자식이 최대 두 개인 트리.

• 힙

이진트리의 일종으로 이진트리에 어떤 특성을 부여한 것이라 할 수 있다.

• 그래프

꼭짓점과 꼭짓점을 잇는 변으로 구성된다.

• 유향 그래프, 무향 그래프

변이 방향성을 갖는지 갖지 않는지에 따른 그래프의 분류이다.