자료구조(Data Structure)란 자료의 집합을 의미한다. 각 자료들 사이의 관계가 미리 정의된 일정한 규칙에 의하여 나열되며 자료에 대한 처리를 효율적으로 수행할 수 있도록 자료를 구분하여 표현한 것을 말한다.
자료와 정보
자료(Data)란 현실 세계에서 얻어진 사실이나 개념의 값 또는 이들의 집합을 의미한다. 흔히 가공되지 않은 형태의 데이터를 자료라고 하며, 특정한 용도로 사용하기 위하여 처리를 거친 형태의 데이터를 정보(Information)라고 한다.
자료구조의 선택 기준
자료구조의 선택이 왜 중요한가? 적은 양의 데이터를 처리할 때에는 어떤 자료구조를 사용하든 큰 차이가 없다. 그러나 대량의 데이터를 한 번에 처리함에 있어서 어떤 자료구조를 사용하는 가에 따라서 효율성에 있어 굉장한 차이가 있다.
예를 들어 스택(Stack)과 연결 리스트(Linked List)가 있다고 했을 때, 원소 삽입에 대한 시간복잡도는 각각 O(1)과 O(n)이다. 데이터가 100만 개가 존재한다고 했을 때, 한 번의 연산을 거치는 것과 100만 번의 연산을 거치는 것은 효율성 면에서 큰 차이가 있다.
자료구조의 선택 기준은 외에도 다음과 같이 다양하다.
- 자료의 처리 시간
- 자료의 크기
- 자료의 활용 빈도
- 자료의 갱신 정도
- 프로그램의 용이성
자료구조의 특징
1. 효율성
자료구조를 사용하는 목적은 상황에 맞게 효율적으로 자료를 관리하고 사용하는 것이다. 따라서 문제에 알맞은 자료구조를 사용하면 업무 효율이 증가할 것이다.
2. 추상화
추상화(Abstraction)란 복잡한 자료, 모듈, 시스템 등으로부터 핵심적인 개념 또는 기능을 간추려 내는 것을 말한다.
자료구조를 이용해서 데이터를 처리할 때에는 어느 시점에 데이터를 삽입할 것인지, 어느 시점에 데이터를 추출하고 사용할 것인지에 초점을 둔다. 즉, 데이터를 어떻게 삽입, 추출, 사용하는지를 구현하는 알고리즘에 중점을 두지 않는다.
데이터를 처리하는 관점에서 보면 각 자료구조의 내부 구현은 그리 중요하지 않으며, 어떻게 사용하는지 그 인터페이스를 알면 된다.
예를 들어 큐(Queue)의 경우 먼저 삽입한 데이터를 가장 먼저 꺼내는 자료구조로, enquque(), dequeue() 메서드를 사용하여 데이터를 삽입하고 접근할 수 있다.
이러한 자료구조의 추상화는 구현 언어에 따라 그 코드는 다르지만, 추상적인 개념에 대해서만 알고 있으면 되기 때문에 언어에 종속적이지 않다는 특징을 가진다.
3. 재사용성
자료구조를 설계할 때, 특정 프로그램에서만 동작하게 설계하지 않는다. 다양한 프로그램에서 동작할 수 있도록 범용성 있게 설계하기 때문에 다른 프로젝트에서도 사용할 수 있다.
자료구조의 종류
자료구조는 크게 선형 구조와 비선형 구조로 나눌 수 있다. 선형 구조는 데이터가 일렬로 연결되어 있는 구조이고 비선형 구조는 자료의 구성이 일렬이 아닌 특정한 형태를 띠는 구조이다.
단순 구조
- 정수
- 실수
- 문자
- 문자열
선형 구조
-
배열(Array): 가장 일반적인 구조로서 인덱스와 인덱스에 대응하는 데이터들로 이루어진 자료구조
- 연결 리스트(Linked List): 각 노드가 데이터와 포인터를 가지고 한 줄로 연결되어 있는 방식으로 데이터를 저장하는 자료구조
- 스택(Stack): 후입선출의 자료구조
- 큐(Queue): 선입선출의 자료구조
비선형 구조
- 트리(Tree): 부모 노드 밑에 여러 개의 자식 노드가 연결되고, 자식 노드가 다시 부모가 되어 각각의 자식 노드가 연결되는 재귀적 형태의 자료구조
- 그래프(Graph): 정점(Vertex)과 정점들을 연결하는 변(Edge)으로 구성된 자료구조