[자료구조] 동적할당을 이용한 연결 리스트(Linked List) 구현

리스트(List)
 - 자료구조의 하나, 데이터를 일렬로 순차적으로 나열한 형태

리스트를 구현하는 방법에는 배열을 이용하는 방법과 동적할당을 이용해 구현하는 방법이 있습니다.

배열로 구현할 경우,

구현이 간단하고, 인덱스를 참조하여 한번에 참조가 가능하다는 장점을 갖고 있지만,
갯수에 제한이 있어 유한적인 데이터만 넣을 수 있다는 단점을 갖고 있습니다.

동적할당으로 구현을 할 경우,

새로운 자료가 입력될 때마다 새로운 주소로 메모리를 할당해주고
이전에 할당된 메모리를 연결해주므로 메모리 관리에 용이하다고 볼 수 있습니다.

그래서 연결리스트(Linked List)란 각 노드가 데이터와 포인터를 갖고 있어,
각 노드가 다음 순서의 노드의 위치정보를 갖고 있는 방식으로 데이터를 저장하는 자료구조입니다.

연결리스트엔 세가지 종류가 있습니다.

- 단일 연결 리스트(Singly Linked List) : 각 노드에 데이터 공간과 한개의 포인터를 갖고 있어, 노드의 포인터는 다음 노드를 가리킨다.

- 이중 연결 리스트(Doubly Linked List) : 단일 연결 리스트와 모양은 비슷하지만 각 노드가 두개의 포인터를 갖고, 다음 노드 뿐만 아니라 이전 노드도 가리키게 구현한다.

- 원형 연결 리스트(Circular Linked List) : 단일 연결 리스트에서 마지막 노드가 처음 노드를 가르키게 되면 원형 연결 리스트가 된다. 이중연결리스트에서 처음과 끝을 서로 연결하면 이중 원형 연결 리스트

원형 연결 리스트

이중 원형 연결 리스트

여기서는 가장 복잡하다고 할 수 있는 이중 원형 연결 리스트를 구현해보자.

우선, 데이터와 이전 노드, 다음 노드를 가르킬 포인터를 갖고있는 노드를 만듭니다.

typedef struct Node
{
    int data;
    Node* prev;
    Node* next;
}Node;

그리고 이러한 연결된 노드들을 갖고 있는 리스트를 만듭니다.
head는 리스트의 시작노드를, tail은 노드의 끝부분을 가르키는 포인터입니다. count는 노드의 갯수입니다.

typedef struct List
{
    Node* head;
    Node* tail;
    int count;
}List;

다음으로 이런 리스트롤 초기화할 InitList함수를 만듭니다.
InitList() 함수는 List를 동적할당 후, 아직 데이터가 없기 때문에 head와 tail 을 NULL, count를 0값으로 초기화 합니다.

void InitList(List **list)
{
    (*list) = (List*)malloc(sizeof(list));
    (*list)->head = NULL;
    (*list)->tail = NULL;
    (*list)->count = 0;
}

다음, 리스트에 Node를 추가하는 AddNode함수를 구현합니다. 
일반적으로 노드를 추가하는 함수는 리스트의 앞(head 이전)에 추가하거나 리스트의 뒤(tail 이후)에 추가하는 두가지 함수가 있는데,
여기선 tail에 Node를 추가하는 함수를 구현해보겠습니다.

Node* CreateNode(int data)
{
    Node* node = (Node*)malloc(sizeof(Node));
    node->data = data;
    node->prev = NULL;
    node->next = NULL;
    return node;
}
 
void AddNode(List **list, Node* node)
{
    if (!(*list) || !node) return;
    cout << "Add Node - data : " << node->data << endl;
 
    if ((*list)->count == 0)
    {
        (*list)->head = (*list)->tail = node;
        node->next = node->prev = node;
    }
    else
    {
        node->prev = (*list)->tail;
        node->next = (*list)->head;
 
        (*list)->tail->next = node;
        (*list)->head->prev = node;
        (*list)->tail = node;
    }
 
    (*list)->count++;
}

1. (노드가 첫번째로 추가된 경우), head와 tail은 모두 NULL값을 가르키고 있으므로 새로 추가된 node를 가르키게 합니다.(line 17)
  *노드가 하나이므로 head와 tail 모두 새로추가된 하나의 노드를 가르키고 있습니다.

   

새로 추가된 노드는 하나밖에 없으므로 자신을 가르키게 합니다. (line 18)

이후 list->count 갯수를 1증가, list->count는 1이된다.(line 30)

2. (두번째 노드 추가) 다음으로 노드가 추가된 경우, 새로 추가된 노드의 prev는 tail을, next는 head를 가르키게 합니다.(line 22~23)
 * tail 다음에 붙이게 되므로, 새로 추가된 노드의 이전노드는 리스트의 후미를 가르키며, 다음 노드는 head를 가르키게 됩니다.

 다음, tail에 새로운 노드를 추가하는 것이므로, tail의 next는 새로운 노드를 가르키며, head의 prev 역시 새로운 노드를 가르킵니다.(25~26)

