5.2.3 연결리스트 테스트

연결리스트를 사용하는 방법은 순차적으로 보관하거나 원하는 위치를 찾아 보관하는 방법이 대표적입니다. 동적 배열에서는 이 외에도 인덱스를 사용하는 방법이 있었지만 연결리스트를 사용할 때는 이 방법은 사용하지 않습니다.

따라서 테스트 코드는 크게 순차 보관하는 시뮬레이션과 원하는 순서로 보관하는 예로 구성할게요.

int main()
{
    Simul_Seq();
    Simul_Order();
    return 0;
}

먼저 순차적으로 보관하는 테스트 코드를 작성합시다.

void Simul_Seq()
{

먼저 연결리스트를 동적으로 생성합니다.

    LinkedList *linkedlist = New_LinkedList();

그리고 도서 개체를 생성하여 연결리스트에 순차 보관합니다. 순차 보관할 때는 LinkedList_PushBack 함수를 이용합니다.

    LinkedList_PushBack(linkedlist,New_Book("C언어","홍길동",10));
    LinkedList_PushBack(linkedlist,New_Book("C++언어","강감찬",20));
    LinkedList_PushBack(linkedlist,New_Book("자료구조","김구",5));
    LinkedList_PushBack(linkedlist,New_Book("알고리즘","이순신",9));
    LinkedList_PushBack(linkedlist,New_Book("디자인패턴","정약용",13));

원하는 순서로 보관하였는지 테스트하기 위해 보관한 전체 자료를 출력합니다. 이 부분은 별도의 함수로 작성합시다.

    View_LinkedList(linkedlist);

도서 제목으로 검색도 테스트 해 봅시다. 테스트를 위해 연결리스트에 보관한 도서와 보관하지 않은 도서의 제목으로 검색을 테스트합시다. 이 부분도 별도의 함수로 작성합시다.

    Simul_Find(linkedlist,"C언어");
    Simul_Find(linkedlist,"이데아이론");

그리고 도서 제목으로 보관한 자료를 삭제하는 것도 테스트합시다. 이 부분도 별도의 함수로 작성합시다.

    Simul_Remove(linkedlist,"자료구조");

원하는대로 삭제가 이루어졌는지 확하기 위해 보관한 전체 자료를 출력합니다.

    View_LinkedList(linkedlist);

시뮬레이션에 사용한 개체를 정리합니다. 이 부분도 별도의 함수로 작성합시다.

    SimulEnd(linkedlist);
}

연결리스트에 보관한 모든 도서 정보를 출력하는 함수를 작성합시다.

void View_LinkedList(LinkedList *linkedlist)
{
    Book *book = 0;

연결리스트의 시작 부분과 끝 부분을 얻어옵니다. 참고로 시작 부분은 보관한 자료 중에 맨 앞에 있는 노드의 위치 정보이고 끝 부분은 마지막 자료를 보관한 노드의 다음 노드 위치입니다.

    Link seek = LinkedList_Begin(linkedlist);
    Link end = LinkedList_End(linkedlist);

순차적으로 이동하여 마지막 끝 위치에 도달할 때까지 보관한 도서를 얻어옵니다.

    printf("-----보유 도서 목록-----\n");
    for(   ;seek!=end;seek = seek->next)
    {
        book = (Book *)(seek->data);

얻어온 도서 개체가 존재하면 도서 정보를 출력합니다.

        if(book)
        {
            Book_View(book);
        }
    }
}

도서 제목으로 검색하는 함수를 작성합시다.

void Simul_Find(LinkedList *linkedlist,const char *title)
{
    Book *book = 0;

마찬가지로 연결리스트의 시작과 끝부분을 얻어옵니다.

    Link seek = LinkedList_Begin(linkedlist);
    Link end = LinkedList_End(linkedlist);

순차적으로 이동하면서 끝부분까지 도서 정보를 얻어옵니다.

    for(   ;seek!=end;seek=seek->next)
    {
        book = (Book *)(seek->data);

얻어온 도서가 유효할 때 입력 인자로 받은 도서 제목과 일치하면 도서 개체 정보를 출력하고 함수를 종료합니다.

        if(book && (Book_CompareTitle(book,title)==0))
        {
            printf("검색 결과:");
            Book_View(book);
            return;
        }
    }

끝까지 탐색해도 원하는 도서를 찾지 못하면 이를 출력합니다.

    printf("<%s> 책을 찾을 수 없습니다.\n",title);
}

도서 제목으로 삭제하는 함수를 작성합시다. 검색 기능과 전체적인 흐름은 비슷하면 단지 찾고 난 후의 동작만 차이가 있습니다.

