[디딤돌 자료구조와 알고리즘] 5.2 연결리스트 - 5.2.3 연결리스트 테스트

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

#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;

}

 

 

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

 

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

---

프로젝트 소스 및 헤더 파일

연결리스트.zip

 

관련 게시글

[디딤돌 자료구조와 알고리즘] 5.2 연결리스트 - 5.2.1 연결리스트 설계

[디딤돌 자료구조와 알고리즘] 5.2 연결리스트 - 5.2.2 연결리스트 구현