자료구조란
자료구조(data structure)는 컴퓨터 과학에서 효율적인 접근 및 수정을 가능케 하는 자료의 조직, 관리, 저장을 의미합니다.
더 정확히 말해, 자료구조는 데이터 값의 모임, 또 데이터 간의 관계, 그리고 데이터에 적용할 수 있는 함수나 명령을 의미합니다.
(무수한 데이터들을 정리하는 규칙과 방법에 따라 정리한 구조입니다)
자료구조가 필요한 이유?
데이터를 효율적으로 저장, 관리하여 메모리를 효율적으로 사용하기 위함입니다. 적절한 자료구조의 사용은 메모리의 용량을 절약해주고, 실행 시간을 단축 시켜줄 수 있습니다.
자료구조의 선택 기준
적은 양의 데이터를 처리할 때는 어떤 자료구조를 사용하든 큰 차이가 없습니다. 그러나 대량의 데이터를 한 번에 처리함에 있어서 어떤 자료구조를 사용하는 가에 따라서 효율성에 있어 굉장한 차이가 있습니다.
예를 들어 스택과 연결 리스트가 있다고 했을 때, 원소 삽입에 대한 시간복잡도는 각각 O(1)과 O(n)입니다. 데이터가 100만 개가 존재한다고 했을 때, 한 번의 연산을 거치는 것과 100만번의 연산을 거치는 것은 효율성 면에서 큰 차이가 있습니다.
자료구조의 선택 기준은 외에서 다음과 같이 다양합니다.
- 자료의 처리 기간
- 자료의 크기
- 자료의 활용 빈도
- 자료의 갱신 정도
- 프로그램의 용이성
자료구조의 특징
-
효율성
자료구조를 사용하는 목적은 상황에 맞게 효율적으로 데이터를 관리하고 사용 하는 것입니다.
따라서 적절한 자료구조를 선택하여 사용한다면 업무의 효율이 올라갈 것입니다.
-
추상화
추상화란 공통적인 개념을 이용하여 같은 종류의 다양한 객체를 정의하는 것 입니다. 추상화를 통해 간결하게 말하는 사람의 의사를 전달할 수 있게 됩니다.
자료 추상화는 다양한 객체를 컴퓨터에서 표현하고 활용하기 위해 필요한 자료의 구조에 대해서 공통의 특징 만을 뽑아 정리한 것입니다. 자료 사이의 논리적 관계를 컴퓨터나 프로그램에 적용하기 위해서는 자료의 추상화가 필요합니다.
자료구조를 구현할 때 중요한 것은 어느 시점에 데이터를 삽입할 것이며, 어느 시점에 이러한 데이터를 어떻게 사용할 것 인지에 대해서 초점을 맞출 수 있기 때문에 구현 외 적인 부분에 더 시간을 쏟을 수 있습니다. 즉, 데이터를 어떻게 삽입, 추출, 사용하는 지를 구현하는 알고리즘에는 중점을 두지 않습니다.
데이터를 처리하는 관점에서 보면 각 자료구조의 내부 구현은 그리 중요하지 않으며, 어떻게 사용하는지 그 인터페이스를 알면 됩니다.
이러한 자료구조의 추상화는 구현 언어에 따라 그 코드는 다르지만, 추상적인 개념에 대해서만 알고 있으면 되기 때문에 언어에 종속적이지 않다는 특징을 가집니다.
-
재사용성
자료구조를 설계할 때 특정 프로그램에서만 동작하게 설계하지는 않습니다. 다양한 프로그램에서 동작할 수 있도록 범용성 있게 설계하기 때문에 해당 프로젝트가 아닌 다른 프로젝트에서도 사용할 수 있습니다.
자료구조의 종류와 구분
자료구조 종류
단순구조
자료 값을 사용하기 위해서 True/False, 정수, 실수, 문자 및 문자열과 같이 컴퓨터가 기본적으로 제공하는 자료형입니다.
- 2진수, 정수, 실수, 문자, 문자열
선형구조
자료를 구성하는 데이터를 순차적으로 나열 시킨 형태입니다.
자료들 간의 관계가 1:1인 자료입니다.
- 배열 : 가장 일반적인 구조입니다. 메모리 상에 같은 타입의 자료가 연속적으로 저장되고 자료 값을 나타내는 가장 작은 단위가 자료를 다루는 단위입니다.
- 연결 리스트 : 노드를 단위로 합니다. 노드는 자료와 다음 노드를 가리키는 참조 값으로 구성되어있습니다. 노드가 다음 노드로 아무것도 가리키지 않으면 리스트의 끝입니다.
- 덱 : 양쪽에서 넣기와 빼기를 할 수 있는 일반화된 선형 구조입니다.
- 스택 : 먼저 저장된 것이 꺼내어 쓸 때는 제일 나중에 나옵니다. 반대로, 가장 최근에 저장된 것이 꺼내어 쓸 때는 제일 먼저 나옵니다.
- 큐 : 스택과 반대로 먼저 저장된 것이 제일 먼저 나옵니다. 반대로, 가장 나중에 저장된 것이 쓸 때는 가장 나중에 나옵니다.
비선형구조
하나의 자료 뒤에 여러 개의 자료가 존재할 수 있는 것을 의미합니다.
계층 구조나 망 구조를 갖는 자료구조로서 트리와 그래프가 있습니다.
- 그래프 : 꼭짓점과 꼭짓점을 잇는 변으로 구성 되어 있습니다.
- 트리 : 뿌리와 뿌리, 또는 다른 꼭짓점을 단 하나의 부모로 갖는 꼭짓점들로 이루어진 구조입니다.
파일구조
서로 관련 있는 필드로 구성된 레코드 집합인 파일에 대한 자료구조로 보조 기억 장치에 데이터가 실제로 기록되는 형태입니다.
메모리에 한번에 올릴 수 없는 대용량을 다룹니다.
- 순차 파일, 색인 파일, 직접 파일