void Simul_Remove(LinkedList *linkedlist,const char *title)
{
    Book *book = 0;
    Link seek = LinkedList_Begin(linkedlist);
    Link end = LinkedList_End(linkedlist);
    for(   ;seek!=end;seek=seek->next)
    {
        book = (Book *)(seek->data);
        if(book && (Book_CompareTitle(book,title)==0))
        {

일치하면 연결리스트에서 해당 위치의 노드를 제거하고 도서 개체를 소멸한 후 함수를 종료합니다.

            LinkedList_Erase(linkedlist,seek);
            Delete_Book(book);
            printf("삭제 성공!\n");
            return;
        }
    }

존재하는 책이 없을 때 이 정보를 출력합니다.

    printf("<%s> 책을 찾을 수 없습니다.\n",title);
}

시뮬레이션을 마치고 자원을 해제하는 함수를 작성합시다.

void SimulEnd(LinkedList *linkedlist)
{
    Book *book = 0;

연결리스트의 시작과 끝 부분을 얻어옵니다.

    Link seek = LinkedList_Begin(linkedlist);
    Link end = LinkedList_End(linkedlist);

순차적으로 이동하면서 보관한 도서 개체를 얻어옵니다.

    for(   ;seek!=end;seek=seek->next)
    {
        book = (Book *)(seek->data);

도서 개체가 유효하면 시뮬레이션에 사용한 해당 도서 개체를 소멸합니다.

        if(book)
        {
            Delete_Book(book);
        }
    }

마지막으로 연결리스트를 소멸합니다.

    Delete_LinkedList(linkedlist);
}

이제 특정 키 순으로 자료를 보관하는 시뮬레이션 함수를 작성합시다.

void Simul_Order()
{

먼저 연결리스트를 동적으로 생성합니다.

    LinkedList *linkedlist = New_LinkedList();

그리고 지은이 순으로 도서 개체를 보관합니다. 이 부분은 별도의 함수로 작성합시다.

    Simul_OrderAdd(linkedlist,New_Book("C언어","홍길동",10));
    Simul_OrderAdd(linkedlist,New_Book("C++언어","강감찬",20));
    Simul_OrderAdd(linkedlist,New_Book("자료구조","김구",5));
    Simul_OrderAdd(linkedlist,New_Book("알고리즘","이순신",9));
    Simul_OrderAdd(linkedlist,New_Book("디자인패턴","정약용",13));

원하는 순서대로 보관하였는지 확인하기 위해 연결리스트에 보관한 전체 도서 정보를 출력합니다.

    View_LinkedList(linkedlist);

도서 검색에 관한 테스트와 삭제에 관한 테스트를 수행한 후에 시뮬레이션을 종료합니다.

    Simul_Find(linkedlist,"C언어");
    Simul_Find(linkedlist,"이데아이론");
    Simul_Remove(linkedlist,"자료구조");
    View_LinkedList(linkedlist);
    SimulEnd(linkedlist);
}

지은이 순으로 도서 개체를 보관하는 함수를 작성합시다.

void Simul_OrderAdd(LinkedList *linkedlist,Book *book)
{
    Book *stored_book = 0;

연결리스트의 시작과 끝 부분을 얻어옵니다.

    Link seek = LinkedList_Begin(linkedlist);
    Link end = LinkedList_End(linkedlist);

순차적으로 이동하면서 보관한 도서 개체를 얻어옵니다.

    for(   ;seek!=end;seek=seek->next)
    {
        stored_book = (Book *)(seek->next);

만약 보관한 도서의 지은이 이름이 입력 인자로 받은 도서의 이름보다 크거나 같으면 보관할 위치를 찾은 것입니다.

        if(stored_book && (Book_CompareAuthor(stored_book,book->author)>=0))
        {
            break;
        }
    }

찾은 위치 뒤에 도서를 보관합니다.

    LinkedList_Insert(linkedlist,seek,book);
}

다음은 테스트 코드를 작성한 Program.c 파일의 내용입니다.

