[자료구조]C로 구현한 간단한 연결 리스트(Linked List)

소개글

C로 구현하였고 초보 티가 팍팍 나게 구현했습니다. 의외로 이런 소스가 필요한 경우가 있어서 여러모로 구하시는 분이 많아서 그렇게 했습니다.

리스트와 C 언어를 처음 배우는 사람이 연결 리스트 과제물을 작성할 때 매우 적합한 소스 코드입니다. 정의되지 않은 연산(없는 것을 지우라고 한다던지...) 하는 경우에도 에러가 난다던지 하지도 않으며 버그라고 할 수 있는 버그도 없습니다. 각각의 함수의 동작에 대한 설명(레포트)도 세가지 포맷 윈도 워드패드(rtf), 메모장(txt) 등으로 저장되어 있습니다. --- 레포트라고 하기에는 빈약하지만, 공대 특성상 이 정도의 레포트만 요구하는 경우도 많으므로... 풍부한 레포트를 기대하시는 분은 받지 마시기 바랍니다! ---

제네릭한 스타일과 효율성의 관점에서 보면 이 소스의 문제점은 여러 가지가 있습니다. 첫째로 각기 다른 타입을 담아내는 여러가지 형태의 리스트를 여러벌 만들기 어렵습니다. 이것은 템플릿을 이용하면 쉽게 적용 가능하고, 템플릿을 지원하는 컴파일러도 있으므로, 간단히 구현할 수 있으나 그냥 두었습니다. 둘째로, 성능이 떨어집니다. 중간에 끼워넣기와 삭제하기가 매우 빠른 리스트이지만, 이터레이터를 구현하지 않았기 때문에 처음부터 순차검색을 하게 되어 있습니다. 리스트의 길이를 구하는 함수도 처음부터 하나씩 갯수를 세는 매우 느리고 비효율적인 방식으로 되어 있습니다. 이것은 추가 삭제 때마다 리스트의 길이를 업데이트하고 길이를 구하라고 할 때 바로 그 값을 리턴하면 빨라집니다. 셋째로, 재사용성이 떨어집니다. 그래서 단순 과제 참고용으로 쓸 수 있고 실용적으로는 거의 쓸모가 없습니다. 그 밖에, define으로 대충 처리해 버린 부분도 있습니다.

그럼에도 불구하고, 이 소스의 필요성을 보자면, 첫째로, 처음 C 언어를 배우는 사람이 공부하는데 쓸 수 있습니다. 처음 하는 사람에게 복잡할 수 있는 복잡한 템플릿을 사용하지 않았고, malloc와 free를 쓰는 방법, 재귀적 호출을 이용하는 방법, 일반적인 변수의 비교방법과 문자열 포인터의 비교방법의 차이 등을 익힐 수 있는 소스입니다.

실행화면은 특별할 게 없으니 대신에 단일 연결 리스트 구조를 그림으로 그린 것을 첨부했습니다.

컴파일 실행환경

대부분의 C 언어 혹은 C++ 컴파일러로 컴파일 할 수 있습니다. Visual C++, Dev-cpp, Borland C, gcc 등에서 컴파일 할 수 있습니다. linked_list.c 파일에는 main 함수가 없고 main.c 파일에 테스트용 main 함수가 있으므로 둘을 함께 프로젝트에 넣고 컴파일하시거나 linked_list.c 파일에 main 함수를 추가하시거나 하셔서 컴파일하시면 됩니다.

본문내용

구조체들입니다.
struct linked_list
{
struct list_node *head;
};
위의 구조체는 리스트 전체를 관리하는 구조체인데 단지 dummy head node의 포인터만 가지고 있습니다. Dummy head node라는 것은 구현의 편의를 위하여, 첫번째 노드에는 아무런 데이터를 기록하지 않고 그냥 빈 노드를 두는 것을 의미합니다. 이것은 Single Linked List이므로 dummy head만 필요하지만 Double Linked List의 경우에는 구현의 편의를 위하여 dummy tail도 함께 사용하고 있습니다. 물론 바로 첫번째 노드를 head로 포인팅할 수도 있겠지만 여러모로 dummy head node를 쓰는 것이 편리하여 그렇게 하였습니다.

struct list_node
{
data_type data;
struct list_node *next;
};
이것은 리스트의 각각의 노드들의 구조체입니다. 노드는 데이터를 가지고 있고, 다음 노드를 가리키는 포인터로 이루어져 있습니다.

List와 관련하여 외부에서 제공되는 함수들의 목록입니다. 사용 방법은 대체로 리스트 포인터를 첫번쨰 인자로 넘겨주고 필요한 경우에 두번째 인자를 받는 형태입니다.

struct linked_list *linked_list_create();
리스트를 새로 만들어서 리턴합니다.

int linked_list_size(struct linked_list *list);
리스트 크기를 리턴합니다.

void linked_list_add_first(struct linked_list *list, data_type param_data);
리스트 앞에 데이터를 덧붙입니다.

void linked_list_add_last(struct linked_list *list, data_type param_data);
리스트의 뒤에 데이터를 덧붙입니다.

int linked_list_remove_first(struct linked_list *list);
첫번째 데이터를 제거하고 리턴합니다.

int linked_list_remove_last(struct linked_list *list);
마지막 데이터를 제거하고 리턴합니다.

data_type linked_list_remove(struct linked_list *list, data_type param_data);
특정 데이터를 찾아서 지웁니다.

data_type linked_list_get(struct linked_list *list, int index);
index 번째의 데이터를 리턴합니다.

data_type linked_list_get_first(struct linked_list *list);
첫번째 데이터를 리턴합니다.

data_type linked_list_get_last(struct linked_list *list);
마지막 데이터를 리턴합니다.

int linked_list_item_exist(struct linked_list *list, data_type param_data);
데이터가 리스트내에 존재하는지 여부를 리턴합니다.

int linked_list_is_empty(struct linked_list *list);
리스트가 비어 있는지를 리턴합니다.

void linked_list_clear(struct linked_list *list);
리스트의 내용을 깨끗이 비웁니다.

void linked_list_destroy(struct linked_list *list);
리스트를 다 사용하고 난 뒤에는 제거합니다.

각각의 함수의 자세한 동작은 뒤에 설명되어 있습니다.
...

압축파일 내 파일목록

source/equal.h
source/linked_list.c
source/linked_list.h
source/main.c
report/linked_list_test_ansi_report.txt
report/linked_list_test_rtf_report.rtf
report/linked_list_test_utf8_report.txt
report/list_pic.PNG

참고 자료

없음