선형 & 비선형 자료구조

선형 자료구조(Linear Data Struct)는 데이터가 순차적인 형태로 저장되는 것을 의미합니다. 아래 그림을 보면 A, B, C, D 자료가 순차적으로 저장된 것을 볼 수 있습니다.

Linear Data Struct

비선형 자료구조(Non-Linear Data Struct)는 데이터가 비순차적인 형태로 저장됩니다. 대표적으로 트리(Tree)와 그래프(Graph)가 있습니다. 선형 자료구조와는 반대로 자료의 저장 형태가 다릅니다.

Non-Linear Data Struct

리스트(List)

리스트는 선형 자료구조를 대표하는 자료구조입니다. 따라서 데이터의 저장 형태가 앞서 설명한 선형 자료구조와 동일한 형태입니다.
리스트는 구현 방식에 따라서 배열 리스트(Array List)와 연결 리스트(Linked List)로 구분합니다. 배열 리스트는 C 언어에서 제공하는 배열을 사용합니다. 반대로 연결 리스트는 포인터를 사용하여 자료가 서로 연결된 것처럼 구성합니다.
- 연결 리스트는 연결 구조에 따라 다양한 형태를 갖고 있습니다. 한쪽 방향으로만 연결되어 있는 연결 리스트와 양쪽 방향으로 연결되어 있는 더블 연결 리스트(Double Linked List), 원형 형태로 연결된 원형 연결 리스트(Circular Linked List)가 있습니다.

리스트의 추상 자료형

추상 자료형(Abstract Data Type)은 기능의 구체적인 구현 방법을 명세하지 않고 기능의 형태나 동작을 대략적으로 나타낸 것을 의미합니다. 자료구조를 공부할 때 자료구조를 직접 구현하는 것보다 해당 자료구조의 의미와 동작을 이해하는 것이 더 중요합니다. C++의 vector나 map 같은 자료구조를 사용할 때 해당 자료구조의 구현을 공부하진 않는 것과 같습니다.
추상 자료형과 비슷한(동일한) 개념은 객체지향 프로그래밍에서 정보 은닉(Information Hiding) 개념입니다. 외부(사용자)에게 구체적인 구현 방법과 자료구조 또는 객체를 사용함에 있어서 불필요한 정보를 제공하지 않습니다. 따라서 추상 자료형은 철저히 자료구조를 사용하는 사람의 입장에서 정의가 되어야 합니다.
그렇다면 리스트의 추상 자료형은 어떻게 정의할 수 있을까요? 일반적으로 리스트를 사용함에 있어서 필수적인 정보만을 작성합니다. 리스트를 활용하여 다른 기능을 수행하도록 하는 것은 리스트를 사용하는 사람의 몫으로 남겨두는 것이 원칙입니다.
리스트의 필수적인 요소는 초기화(Initialize), 데이터 삽입(추가), 데이터 조회, 데이터 삭제, 리스트 삭제가 있을 것입니다. 만약 필요에 따라 다른 것이 추가되어야 한다면 얼마든지 추가해도 괜찮습니다.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
// 리스트의 추상 자료형

// 리스트 초기화
void initList(List* plist);

// 데이터 삽입(추가)
void insertList(List* plist, ListData data);

// 데이터 조회(첫 번째)
void getFirstListData(List* plist, ListData* pdata);

// 데이터 조회(두 번째 이후)
void getNextListData(List* plist, ListData* data);

// 데이터 삭제
ListData removeListData(List* plist);

// 추가적인 함수
int getListLength(List* plist);

리스트의 추상 자료형을 정의하였으니, 이제 리스트의 구현을 확인해볼까요?

배열 리스트의 구현