//Program.c
#include "LinkedList.h"
#include "Book.h"
void View_LinkedList(LinkedList *linkedlist)
{
    Book *book = 0;
    Link seek = LinkedList_Begin(linkedlist);
    Link end = LinkedList_End(linkedlist);
    
    printf("-----보유 도서 목록-----\n");
    for(   ;seek!=end;seek = seek->next)
    {
        book = (Book *)(seek->data);
        if(book)
        {
            Book_View(book);
        }
    }	
}
void SimulEnd(LinkedList *linkedlist)
{
    Book *book = 0;
    Link seek = LinkedList_Begin(linkedlist);
    Link end = LinkedList_End(linkedlist);
    
    for(   ;seek!=end;seek=seek->next)
    {
        book = (Book *)(seek->data);
        if(book)
        {
            Delete_Book(book);
        }
    }
    Delete_LinkedList(linkedlist);
}
void Simul_Find(LinkedList *linkedlist,const char *title)
{
    Book *book = 0;
    Link seek = LinkedList_Begin(linkedlist);
    Link end = LinkedList_End(linkedlist);
    
    for(   ;seek!=end;seek=seek->next)
    {
        book = (Book *)(seek->data);
        if(book && (Book_CompareTitle(book,title)==0))
        {
            printf("검색 결과:");
            Book_View(book);
            return;
        }
    }
    printf("<%s> 책을 찾을 수 없습니다.\n",title);
}
void Simul_Remove(LinkedList *linkedlist,const char *title)
{
    Book *book = 0;
    Link seek = LinkedList_Begin(linkedlist);
    Link end = LinkedList_End(linkedlist);
    
    for(   ;seek!=end;seek=seek->next)
    {
        book = (Book *)(seek->data);
        if(book && (Book_CompareTitle(book,title)==0))
        {
            LinkedList_Erase(linkedlist,seek);
            Delete_Book(book);
            printf("삭제 성공!\n");
            return;
        }
    }
    printf("<%s> 책을 찾을 수 없습니다.\n",title);
}
void Simul_Seq()
{
    LinkedList *linkedlist = New_LinkedList();
    LinkedList_PushBack(linkedlist,New_Book("C언어","홍길동",10));
    LinkedList_PushBack(linkedlist,New_Book("C++언어","강감찬",20));
    LinkedList_PushBack(linkedlist,New_Book("자료구조","김구",5));
    LinkedList_PushBack(linkedlist,New_Book("알고리즘","이순신",9));
    LinkedList_PushBack(linkedlist,New_Book("디자인패턴","정약용",13));
    View_LinkedList(linkedlist);
    Simul_Find(linkedlist,"C언어");
    Simul_Find(linkedlist,"이데아이론");
    Simul_Remove(linkedlist,"자료구조");
    View_LinkedList(linkedlist);
    SimulEnd(linkedlist);	
}

void Simul_OrderAdd(LinkedList *linkedlist,Book *book)
{	
    Book *stored_book = 0;
    Link seek = LinkedList_Begin(linkedlist);
    Link end = LinkedList_End(linkedlist);
    
    for(   ;seek!=end;seek=seek->next)
    {
        stored_book = (Book *)(seek->next);
        if(stored_book && (Book_CompareAuthor(stored_book,book->author)>=0))
        {
            break;
        }
    }	
    LinkedList_Insert(linkedlist,seek,book);
}
void Simul_Order()
{
    LinkedList *linkedlist = New_LinkedList();
    
    Simul_OrderAdd(linkedlist,New_Book("C언어","홍길동",10));
    Simul_OrderAdd(linkedlist,New_Book("C++언어","강감찬",20));
    Simul_OrderAdd(linkedlist,New_Book("자료구조","김구",5));
    Simul_OrderAdd(linkedlist,New_Book("알고리즘","이순신",9));
    Simul_OrderAdd(linkedlist,New_Book("디자인패턴","정약용",13));
    View_LinkedList(linkedlist);
    Simul_Find(linkedlist,"C언어");
    Simul_Find(linkedlist,"이데아이론");
    Simul_Remove(linkedlist,"자료구조");
    View_LinkedList(linkedlist);
    SimulEnd(linkedlist);
}

int main()
{
    Simul_Seq();
    Simul_Order();	
    return 0;
}

동적 배열과 연결리스트를 설계 및 구현하고 이를 테스트해 보았습니다. 동적 배열은 자료를 보관하는 저장소가 하나의 메모리여서 시작 위치에서 상대적 거리에 있는 원소를 참조하는 기능을 제공한다는 점을 제외하면 대부분 사용 방법이 비슷하다는 것을 알 수 있습니다. 좀 더 세부적으로 비교한다면 동적 배열에 원하는 위치에 자료를 보관하면 최악의 경우 보관한 자료 전체를 이동하지만 연결리스트에서는 네 개의 링크만 조절하면 가능함을 알 수 있습니다. 마찬가지로 자료를 삭제할 때 배열에서는 최악의 경우 보관한 자료 전체를 이동하지만 연결리스트에서는 두 개의 링크만 조절하면 가능합니다.

이 외에도 보관한 자료를 통합하거나 분리하는 등의 기능을 제공한다면 연결리스트가 보다 효과적으로 제공할 수 있음을 알 수 있는데 이 부분은 이 책에서는 논하지 않겠습니다. 여러분 스스로 해결해 보세요.