01. 자료구조의 정의

컴퓨터 프로그램은 크게 2가지 공통점이 있다.

1. 컴퓨터에 의해서 실행되는 명령어들의 집합이다.

2. 명령을 수행하기 위해 내부적으로 여러 자료(Data, 데이터)를 저장한다.

즉, 프로그램은 내부적으로 자료(데이터)를 저장하고 이를 처리하기 위한 명령어들의 집합을 가지고 있다.

자료구조

자료구조는 컴퓨터에 자료(데이터)를 효율적으로 저장하는 방식을 말한다. 효율적인 자료구조는 컴퓨터메모리를 절약(Space Complexity)할 뿐아니라, 프로그램 수행 시간을 최소화(Time Complexity) 할 수 있다. 컴퓨터 명령 자체의 효율성을 증가시키기 위한 절차를 알고리즘이라고 하는데 효율적인 알고리즘이 가능하기 위해서는 먼저 효율적인 자료구조가 선행되어야한다.

자료구조의 설계는 보통 프로그램이 어떻게 사용되는지에 따라 결정된다. 이러한 자료구조의 정의와 기능을 예를 들자면 아래와 같다.

1. 윈도우 탐색기 → Tree 구조
2. 웹 브라우저의 즐겨찾기 목록 → List 구조
3. Ctrl + Z → Stack 구조
4. 프린터 출력 → Queue 구조

위 예시 외에도 다양한 곳에서 사용되는 자료구조를 확인할 수 있을 것이고 또 앞으로 사용하게 될것이다. 자료구조를 설계하면서 가장 중요하게 생각해야 할 것은 실제 그 프로그램이 어떠한 목적으로 어떻게 사용되느냐는 것이다. 적절한 때 사용되는 자료구조는 위에서 말했듯이 메모리가 절약될 뿐 아니라 프로그램 수행에 걸리는 시간도 최소화될 것이다.

자료구조의 분류

자료구조는 특정 기준에 의해 몇개의 카테고리로 분류해 볼 수 있다.

단순 구조

프로그래밍 언어에서 제공하는 기본적인 데이터 타입을 말한다. 일반적으로 자료구조라 하면 단순 구조를 지칭하는 것은 아니지만 이러한 단순구조도 언어에서 정의한 특정 길이의 자료구조라고 말 할 수 있다.

선형 구조

각각의 자료들이 사이의 앞뒤 관계가 일대일인 경우를 말한다.

선형 구조 예시

위 그림은 4개의 자료가 선형적으로 연결된 자료구조를 나타낸다. "두번째"는 "첫번째"와 일대일 관계이며 그 뒤인 "세번째"와도 일대일 관계이다. 이러한 공통점을 가지는 선형 자료구조들은 Array, List, Stack, Queue, Record(Tuple)등이 있으며 자료를 저장하는 방식 사용하는 방식 불변성등의 차이점들을 가진다.

비선형 구조

자료들 사이의 앞뒤 관계가 일대일이 아닌 계층 구조(Hierarchical Structure)또는 망구조(Network Structure)를 가지는 경우를 말한다. 대표적으로 Tree와 Graph등이 있다.

비선형 구조 예시

추상 자료형(Abstract Data Type, ADT)

정보은닉(Information Hiding)은 중요한 정보만을 나타내고, 중요하지 않은 정보는 숨기는 것을 말한다. 즉, 사용자 관점에서 불필요한 정보를 제거하고, 사용자에게 반드시 필요한 것만을 심플하게 제공하여 개발 효율성을 증가시키려는 접근 방식이다.

자료구조에서도 이러한 정보은닉 개념을 적용할 수 있다. 자료구조를 사용할 수 있는 연산(Operation)들의 정의 즉, 자료구조의 인터페이스(Interface)는 제공하고 사용자에게 불필요한 자료구조의 내부 구현 로직은 감추어 사용자가 내부 구조까지 신경쓰지 않게 하는 것이다.

추상 자료형(Abstract Data Type, ADT)은 정보 은닉의 개념을 이용하여 자료구조를 간략히 표현하는 것을 말한다. 추상 자료형이 자료구조를 사용하는 데 필요한 인터페이스만을 간단하게 전달하여 각 연산이 어떤 기능을 하며 입력값과 출력값이 무엇인지만을 노출하고 있고, 연산 내부의 세부적이고 복잡한 것을 생략 하고 있다.

 

---

Abstract data type - Wikipedia