연결 리스트(Linked List)

일반적으로 리스트를 생각하면 연결 리스트를 떠올리곤 합니다. 그만큼 리스트를 구현하는 방법 중 연결 리스트를 많이 채택하고 있습니다. 앞에서 배열 리스트에 대해 알아보았는데 배열 리스트는 치명적인 단점이 존재합니다. 배열 리스트는 메모리의 낭비가 존재한다는 점 입니다.
연결 리스트는 데이터를 동적으로 할당하여 데이터들끼리 연결합니다. 추가되는 데이터를 그때그때 메모리에 할당하기 때문에 메모리 낭비가 존재하지 않습니다. 하지만 배열 리스트와 다르게 데이터의 접근이 불편합니다. 찾고자 하는 데이터의 위치를 파악하기 위해서는 각 연결된 데이터들을 하나씩 찾아봐야 하기 때문입니다.
연결 리스트가 어떤 특징이 있는지 확인하였으니, 이제 추상 자료형을 살펴볼까요?

연결 리스트의 추상 자료형

연결 리스트의 추상 자료형은 배열 리스트의 추상 자료형과 동일합니다. 아니 구현 방법이 다른데 추상 자료형이 같을 수가 있을까요?
추상 자료형을 ‘추상 자료형(Abstract Data Type)은 기능의 구체적인 구현 방법을 명세하지 않고 기능의 형태나 동작을 대략적으로 나타낸 것을 의미’한다고 하였습니다. 리스트의 형태나 동작은 겉으로 보기에는 동일합니다. 사용자의 입장에서 리스트가 배열 리스트인지, 연결 리스트인지는 중요하지 않습니다. 리스트의 특징을 갖는 자료구조를 잘 사용할 수만 있으면 되기 때문입니다.

 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 언어에서는 메모리의 주소를 가리키는 포인터를 사용하여 연결할 수 있습니다.
또한 연결 리스트는 데이터를 연결하는 형태에 따라 다양한 형태로 구분할 수 있다고 하였습니다. 여기서는 가장 기본적인 단방향 연결 리스트를 먼저 살펴보고 추가적인 리스트에 대해 확인해보겠습니다.

연결 리스트의 헤더 파일

앞서 공부한 배열 리스트와 노드의 구성이 어떻게 다른지 주의 깊게 살펴보는 것이 중요합니다.

 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
// LinkedList.h

#ifndef __LINKED_LIST__
#define __LINKED_LIST__

typedef int ListData; // 저장할 데이터 타입

#define TRUE 1
#define FALSE 0

typedef struct _Node
{
    ListData data;
    struct _Node* next; // 다음 노드를 연결하는 포인터
} Node;

typedef struct _LinkedList
{
    Node* head; // 시작 노드
    Node* current; // 현재 노드
    Node* before; // 이전 노드
    int numberOfData;
} LinkedList;

typedef LinkedList 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 // !__LINKED_LIST__

배열 리스트에는 존재하지 않았던 노드(Node) 구조체가 추가되었습니다. 배열 리스트는 사용자가 사용하려는 자료형을 단순 배열로 구현할 수 있었지만, 연결 리스트는 다음 데이터를 가리키기 위해 포인터 자료형이 필요합니다. 사용자가 사용하려는 자료를 담는 변수와 다음 노드를 가리킬 포인터 변수를 갖는 하나의 구조체를 노드라고 합니다.
이미 배열 리스트를 공부하였기 때문에 구조체의 변화 빼고는 비교적 쉽게 정의할 수 있었습니다.

연결 리스트의 구현

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

초기화

연결 리스트의 구조체가 다음과 같이 정의되어 있습니다.

1
2
3
4
5
6
7
typedef struct _LinkedList
{
    Node* head; // 시작 노드
    Node* current; // 현재 노드
    Node* before; // 이전 노드
    int numberOfData;
} LinkedList;