마지막으로 list의 tail는 새로추가된 노드를 가르키게 합니다.(line 27)

이렇게 되면 두개의 각 노드가 서로를 가르키며 head는 처음 추가된 노드, tail은 마지막에 추가된 노드를 가르키고 있게 됩니다.
이후 list->count 갯수를 1증가, list->count는 1이된다.(line 30)

3. (세번째 노드 추가) 

역시나 새로운 노드가 추가되면 새로운 노드의 prev는 tail을, next는 head를 가르키게 한다. (새로 추가된 노드가 끝노드이므로)

다음 tail의 next, head의 prev는 새로운 노드를 가르키게한다.

끝으로 tail은 새로운 노드를 가르킨다.

세번째로 구현할 함수는 Node의 전부를 출력하는 PrintAllNode함수.

list가 비어있는지 확인 후, head를 기준이든 tail을 기준이든 연결된 노드포인터를 갖고 쭉 출력해주면 됩니다.

void PrintAllNode(List**list)
{
    if (!(*list)) return;
    cout << endl;
    if ((*list)->count == 0)
    {
        cout << " ### List is empty  ### " << endl;
        return;
    }
 
    cout << " ### Print All Node ### " << endl;
    int idx = 1;
    int cnt = (*list)->count;
    Node* n = (*list)->head;
    while (idx <= cnt)
    {
        cout <<"["<<idx<<"] "<< n->data << endl;
        n = n->next;
        idx++;
    }
    cout << endl;
}

다음으로 추가된 노드에서 데이터를 찾는 FindNode() 함수,
처음부터 순차적으로 탐색하면서 원하는 데이터가 있는 경우 찾은 노드를, 없으면 Null값을 반환해줍니다.

Node* FindNode(List ** list, int data)
{
    if (!(*list)) return NULL;
 
    int idx = 1;
    int cnt = (*list)->count;
    Node* n = (*list)->head;
 
    while (idx <= cnt)
    {
        if (n->data == data)
        {
            cout << "Find Node data : " <<data<< endl;
            return n;
        }
        n = n->next;
        idx++;
    }
    cout << "Can't find data" << endl;
    return NULL;
}

리스트에서 원하는 노드를 지우는 DelNode함수

void DelNode(List **list, Node * n)
{
    if (!(*list) || !n) return;
 
    cout << "Delete Node data : " << n->data << endl;
    if ((*list)->count==1)
    {
        (*list)->head = (*list)->tail = NULL;
        free(n);
    }
    else
    {
        if ((*list)->head == n)
        {
            (*list)->head = n->next;
        }
        else if ((*list)->tail == n)
        {
            (*list)->tail = n->prev;
        }
        n->prev->next = n->next;
        n->next->prev = n->prev;
        
        free(n);
    }
 
    (*list)->count--;
}

우선, list의 노드가 하나인 경우, 찾은 노드를 지우고 head와 tail을 NULL값을 넣어준다. (line 8~9)

하나보다 많은 경우, 삭제할 노드의 이전 노드와 다음 노드를 연결시켜주면 된다.

만약 head노드일 경우엔 head를 삭제할 노드의 다음노드, tail노드이면 삭제할 노드의 이전노드로 설정해주면 됩니다.

그리고 아래와 같이 테스트해보면 됩니다.

int main()
{ 
    List*list;
    InitList(&list);
    for (int i = 1; i < 5; i++)
        AddNode(&list, CreateNode(i));
    
    PrintAllNode(&list);
 
    DelNode(&list, FindNode(&list, 3));
    PrintAllNode(&list);
 
    DelNode(&list, FindNode(&list, 1));
    PrintAllNode(&list);
 
    DelNode(&list, FindNode(&list, 4));
    PrintAllNode(&list);
 
    DelNode(&list, FindNode(&list, 4));
    PrintAllNode(&list);
 
    DelNode(&list, FindNode(&list, 2));
    PrintAllNode(&list);
 
    AddNode(&list, CreateNode(100));
    AddNode(&list, CreateNode(102));
    AddNode(&list, CreateNode(104));
    PrintAllNode(&list);
 
    return 0;
}

사실 원형 연결리스트는 단일 연결 리스트보단 구현이 까다롭습니다.

처음 구현 해볼 경우엔 단일 연결리스트-> 이중연결리스트 -> 원형연결리스트 순으로 순차적으로 구현해볼 것을 추천드립니다.

연결리스트를 완벽히 이해하신 다음에는,
연결리스트를 이용하여 스택, 큐를 이해하고 구현해보는 것 역시 추천드립니다.

  - 스택 구현하기
  - 큐 구현하기