자료구조(Data Structure)와 추상자료형(ADT)

자료구조와 알고리즘

컴퓨터가 기본적으로 하는 일은 아래와 같다.

• 데이터 저장
• 데이터 연산

이 기준으로 자료구조와 알고리즘을 정의 내릴 수 있다.

• 자료구조는 데이터를 저장할 때, 어떻게 하면 컴퓨터가 처리하기 쉽게 만드는지를 다루는 것이다.
• 알고리즘은 데이터를 연산할 때, 어떻게 하면 컴퓨터가 처리하기 쉽게 만드는지를 다루는 것이다.

다시 말해 자료구조(Data Structure)는 자료를 저장하는 방법이고, 알고리즘(Algorithm)은 문제를 효율적으로 해결하기 위한 방법이라고 할 수 있다.

모든 상황에 좋은 자료구조는 존재하지 않으므로, 상황에 따라 효율적인 자료구조를 선택하고 알고리즘을 구현해야 한다. 또한 알고리즘을 적용하지 않아도 문제를 해결할 수 있지만, 문제의 크기가 커진다면 성능을 위해 반드시 고려해야 한다.

자료구조와 추상자료형

좀 더 깊게 들어가서 추상자료형(Abstract Data Type)은 무엇일까?

추상자료형이란 기능의 구현 부분을 나타내지 않고, 데이터의 형태와 그 데이터의 연산들을 정의한 것이다. 그리고 추상자료형이 정의한 연산들을 구현한 구현체가 바로 자료구조(Data structure)인 것이다.

예를 들어보자. 스택(Stack)도 추상자료형이다. 스택의 형태는 LIFO(Last In First Out) 값들의 모임이고 push, pop, size 같은 연산을 정의할 수 있다. 그렇지만 스택이 내부적으로 배열로 구현되는지, 연결 리스트로 구현되는지, 또는 size 연산을 수행할 때 원소의 개수를 일일이 세는지, 아니면 개수를 따로 저장해 두는지와 같은 세부사항들은 추상자료형에서는 다루지 않으며, 그걸 다루기 시작하면 자료구조의 영역으로 넘어가게 된다. 즉, 추상자료형은 구현 방법을 명시하지 않는다.

둘은 명백히 구분되지만, 추상자료형과 그것을 구현한 자료구조의 이름이 비슷하거나 아예 같은 경우가 많다. 이를 구분하는 법은 조금이라도 구현 방법이 정해져 있는지 보는 것이다.

스택이나 큐는 구현 방법이 전혀 정의되어 있지 않으므로 추상자료형이고, 배열은 연속적으로 저장되어 있도록 구현되어 있어야 하므로 자료구조이며, 연결 리스트도 다음 데이터의 위치를 저장하는 방식으로 정해져 있으니 자료구조이다.

따라서 자료구조와 추상자료형은 구분해 쓰는 것이 맞지만, 자료구조라는 단어가 광범위하게 쓰이다 보니 아래처럼 추상자료형도 포함해서 자료구조라고 정의되곤 한다.

자료구조의 분류

구현에 따라

• 배열
• 튜플
• 연결 리스트
• 원형 연결 리스트
• 이중 연결 리스트
• 해시 테이블

형태에 따라

• 선형 구조
  • 스택
  • 큐
  • 덱
• 비선형 구조
  • 그래프
    • 유향 그래프
    • 무향 그래프
  • 트리
    • 이진트리
    • 힙

References

• 나무위키 - 자료구조
• 위키백과 - 자료구조