해당 리스트를 초기화하기 위해 없음을 의미하는 NULL로 포인터를 초기화합니다.
단 시작 노드인 head는 두 가지 방법이 존재하는데요.
- NULL 초기화: 더미 노드를 생성하지 않으므로 약간의 메모리 절약이 장점으로 있다. 단 head가 NULL 인 경우와 아닌 경우를 구분해야 하기 때문에 코드가 복잡해진다.
- 더미 노드 초기화: 더미 노드를 생성하지만 head가 NULL인 경우가 없으므로 코드가 단순해진다.
구현의 장점을 갖는 방법은 더미 노드를 갖는 방법입니다. 따라서 더미 노드를 갖는 방법으로 초기화를 진행합니다.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
// 리스트 초기화
void initList(List* plist)
{
    plist->head = (Node*)malloc(sizeof(Node));
    if (plist->head == NULL)
    {
        return;
    }
    plist->current = NULL;
    plist->before = NULL;

    plist->numberOfData = 0;
}

데이터 삽입

연결 리스트는 데이터를 추가하기 위해 노드를 그때그때 생성합니다.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
// 데이터 삽입(추가)
void insertList(List* plist, ListData data)
{
    Node* newNode = (Node*)malloc(sizeof(Node));
    if (newNode == NULL)
    {
        return;
    }

    newNode->data = data;
    newNode->next = plist->head->next;
    
    plist->head->next = newNode;
    plist->numberOfData++;

    return;
}

데이터 추가 코드를 잘 이해해야 합니다.
- 새로운 노드의 다음 노드는 리스트의 더미 노드가 가리키는 다음 노드를 가리키게 합니다.
- 만약 A, B, C 순으로 데이터를 추가한다면 plist->head->nexe는 C를 가리키게 됩니다.
- 이어 C는 B를 가리키고, B는 A를 가리키게 됩니다.
- 즉 연결 리스트는 배열 리스트와 다르게 저장된 데이터의 순서를 유지하지 않습니다.

데이터 조회

연결 리스트의 데이터 조회도 두 가지 함수로 작성합니다.

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
32
33
34
35
36
37
38
39
// 데이터 조회(첫 번째)
int getFirstListData(List* plist, ListData* pdata)
{
    // 데이터가 존재하지 않는다면...
    if (plist->head->next == NULL)
    {
        return FALSE;
    }

    // 첫 번째 데이터를 가리킨다.
    plist->current = plist->head->next;
    // current의 이전 노드를 가리킨다. 여기서는 더미 노드를 의미한다.
    plist->before = plist->head;

    // 데이터 전달
    *pdata = plist->current->data;
    
    return TRUE;
}

// 데이터 조회(두 번째 이후)
int getNextListData(List* plist, ListData* pdata)
{
    // 데이터가 존재하지 않는다면...
    if (plist->current->next == NULL)
    {
        return FALSE;
    }

    // 이전 노드는 현재 노드를 가리킨다.
    plist->before = plist->current;
    // 현재 노드는 다음 노드를 가리킨다.
    plist->current = plist->current->next;

    // 데이터 전달
    *pdata = plist->current->data;
    
    return TRUE;
}

첫 번째와 두 번째 이후 데이터 조회에서 데이터의 존재 여부를 확인하는 부분이 차이가 있습니다.
- 첫 번째 데이터가 존재하지 않는다면 더미 노드가 데이터 노드를 가리키지 않습니다. 즉 NULL을 가리킵니다.
- 두 번째 이후 데이터가 존재하지 않는다면 현재 노드가 다음 데이터 노드를 가리키지 않습니다.
데이터 조회에서 가장 중요한 부분은 다음과 같습니다.

1
2
3
4
5
6
7
// 첫 번째 데이터 조회
plist->current = plist->head->next;
plist->before = plist->head;

// 두 번째 이후 데이터 조회
plist->before = plist->current;
plist->current = plist->current->next;

특히 두 번째 이후 데이터 조회에서 실수로 current가 다음 노드를 먼저 가리키지 않도록 하는 것이 중요합니다.

데이터 삭제

