더블 연결 리스트(Double Linked List)

  • 더블 연결 리스트는 연결 리스트의 한 종류입니다. 연결 리스트는 한 방향으로만 노드를 연결한 형태임을 기억한다면, 더블 연결 리스트는 이름대로 양 방향으로 노드를 연결합니다. 즉 한 노드는 다음 노드와 이전 노드를 가리키고 있습니다.

Double Linked List

  • 위 그림을 보면 화살표가 양 방향으로 그려진 것을 볼 수 있습니다. 이는 앞서 설명한 다음 노드와 이전 노드로의 이동이 가능함을 의미합니다.

더블 연결 리스트의 추상 자료형

  • 더블 연결 리스트는 연결 리스트에서 이전 노드를 가리키는 부분이 추가된 버전입니다. 따라서 노드 구조체와 기능 내부적인 구현이 조금 달라집니다. 하지만 연결 리스트의 추상 자료형은 모두 동일하기 때문에 사용법은 동일합니다.
 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);

더블 연결 리스트의 구현

  • 더블 연결 리스트는 연결 리스트에서 이전 노드로의 이동이 가능한 리스트입니다. 따라서 이전 노드를 조회하는 기능이 추가되었습니다.
  • 한 가지 중요한 점은 노드의 데이터 삭제 부분입니다. 연결 리스트에서는 현재 노드를 삭제한 뒤 이전 노드가 가리키는 다음 노드만을 수정하면 되었습니다. 하지만 더블 연결 리스트에서는 삭제된 노드의 다음 노드가 이전 노드를 가리키는 것을 수정해야 합니다. (다음 노드의 이전 노드가 삭제된 노드이기 때문입니다.)
  • 또한 더블 연결 리스트를 간편하게 더블 리스트(Double List)라고 부르기도 합니다.

더블 연결 리스트의 헤더 파일

  • 노드의 구성이 다음 노드를 연결하는 포인터와 이전 노드를 연결하는 포인터로 되어있는 점을 주의깊게 봐야 합니다.
 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

#ifndef __DOUBLE_LINKED_LIST__
#define __DOUBLE_LINKED_LIST__

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

#define TRUE 1
#define FALSE 0

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

typedef struct _DoubleLinkedList
{
    Node* head; // 시작 노드
    Node* current; // 현재 노드
    Node* tail; // 꼬리 노드
    int numberOfData;
} DoubleLinkedList;

typedef DoubleLinkedList 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 // !__DOUBLE_LINKED_LIST__

더블 연결 리스트의 구현

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

초기화

  • 더블 연결 리스트의 구조체가 다음과 같이 정의되어 있습니다.
1
2
3
4
5
6
7

typedef struct _DoubleLinkedList
{
    Node* head; // 시작 노드
    Node* current; // 현재 노드
    Node* tail; // 꼬리 노드
    int numberOfData;
} DoubleLinkedList;
  • 연결 리스트에서 사용한 더미 노드 기법을 응용하도록 하겠습니다. 더미 노드를 사용할 경우 구현이 조금 더 간편해지는 장점이 있습니다. 더블 연결 리스트는 더미 노드가 시작과 끝에 존재해야 하기 때문에 시작 노드와 꼬리 노드가 있습니다. 꼬리 노드의 이전 노드가 마지막 노드임을 기억해야 합니다.
  • 초기화 코드를 살펴보겠습니다.
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24

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

    plist->tail = (List*)malloc(sizeof(Node));
    if (plist->tail == NULL)
    {
        free(plist->head);
        return;
    }

    plist->head->prev = NULL;
    plist->head->next = plist->tail;

    plist->tail->next = NULL;
    plist->tail->prev = plist->head;

    plist->numberOfData = 0;
}
  • 초기화 코드가 다소 복잡합니다. 천천히 알아보도록 하겠습니다.
    • plist->head->prev가 의미하는 것은 시작 노드의 이전 노드를 의미합니다. 시작 노드의 이전 노드는 존재하지 않으므로 NULL로 초기화합니다.
    • plist->head->next는 시작 노드의 다음 노드를 의미합니다. 초기화된 더블 연결 리스트는 시작 노드와 마지막(꼬리) 노드만을 갖고 있으므로, 꼬리 노드를 가리킵니다.
    • plist->tail->next는 꼬리 노드의 다음 노드를 의미합니다. 꼬리 노드의 다음 노드는 존재하지 않으므로 NULL로 초기화합니다.
    • plist->tail->prev는 꼬리 노드의 이전 노드를 의미합니다. 꼬리 노드의 이전 노드는 시작 노드이므로, 시작 노드를 가리킵니다.

