연결 리스트 맛보기

연결 리스트 맛보기

 연결 리스트란 무엇일까요? 쉽게 프로그래밍을 하면서 가장 많이 접하는 배열을 예로 들겠습니다. 아니, 예로 들 것 까지도 없습니다. 연결 리스트는 배열 그 자체입니다.

 연결 리스트는 배열처럼 데이터가 연속적으로 이루어진 리스트 입니다. 다만, 배열은 데이터 각각의 메모리 주소가 연결되어있고(예, 첫번째가 0x00000004라면 두번째는 반드시 0x00000008, 자료형의 크기는 4b로 한다.), 연결 리스트는 각 순서의 데이터가 어디에 저장되어 있는지 알 수 없다는 것입니다. 환경에 따라서 실제로 배열 처럼 바로 다음 번지에 있을수도 있고 아예 관련이 없는 다른 곳에 있을수도 있습니다.

 그렇다면 조금 더 배열과 연결 리스트의 다른 점을 알아봅시다. 우선 접근 방법인데요, 배열은 공간이 모두 연속적입니다. 따라서 접근할 때 자료형의 크기만큼 메모리 주소값을 이동하여 접근하는 방식을 쓸 수 있습니다. 단순히 주솟값을 이동하면서 참조하기 때문에 그 속도는 상상할 수도 없습니다. 다만, 데이터의 주솟값이 연속적이기 때문에 도중에 값을 삽입하거나 제거할 수 없습니다.(편법으로 가능하긴 합니다만, 여기서 편법은 우선 제외하겠습니다.)

 반대로, 연결 리스트는 데이터당 주솟값이 독립적입니다. 따라서 특별히 주솟값에 대한 일정한 연산으로는 다음 데이터를 구할 수 없습니다. 그렇기 때문에 연결 리스트는 다음 데이터를 가리키는 포인터를 가집니다. 이 포인터를 통해서 다음 데이터를 알 수 있고, 당연히 그 다음 데이터도 또 그 다음 데이터의 포인터를 가지므로 이것들이 서로 연결됩니다. 마지막 데이터는 다음 데이터를 가리키는 포인터가 NULL입니다. 이러한 특성을 가지기 때문에 배열과 비교하면 값을 찾아 들어가는 속도는 느린 편입니다. 하지만 크게 신경 쓸 정도는 아니죠.

 또한, 배열과는 다르게 메모리 주솟값을 독립적으로 가지기 때문에 언제든지 값을 추가할 수 있습니다. 값을 추가할 때는 추가할 공간의 연결 관계를 잠시 끊어놓고(아예 사라지면 안되므로 일단 임시 변수에라도 저장해 놓습니다.) 그 사이에 데이터를 놓고 다시 연결합니다. 그럼 간단하게 연결할 수 있죠.

 

 이제 이론은 정리 된 것 같습니다. 그렇다면 연결 리스트를 만드는 것 부터 시작해 봅시다.

 

 우선, 연결 리스트는 구조체의 형태를 지니고 있어야 합니다. 저장될 데이터와 다음 데이터까지의 경로(포인터)가 있어야 하기 때문이죠. 그러므로 구조체를 꾸며줍시다.

 

typedef struct node

{

        int Data;

        struct node *Next;

} Node;

 

 데이터를 저장하는 int형 변수(여기선 데이터가 int라고 가정합시다.)와 다음 데이터와의 길을 놓는 node*형 변수가 있습니다. 이렇게 두 가지 변수로만 이루어진 이 구조체를 통해서 연결 리스트를 꾸미게 됩니다.

 

 우선 연결 리스트를 초기화 해주는 함수를 꾸며봅시다. 사실, 연결 리스트의 초기화는 별거 없습니다. Data에 값을 넣고 Next가 NULL인 Node를 만들어서 포인터에 연결해 주면 됩니다. 그리고, 함수를 나가도 유지되게 하기 위해 malloc을 통한 동적 할당이 이루어져야 하겠군요. 동적 할당으로 만들어진 공간은 반드시 free 해주어야 합니다. 따라서 파괴 함수도 있어야 되겠군요.

 이 둘을 꾸며보면 다음과 같습니다.

 

