[자료구조] 자료구조의 정의

자료구조

자료구조의 정의

자료구조는 문제 해결을 위해 데이터를 조직화하고 저장하는 것과

이를 구현하는 데 필요한 알고리즘에 대해 논하는 기초이론이다.

자료구조는 CS(컴퓨터 사이언스)에서 알고리즘과 함께 가장 중요한 기초이론이다.

알고리즘에서 효과적으로 접근, 변경, 처리가 가능하도록 만들어진 데이터 체계이기 때문이다.

자료구조는 데이터를 효율적으로 사용하기 위한 것으로 연산의 다양성 및 효율성 등을 제고하여

사칙연산 외에도 읽기, 삽입, 삭제, 비교, 교환 등 다양한 연산의 사용을 고려해야 한다.

 

추상 자료형과 자료구조

자료에 대해  처리를 어떻게 할지 자료와 동작을 함께 고려하면서,

컴퓨터에 효과적으로 표혀느 저장, 처리하는 기술 그리고 캡슐화 하는 것을 추상 자료형이라고 한다.

추상 자료형은 문제를 해결하는데 필요한 자료의 형태와 필요한 연산들을 수학적으로 정의한 것이고

자료구조는 추상 자료형이 정의한 연산들을 구현시킨 구현체를 가리키는 말인 것이다.

 

자료구조의 종류

기본적인 자료구조로는 자료형을 뜻하는 단순구조가 있다.

자료 간의 연결 형태 혹은 모양에 따른 구분으로는

'선형 자료구조'와 '비선형 자료구조'로 구분이 가능하다.

이 외에도 파일구조라는 구조형이 있다.

<자료구조의 종류>

 

단순구조(Simple Structure)

단순구조는 앞서 말한대로 자료형을 뜻한다.

정수(Integer), 실수(Real Number), 문자(Character), 문자열(String)이 해당하며

이 외의 자료형들도 단순구조에 포함된다.

 

선형 자료구조(Linear Data Structure)

선형 자료구조는 하나의 자료 뒤에 하나의 자료가 존재하는 것으로

자료들 간의 앞뒤 관계가 선형 관계를 이루고 있는 것이라 할 수 있다.

선형 자료구조의 대표적인 예로는 배열과 리스트가 있다.

그 외에도 스택과 큐, 데크가 선형 자료구조에 해당한다.

 

비선형 자료구조(NonLinear Data Structure)

비선형 자료구조는 계층구조나 망구조를 갖는 자료구조로

트리와 그래프가 대표적인 비선형 자료구조이다.

그래프는 주로 네트워크 모델에 사용되는 형태로

노드들 사이에서 무방향/방향/양방향 경로를 가질 수 있다.

그렇기 때문에 루트 노드, 부모-자식 관계의 개념이 없다.

트리는 그래프에서도 특별한 케이스로 최소 연결 트리라고도 한다.

두 개의 정점 사이에 반드시 1개의 경로만을 가지는 것이 특징이다.

 

※선형 구조와 비선형 구조의 차이

선형 자료구조와 비선형 자료구조의 차이점은 구성형태와 용도차이이다.

먼저 선형구조는 하나의 자료 뒤에 하나의 자료만 존재하는 형태로

자료와 자료가 1:1 관계를 이루는 것이 특징이다.

비선형 구조는 하나의 자료 뒤에 여러개의 자료가 존재하는 형태로

자료들 간의 앞뒤 관계가 1:다 혹은 다:다의 관계를 이루고 있다.

그리고 선형구조 자료를 저장하고 꺼내는 것이 중점이라면

비선형 구조는 디렉토리, 네트워크와 같이 표현에 초점이 맞춰져 있다.

 

파일구조(File structure)

파일 구조는 데이터를 효율적으로 이용할 수 있도록 파일에 저장하는 방법이다.

파일 구조의 설계 목표는 빠른 메모리 접근에 비해 느린 디스크 접근을 최소화 하는 것이다.

파일 구조에는 힙 파일 구조, 순차적 파일구조, 색인 파일구조, 직접 파일구조 등이 있다.