데이터 삽입

  • 더블 연결 리스트는 데이터를 추가할 경우 다음과 같은 노드의 연결을 수정해야 합니다.
    1. 추가된 노드의 next -> 다음 노드
    2. 추가된 노드의 prev -> 이전 노드
    3. 이전 노드의 next -> 추가된 노드
    4. 다음 노드의 prev -> 추가된 노드
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

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

    newNode->data = data;

    // 2번
    newNode->prev = plist->tail->prev;
    // 3번
    plist->tail->prev->next = newNode;

    // 1번
    newNode->next = plist->tail;
    // 4번
    plist->tail->prev = newNode;

    plist->numberOfData++;
}

데이터 조회

  • 데이터를 조회하는 방법은 리스트의 조회와 원리가 동일합니다. 마지막 더미 노드인 tail을 찾으면 되는데요.
 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

// 데이터 조회(첫 번째)
int getFirstListData(List* plist, ListData* pdata)
{
    // head->next가 tail이면 데이터가 없는 상태
    if (plist->head->next == plist->tail)
    {
        return FALSE;
    }

    plist->current = plist->head->next;
    *pdata = plist->current->data;

    return TRUE;
}

// 데이터 조회(두 번째 이후)
int getNextListData(List* plist, ListData* pdata)
{
    // current의 다음 노드가 tail이면 마지막 노드인 상태
    if (plist->current->next == plist->tail)
    {
        return FALSE;
    }

    plist->current = plist->current->next;
    *pdata = plist->current->data;

    return TRUE;
}

데이터 삭제

  • 중간에 데이터가 삭제되면 두 가지 수정이 필요합니다.
    1. 이전 노드의 next를 current->next로 수정
    2. current->next->prev를 이전 노드로 연결
  • 또한 current의 위치를 조정하여 데이터 조회 시 건너뛰지 않도록 합니다.
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18

// 데이터 삭제
ListData removeListData(List* plist)
{
    Node* rpos = plist->current;
    ListData remv = rpos->data;

    // 1번
    plist->current->prev->next = plist->current->next;
    // 2번
    plist->current->next->prev = plist->current->prev;

    plist->current = plist->current->prev;

    free(rpos);
    plist->numberOfData--;

    return remv;
}

추가적인 함수

  • 추가적인 함수는 배열 리스트의 구현과 동일합니다.
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

// DoubleList.c
#include <stdlib.h>

#include "DoubleList.h"

void initList(List* plist)
{
    plist->head = (List*)malloc(sizeof(Node));
    if (plist->head == NULL)
    {
        return;
    }

    plist->tail = (List*)malloc(sizeof(Node));
    if (plist->tail == NULL)
    {
        free(plist->head);
        return;
    }

    plist->head->prev = NULL;
    plist->head->next = plist->tail;

    plist->tail->next = NULL;
    plist->tail->prev = plist->head;

    plist->numberOfData = 0;
}

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

    newNode->data = data;

    newNode->prev = plist->tail->prev;
    plist->tail->prev->next = newNode;

    newNode->next = plist->tail;
    plist->tail->prev = newNode;

    plist->numberOfData++;
}

// 데이터 조회(첫 번째)
int getFirstListData(List* plist, ListData* pdata)
{
    if (plist->head->next == plist->tail)
    {
        return FALSE;
    }

    plist->current = plist->head->next;
    *pdata = plist->current->data;

    return TRUE;
}

// 데이터 조회(두 번째 이후)
int getNextListData(List* plist, ListData* pdata)
{
    if (plist->current->next == plist->tail)
    {
        return FALSE;
    }

    plist->current = plist->current->next;
    *pdata = plist->current->data;

    return TRUE;
}

// 데이터 삭제
ListData removeListData(List* plist)
{
    Node* rpos = plist->current;
    ListData remv = rpos->data;

    plist->current->prev->next = plist->current->next;
    plist->current->next->prev = plist->current->prev;

    plist->current = plist->current->prev;

    free(rpos);
    plist->numberOfData--;

    return remv;
}

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