배열 리스트는 배열을 활용한 리스트입니다. 참고로 배열 또한 자료구조의 한 종류입니다. 이처럼 어떤 자료구조를 사용하여 다른 자료구조를 구성하는 것은 매우 자연스러운 일입니다.
C 언어에서 배열은 어떤 특징을 갖고 있을까요? 배열을 사용하는 방법은 크게 두 가지입니다.
- 고정된 크기를 갖는 배열을 사용하는 방법
- 동적 할당을 사용하여 임의의 크기를 갖는 배열을 사용하는 방법
배열을 사용하는 방법은 다르지만, 공통된 특징이 존재합니다. 바로 인덱싱(Indexing)을 사용하여 데이터 할당 및 조회가 가능하다는 특징입니다. 이러한 특징을 잘 기억하고 구체적인 부분을 하나씩 구현해보도록 하겠습니다.

배열 리스트의 헤더 파일

자료구조를 사용할 때는 저장하려는 데이터가 무엇인지 고민할 필요가 없습니다. 어떤 데이터든 자료구조는 자료구조대로 동작이 가능해야 합니다. 따라서 어떤 데이터를 저장할지는 사용자가 결정할 수 있도록 하겠습니다.
또한 여기서는 고정된 크기를 갖는 배열 리스트를 사용하겠습니다. 배열 리스트는 필요 이상의 메모리 공간을 점유한다는 단점이 있습니다. 하지만 데이터의 추가 및 삭제에 불필요한 메모리 할당 및 삭제가 없기 때문에 빠르다는 장점도 있습니다.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
// ArrayList.h

#ifndef __ARRAY_LIST__
#define __ARRAY_LIST__

typedef int ListData; // 저장할 데이터 타입
#define LIST_LENGTH 100 // 리스트의 최대 크기

#define TRUE 1
#define FALSE 0

typedef struct __ArrayList
{
    ListData data[LIST_LENGTH]; // 리스트 저장소
    int numberOfData; // 저장된 데이터의 수
    int currentIndex; // 현재 데이터의 인덱스
} ArrayList;

typedef ArrayList List;

// 리스트의 추상 자료형
// 리스트 초기화
void initList(List* plist);

// 데이터 삽입(추가)
void insertList(List* plist, ListData data);

// 데이터 조회(첫 번째)
int getFirstListData(List* plist, ListData* pdata);

// 데이터 조회(두 번째 이후)
int getNextListData(List* plist, ListData* pdata);

// 데이터 삭제
ListData removeListData(List* plist);

// 추가적인 함수
int getListLength(List* plist);

#endif // !__ARRAY_LIST__

배열 리스트의 구현

헤더 파일이 정의되었으니, 실제 구현을 하나씩 진행해보도록 하겠습니다.

초기화

배열 리스트의 구조체를 정의할 때 배열의 크기를 정의하였습니다. 따라서 리스트를 생성할 당시 배열이 생성되기 때문에 배열의 크기를 초기화할 필요가 없습니다.
또한 리스트 초기화 단계이기 때문에 배열에 저장된 데이터가 존재하지 않습니다.
- 따라서 데이터의 수(numberOfData)는 0으로 설정합니다.
- 현재 인덱스(currentIndex)는 -1로 설정합니다. C 언어는 배열의 시작 인덱스가 0이기 때문에 현재 인덱스를 0으로 설정하면 안 됩니다.

1
2
3
4
5
6
// 리스트 초기화
void initList(List* plist)
{
    plist->numberOfData = 0;
    plist->currentIndex = -1;
}

데이터 삽입

배열 리스트는 배열의 인덱스를 활용하면 데이터 삽입이 매우 간단합니다. 리스트를 초기화할 때 저장된 데이터의 수를 0으로 설정하였기 때문에 이를 인덱스로 활용합니다.
한 가지 중요한 점은 배열이 가득 차면 데이터를 입력할 수 없다는 점입니다. 현재 저장된 데이터의 크기를 반환하는 함수를 작성할 것이기 때문에 이를 활용하여 배열의 크기를 벗어나는지 검사하는 로직을 추가합니다.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
// 데이터 삽입(추가)
void insertList(List* plist, ListData data)
{
    if (getListLength(plist) >= LIST_LENGTH)
    {
        printf("Failed to insert data to Array List\nArray List is full.\n");

        return;
    }

    plist->data[plist->numberOfData] = data;
    plist->numberOfData++;

    return;
}