동적 할당된 데이터의 삭제는 free() 함수를 사용합니다.
또한 리스트 중간에 노드가 삭제된다면 노드가 중간에 끊기는 현상이 발생합니다.
- 이를 위해 before 포인터를 생성하였습니다. before 포인터가 항상 다음 노드를 가리킬 수 있도록 합니다.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
// 데이터 삭제
ListData removeListData(List* plist)
{
    // 삭제할 노드가 현재 노드를 가리키게 한다.
    Node* delNode = plist->current;
    // 데이터를 임시로 저장한다.
    ListData rdata = delNode->data;

    // 노드의 연결 조정한다.
    plist->before->next = plist->current->next;
    // 현재 노드가 이전 노드를 가리키게 한다.
    plist->current = plist->before;

    // 노드 삭제
    free(delNode);
    plist->numberOfData--;

    return rdata;
}

plist->before->next = plist->current->next 코드를 유의해서 봐야 합니다.
- 이전 노드의 다음 노드를 현재 노드의 다음 노드로 가리키게 해야 합니다.
- 이렇게 해야 노드가 끊기지 않고 계속 연결된 상태를 유지할 수 있습니다.

추가적인 함수

추가적인 함수는 배열 리스트의 구현과 동일합니다.

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
 86
 87
 88
 89
 90
 91
 92
 93
 94
 95
 96
 97
 98
 99
100
101
102
103
104
105
// LinkedList.c

#include <stdlib.h>
#include <stdio.h>

#include "LinkedList.h"

// 리스트 초기화
void initList(List* plist)
{
    plist->head = (Node*)malloc(sizeof(Node));
    if (plist->head == NULL)
    {
        return;
    }
    plist->head->next = NULL;
    plist->current = NULL;
    plist->before = NULL;

    plist->numberOfData = 0;
}

// 데이터 삽입(추가)
void insertList(List* plist, ListData data)
{
    Node* newNode = (Node*)malloc(sizeof(Node));
    if (newNode == NULL)
    {
        return;
    }

    newNode->data = data;
    newNode->next = plist->head->next;
    
    plist->head->next = newNode;
    plist->numberOfData++;

    return;
}

// 데이터 조회(첫 번째)
int getFirstListData(List* plist, ListData* pdata)
{
    // 데이터가 존재하지 않는다면...
    if (plist->head->next == NULL)
    {
        return FALSE;
    }

    // 첫 번째 데이터를 가리킨다.
    plist->current = plist->head->next;
    // current의 이전 노드를 가리킨다. 여기서는 더미 노드를 의미한다.
    plist->before = plist->head;

    // 데이터 전달
    *pdata = plist->current->data;
    
    return TRUE;
}

// 데이터 조회(두 번째 이후)
int getNextListData(List* plist, ListData* pdata)
{
    // 데이터가 존재하지 않는다면...
    if (plist->current->next == NULL)
    {
        return FALSE;
    }

    // 이전 노드는 현재 노드를 가리킨다.
    plist->before = plist->current;
    // 현재 노드는 다음 노드를 가리킨다.
    plist->current = plist->current->next;

    // 데이터 전달
    *pdata = plist->current->data;
    
    return TRUE;
}

// 데이터 삭제
ListData removeListData(List* plist)
{
    // 삭제할 노드가 현재 노드를 가리키게 한다.
    Node* delNode = plist->current;
    // 데이터를 임시로 저장한다.
    ListData rdata = delNode->data;

    // 노드의 연결 조정한다.
    plist->before->next = plist->current->next;
    // 현재 노드가 이전 노드를 가리키게 한다.
    plist->current = plist->before;

    // 노드 삭제
    free(delNode);
    plist->numberOfData--;

    return rdata;
}

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

연결 리스트(Linked List)#

연결 리스트의 추상 자료형#

연결 리스트의 구현#

연결 리스트의 헤더 파일#

연결 리스트의 구현#

초기화#

데이터 삽입#

데이터 조회#

데이터 삭제#

추가적인 함수#

전체 소스 코드#

연결 리스트(Linked List)

연결 리스트의 추상 자료형

연결 리스트의 구현

연결 리스트의 헤더 파일

연결 리스트의 구현

초기화

데이터 삽입

데이터 조회

데이터 삭제

추가적인 함수

전체 소스 코드