Node *CreateLinkedList(int Data)

{

    Node *Start;

    Start = (Node*)malloc(sizeof(Node));

    Start->Data = Data;

    Start->Next = NULL;

    return Start;

}

void DestroyLinkedList(Node *List)

{

    free(List);

    return;

}

 Destroy함수는 나중에 손을 좀 봐야할것 같습니다.

 

 이제 리스트에 값을 추가해야할 차례입니다. 초기화 때 넣은 값만으로 리스트를 꾸밀 수는 없으니 말이죠. 값을 추가하는 함수를 만들어 봅시다.

 값을 추가하는 함수가 있으면 당연히 값을 제거하는 함수도 있어야 합니다. 그 두개를 이번엔 같이 꾸며봅시다.

 

void InsertLinkedList(Node **List, int Data, unsigned int Index)

{

    Node *Start = *List;

    Node *Now;

    Node *Insert;

    int NowIndex = 0;

    if(Index == 0)

    {

        Insert = (Node*)malloc(sizeof(Node));

        Insert->Data = Data;

        Insert->Next = Start;

        *List = Insert;

    }

    else

    {

        for(Now = Start; Now->Next != NULL; Now = Now->Next)

        {

            if(NowIndex >= Index-1)

            {

                 break;

            }

                else

            {

                NowIndex++;

            }

        }

        Insert = (Node*)malloc(sizeof(Node));

        Insert->Data = Data;

        Insert->Next = Now->Next;

        Now->Next = Insert;

    }

    return;

}

void RemoveLinkedList(Node **List, unsigned int Index)

{

    Node *Start = *List;

    Node *Now;

    Node *Remove;

    int NowIndex = 0;

    if(Index == 0)

    {

        *List = Start->Next;

        free(Start);

    }

    else

    {

        for(Now = Start; Now->Next != NULL; Now = Now->Next)

        {

            if(NowIndex >= Index-1)

            {

                break;

            }

            else

            {

                NowIndex++;

            }

        }

        Remove = Now->Next;

        Now->Next = Now->Next->Next;

        free(Remove);

     }

    return;

}

 

 이정도로 꾸며보았습니다.

 

 아까 Destroy함수에 좀 수정을 가해야 한다고 했습니다. Destroy함수를 보면 free함수를 통하여 리스트의 시작 부분만 제거하고 있습니다. 그렇게 될 경우 뒤의 리스트들은 전부 지워지지 않습니다. 이 문제를 해결하려면 링크를 따라가면서 할당된 자원들을 전부 해제해 주면 됩니다.

 링크를 따라가는 과정은 그리 어렵지 않습니다. 한번 봅시다.

 

void DestroyLinkedList(Node *List)

{

    Node *Now;

    Node *Next;

    for(Now = List; Now->Next != NULL; Now = Next)

    {

        Next = Now->Next;

        free(Now);

    }

    free(Now);

    return;

}

 

 이렇게 데이터를 순서대로 삭제하기 이전에 다음 데이터의 링크를 저장해놓고 삭제하는 것을 반복하면 됩니다. 이렇게 제거한 다음, 마지막 데이터를 또 제거해 주어야 합니다. for문을 잘 보면 그렇게 구조가 되어 있기 때문이죠.

 

 이렇게 구성된 4개의 함수만으로 왠만한 연결 리스트를 꾸며낼 수 있습니다. 그리고 이 4개의 함수를 조금 응용하면 다양한 연결 리스트들을 꾸며낼 수 있겠지요. 중요한 것은 함수 그 자체가 아니라 연결 리스트의 원리입니다. 이번 글을 시작으로 연결 리스트 때문에 고생하는 사람이 좀 줄었으면 좋겠습니다.