데이터 조회

데이터를 조회하는 함수는 두 가지로 구분하였습니다.

1
2
3
4
5
// 데이터 조회(첫 번째)
void getFirstListData(List* plist, ListData* pdata);

// 데이터 조회(두 번째 이후)
void getNextListData(List* plist, ListData* data);

이렇게 한 이유는 순차적으로 데이터를 조회할 때 인덱스 정보를 활용하기 위해서입니다. 첫 번째 데이터 조회 함수에서 리스트의 인덱스를 배열의 초기 위치로 지정하기 위해 첫 번째 데이터를 조회하는 함수를 작성하였습니다. 이 자료구조를 사용하는 사용자에게 반드시 첫 번째 데이터 조회를 먼저 호출하도록 안내를 해야 합니다.
자료구조를 구현함에 있어 방법이 다양하기 때문입니다. 다음과 같이 두 가지 방법이 존재합니다. (혹은 더 많은, 효율적인 방법이 존재할 수 있습니다.)
- 지금처럼 첫 번째 데이터를 조회하는 함수와 두 번째 이후 데이터를 조회하는 함수를 만들어도 됩니다.
- 리스트의 인덱스를 배열의 시작 위치로 조정하는 함수와 전체 데이터를 조회하는 함수를 만들어도 됩니다.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
// 데이터 조회(첫 번째)
int getFirstListData(List* plist, ListData* pdata)
{
    if (getListLength(plist) == 0)
    {
        printf("Array list is empty\n");

        return FALSE;
    }

    plist->currentIndex = 0;
    pdata = plist->data[plist->currentIndex];

    return TRUE;
}

// 데이터 조회(두 번째 이후)
int getNextListData(List* plist, ListData* pdata)
{
    if (plist->currentIndex >= (getListLength(plist) - 1))
    {
        printf("End of array list\n");
        
        return FALSE;
    }

    plist->currentIndex++;
    pdata = plist->data[plist->currentIndex];

    return TRUE;
}

데이터 삭제

배열 리스트에서 데이터를 삭제하는 부분은 조금 고민이 필요한 사항입니다.
만약 [A, B, C, D, E] 배열이 존재하는 상황에서 데이터 C을 삭제하면 어떻게 될까요? 남겨진 배열은 [A, B, D, E]가 됩니다. 즉 배열 리스트에서 데이터를 삭제하면 삭제한 데이터 이후의 모든 데이터를 앞으로 한 칸 당겨야 합니다.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
// 데이터 삭제
ListData removeListData(List* plist)
{
    int rpos = plist->currentIndex; // 삭제할 데이터의 인덱스
    ListData rdata = plist->data[rpos]; // 삭제할 데이터

    // 삭제할 데이터의 인덱스부터, 마지막 데이터까지 순회하면서 데이터를 덮어씌운다.
    for (int i = rpos; i < plist->numberOfData - 1; i++)
    {
        plist->data[i] = plist->data[i + 1];
    }

    // 데이터를 삭제하였으니, 데이터의 수와 인덱스를 하나씩 감소한다.
    plist->numberOfData--;
    plist->currentIndex--;

    return rdata;
}

