C언어로 배우는 자료구조

👋 소개

컴퓨터 과학에서 빠질 수 없는 자료구조에 대해 소개하려고 한다.

개발을 하게 되면 다양한 형태의 데이터를 다루게 되는데 이를 효과적으로 처리하고, 관리하는 관점에서 자료구조는 상당히 중요하다고 볼 수 있다.

기본적인 개념을 짚어보고, C언어로 구현해보며 자료구조를 익혀나가도록 하자.

📖 목차

총 7가지 자료구조에 대해 알아볼 수 있도록 구성했다.

1. 배열(Array)
2. 스택(Stack)
3. 큐(Queue)
4. 연결 리스트(Linked list)
5. 해시 테이블(Hash table)
6. 그래프(Graph)
7. 트리(Tree)

🔥 알고 있어야 하는 것

📦 자료형 (Data Type)

자료형이란, 컴퓨터 과학과 프로그래밍 언어에서 다루게 되는 데이터들을 구분하고 분류하기 위한 개념이다.
컴퓨터는 실제로 0, 1 로 구성된 값을 다루는데 이를 구분하고 분류하기 위해 자료형을 사용한다.

메모리에 아래와 같은 값이 할당되어있다고 가정하자.

00000000 00010010 11010000 00100100

이 값은 어떤 값을 나타내는 것일까?
여기서 대답할 수 있는 사람은 아무도 없을 것이다.

단순히 2진수 > 10진수로 변환하여 해석할 수도 있지만, 컴퓨터는 0, 1로만 값을 표현하기 때문에, 섣불리 10진수로 변환하기엔 무리가 있다. (즉, 어떤 형태의 값을 표현하고자 하는지 알 수 없다)

예상했던 것처럼 10진수 정수형 값을 나타내는지, 아니면 문자열 값 일부를 나타내는 것인지 어떻게 알 것인가?
오늘날 대부분의 프로그래밍 언어는 기본적으로 자료형을 따르기 때문에 이러한 문제가 없다.

프로그래머가 위의 값을 아래 조건에 맞게 변수를 선언하고, 값을 할당했다고 하자.

- 이 값은 4바이트(32비트) 공간을 차지해.
- 그리고 이 값은 정수형 값이야.

C언어 기준으로 보면 int 형태의 값임을 유추할 수 있을 것이다. 여기서 int 가 자료형에 해당한다.

int 라는 자료형만 보고도 값의 형태(정수형 숫자)를 알 수 있고, 이 값이 어느 정도의 공간을 차지(4바이트)하는지 알 수 있다.

이 외에도 실수(float, double), 문자(char) 등 여러 형태의 값이 존재하는데 이를 구분하고 분류하기 위해 자료형을 사용한다.

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

추상 자료형은 어떠한 대상의 기능들을 단순히 나열(정의)한 것이며, 기능에 대한 세부 구현사항은 나타내지 않는다.
추상(Abstract)이라는 단어만 들어도 이미 뭔진 모르겠지만 붕 떠있는 기분이 드는데, 그 느낌이 든다면 정상이다.

한 가지 예를 들어보도록 하겠다.

- 커피를 만들 수 있는 바리스타 A가 있다.
- 커피를 마시고자 하는 손님 B가 있다.

손님 B는 커피를 마시기 위해 카페로 이동한 후 아메리카노를 주문한다.
바리스타 A는 주문을 받고, 본인만의 노하우로 커피를 내려 손님에게 제공한다.

여기서 B는 A가 커피를 어떻게 만드는지 구체적으로 알 필요가 없다.
단지 커피를 주문하고, 결과물인 커피를 받아서 본인이 이루고자 하는 목적(커피 마시기)을 달성하면 되기 때문이다.

바리스타 A를 추상 자료형으로 나타내면 아래와 같이 정의할 수 있을 것이다.

A {
  takeOrder();
  makeCoffee();
}

정말 A가 하던 행위(기능)가 나열되어 있기만 할 뿐 세부 구현사항은 보이지 않는다.
본 예시를 추상 자료형의 정의에 대입해보면 어느 정도 가닥이 잡힐 것이다.

어떠한 기능들을 나열(주문 받기/커피 제조)한 것이며, 세부 구현 사항은 나타내지 않는다.

B의 관점에서 보면 메뉴 주문을 어떻게 관리하고 있는지, 커피가 어떤 과정을 거쳐 만들어지는지 궁금하지 않은 것은 어찌 보면 당연해 보인다. 그렇다면 자료구조와 추상 자료형은 무슨 관계가 있을까? 추상 자료형은 설계도와 같고, 자료구조는 이를 실제로 구현한 형태라고 볼 수 있다. 앞으로 알아볼 스택(Stack)은 자료를 넣고, 뺄 수 있다.

추상 자료형 관점으로 바라보면 자료를 넣는 기능과 뺄 수 있는 기능이 필요한데, 아래와 같이 나타낼 수 있다.

Stack {
  push();
  pop();
}

이러한 추상 자료형을 구현하게 되면 자료구조로써의 스택이 된다. 앞으로 몇 가지 자료구조에 대해 개념적으로 먼저 알아보고, 직접 구현해보며 익혀보도록 하자.