5.2.2 연결리스트 구현

연결리스트를 동적으로 생성하는 함수를 작성합시다.

LinkedList *New_LinkedList()
{
    LinkedList *linkedlist = 0;

먼저 LinkedList 형식 크기의 메모리를 할당합니다.

    linkedlist = (LinkedList *)malloc(sizeof(LinkedList));

그리고 head와 tail에 더미 노드를 생성합니다. 노드를 생성하는 함수는 별도로 작성합시다.

    linkedlist->head = New_Node(0);
    linkedlist->tail = New_Node(0);

head의 next링크를 tail을 가리키게 하고 tail의 prev 링크를 head를 가르키게 합니다.

    linkedlist->head->next = linkedlist->tail;
    linkedlist->tail->prev = linkedlist->head;

보관하고 있는 자료의 개수를 0으로 초기화한 후 생성한 연결리스트를 반환합니다.

    linkedlist->usage = 0;
    return linkedlist;
}

노드를 생성하는 함수를 작성합시다. 반환할 노드의 위치 정보를 Link로 타입 재지정하였기 때문에 반환 형식을 Link로 정의할게요.

Link New_Node(Element data)
{

먼저 Node 형식 크기의 메모리를 할당합니다.

    Link link = (Link)malloc(sizeof(Node));

입력 인자로 전달받은 data를 설정하고 next와 prev 링크를 0으로 초기 설정한 후 반환합니다.

    link->data = data;
    link->next = link->prev = 0;
    return link;
}

연결리스트를 해제화하는 함수를 작성합시다.

void Delete_LinkedList(LinkedList *linkedlist)
{

연결리스트를 해제화하는 함수에서는 head에서 링크를 따라가면서 tail이 가리키는 노드를 해제한 후에 자신을 해제해야 합니다.

    Link seek = linkedlist->head;
    while( seek != linkedlist->tail)
    {

그런데 자신을 해제한 이후에 다음 노드로 이동할 수가 없으므로 먼저 이동한 후에 이전 노드를 제거합니다.

        seek = seek->next;
        free(seek->prev);
    }

위의 반복문에서는 마지막 노드는 제거하지 않은 상태입니다. 따라서 tail이 가르키는 노드를 제거한 후에 자신의 메모리를 해제합니다.

    free(linkedlist->tail);
    free(linkedlist);
}

순차적으로 자료를 보관하는 함수를 작성합니다.

 void LinkedList_PushBack(LinkedList *linkedlist,Element data)
{

tail 앞에 자료를 보관하면 순차적으로 보관할 수 있습니다.

    LinkedList_Insert(linkedlist,linkedlist->tail,data);
}

특정 노드 앞에 자료를 보관하는 함수를 작성합시다. 노드의 위치 정보를 Link로 타입 재지정한 것을 잊지 마세요.

void LinkedList_Insert(LinkedList *linkedlist,Link pos,Element data)
{

먼저 자료를 보관하는 노드를 생성합니다.

    Link link = New_Node(data);

그리고 입력 인자로 받은 노드 앞에 새로 생성한 노드를 연결합니다. 이 부분은 별도의 함수로 작성합시다.

    HangNode(link,pos);

보관한 자료의 개수를 1 증가합니다.

    linkedlist->usage++;
}

특정 노드 앞에 노드를 연결하는 함수를 작성합시다.

void HangNode(Link now,Link pos)
{

먼저 새로운 now의 prev를 pos의 prev로 설정합니다. 그리고 now의 next를 pos로 설정합니다.

    now->prev = pos->prev;
    now->next = pos;

그리고 pos의 prev 노드의 next를 now로 설정합니다.

    pos->prev->next = now;

마지막으로 pos의 prev를 now로 설정합니다.

    pos->prev = now;
}

연결하는 함수에서 링크를 설정하는 방법은 여러가지가 있습니다. 위 예는 그 중 한 가지 예입니다.