여기서 한 가지 중요한 점은 배열 리스트의 현재 인덱스를 하나 감소한다는 점입니다. 왜 그럴까요? [A, B, C, D, E] 배열에서 데이터 C의 인덱스는 2입니다. 데이터 C를 삭제하면 [A, B, D, E] 배열이 됩니다. 이 배열에서 인덱스 2의 데이터는 무엇일까요? 바로 D가 됩니다. 배열을 삭제할 뿐인데 다음 데이터를 가리키고 있는 상황입니다.
우리가 구현한 두 번째 이후 데이터 조회 함수(getNextListData)를 보면 배열 리스트의 현재 인덱스를 하나 증가한 다음에 데이터를 조회합니다. 바로 첫 번째 데이터 조회 함수(getFirstListData)에서 현재 인덱스를 0으로 설정하였기 때문입니다.
만약 데이터를 삭제한 이후 현재 인덱스를 하나 감소하지 않는다면, 현재 인덱스는 바로 다음 데이터(D)를 가리키고 있습니다. 여기서 데이터를 조회한다면 현재 데이터(D)를 건너뛰고 다음 데이터(E)를 조회하게 됩니다. 조회할 데이터가 하나 빠지게 되는 경우입니다. 이런 경우를 방지하기 위해 데이터를 삭제하는 과정에서 현재 인덱스를 하나 감소하게 하여 정상적인 데이터를 조회하도록 합니다.

추가적인 함수

추가 함수로 배열 리스트의 저장된 데이터의 수를 반환하는 함수를 작성하였습니다. 해당 함수는 매우 간단하므로 별도의 설명을 작성하지 않겠습니다.

1
2
3
4
5
// 추가적인 함수
int getListLength(List* plist)
{
    return plist->numberOfData;
}

전체 소스 코드

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
// "ArrayList.c"

#include <stdio.h>

#include "ArrayList.h"

// 리스트 초기화
void initList(List* plist)
{
    plist->numberOfData = 0;
    plist->currentIndex = -1;
}

// 데이터 삽입(추가)
void insertList(List* plist, ListData data)
{
    if (getListLength(plist) >= LIST_LENGTH)
    {
        printf("Failed to insert data to Array List\nArray List is full.\n");

        return;
    }

    plist->data[plist->numberOfData] = data;
    plist->numberOfData++;

    return;
}

// 데이터 조회(첫 번째)
int getFirstListData(List* plist, ListData* pdata)
{
    if (getListLength(plist) == 0)
    {
        printf("Array list is empty\n");

        return FALSE;
    }

    plist->currentIndex = 0;
    pdata = plist->data[plist->currentIndex];

    return TRUE;
}

// 데이터 조회(두 번째 이후)
int getNextListData(List* plist, ListData* pdata)
{
    if (plist->currentIndex >= (getListLength(plist) - 1))
    {
        printf("End of array list\n");
        
        return FALSE;
    }

    plist->currentIndex++;
    pdata = plist->data[plist->currentIndex];

    return TRUE;
}

// 데이터 삭제
ListData removeListData(List* plist)
{
    int rpos = plist->currentIndex; // 삭제할 데이터의 인덱스
    ListData rdata = plist->data[rpos]; // 삭제할 데이터

    // 삭제할 데이터의 인덱스부터, 마지막 데이터까지 순회하면서 데이터를 덮어씌운다.
    for (int i = rpos; i < plist->numberOfData - 1; i++)
    {
        plist->data[i] = plist->data[i + 1];
    }

    // 데이터를 삭제하였으니, 데이터의 수와 인덱스를 하나씩 감소한다.
    plist->numberOfData--;
    plist->currentIndex--;

    return rdata;
}

// 추가적인 함수
int getListLength(List* plist)
{
    return plist->numberOfData;
}

선형 & 비선형 자료구조#

리스트(List)#

리스트의 추상 자료형#

배열 리스트의 구현#

배열 리스트의 헤더 파일#

배열 리스트의 구현#

초기화#

데이터 삽입#

데이터 조회#

데이터 삭제#

추가적인 함수#

전체 소스 코드#

선형 & 비선형 자료구조

리스트(List)

리스트의 추상 자료형

배열 리스트의 구현

배열 리스트의 헤더 파일

배열 리스트의 구현

초기화

데이터 삽입

데이터 조회

데이터 삭제

추가적인 함수

전체 소스 코드