동적 배열처럼 자료를 보관한 노드 중에 맨 앞의 노드의 위치 정보를 반환하는 메서드와 맨 마지막 자료를 보관한 노드의 다음 노드를 반환하는 함수를 제공합시다.

Link LinkedList_Begin(LinkedList *linkedlist)
{

연결리스트의 head가 가리키는 노드는 더미 노드이며 head의 next가 가리키는 노드가 자료를 보관한 맨 앞의 노드입니다.

    return linkedlist->head->next;
}

Link LinkedList_End(LinkedList *linkedlist)
{

언제나 맨 마지막 보관한 자료를 보관한 노드의 다음 노드가 tail입니다.

    return linkedlist->tail;
}

이제 연결리스트에서 특정 위치의 노드를 제거하는 함수를 작성합시다.

void LinkedList_Erase(LinkedList *linkedlist,Link pos)
{

먼저 연결을 끊습니다. 이 부분은 별도의 함수로 작성합시다.

    DisconnectNode(pos);

그리고 노드를 위해 할당한 메모리를 해제하고 보관한 자료 개수를 1 감소합니다.

    free(pos);
    linkedlist->usage--;
}

연결리스트에서 연결을 끊는 함수를 작성합시다.

void DisconnectNode(Link pos)
{

연결을 끊을 노드의 이전(prev) 노드의 next를 연결을 끊을 노드의 이후(next) 노드로 설정합니다.

    pos->prev->next = pos->next;

연결을 끊을 노드의 이후(next) 노드의 prev를 연견을 끊을 노드의 이전(prev) 노드로 설정합니다.

    pos->next->prev = pos->prev;
}

연결을 끊는 과정은 [그림 5.4]를 참고하세요. 여러분께서 알고리즘이나 자료구조를 학습할 때는 종이에 논리를 전개하거나 메모리 그림 혹은 논리적 모습을 도식하는 습관을 갖길 권합니다. 머리 속에서 그리는 것보다 종이에 쓰거나 그린 후에 생각하면 보다 효과적으로 이해하고 원하는 결과를 얻을 수 있습니다.

다음은 LinkedList.c 소스 파일의 내용입니다.

//LinkedList.c
#include "LinkedList.h"
#include <malloc.h>
#include <memory.h>
Link New_Node(Element data)
{
    Link link = (Link)malloc(sizeof(Node));
    link->data = data;
    link->next = link->prev = 0;
    return link;
}
void HangNode(Link now,Link pos)
{
    now->prev = pos->prev;
    now->next = pos;
    pos->prev->next = now;
    pos->prev = now;
}
void DisconnectNode(Link pos)
{
    pos->prev->next = pos->next;
    pos->next->prev = pos->prev;
}
LinkedList *New_LinkedList()
{
    LinkedList *linkedlist = 0;
    linkedlist = (LinkedList *)malloc(sizeof(LinkedList));
    linkedlist->head = New_Node(0);
    linkedlist->tail = New_Node(0);
    linkedlist->head->next = linkedlist->tail;
    linkedlist->tail->prev = linkedlist->head;
    linkedlist->usage = 0;
    return linkedlist;
}
void Delete_LinkedList(LinkedList *linkedlist)
{
    Link seek = linkedlist->head;
    while( seek != linkedlist->tail)
    {
        seek = seek->next;
        free(seek->prev);
    }
    free(linkedlist->tail);
    free(linkedlist);
}
void LinkedList_PushBack(LinkedList *linkedlist,Element data)
{
    LinkedList_Insert(linkedlist,linkedlist->tail,data);
}
void LinkedList_Insert(LinkedList *linkedlist,Link pos,Element data)
{
    Link link = New_Node(data);
    HangNode(link,pos);
    linkedlist->usage++;
}
Link LinkedList_Begin(LinkedList *linkedlist)
{
    return linkedlist->head->next;
}
Link LinkedList_End(LinkedList *linkedlist)
{
    return linkedlist->tail;
}
void LinkedList_Erase(LinkedList *linkedlist,Link pos)
{
    DisconnectNode(pos);
    free(pos);
    linkedlist->usage--;
}