이번 절에서는 연결 리스트를 이용하여 리스트 ADT를 구현하여보자.
여기서는 연결 리스트 중에서 단순 연결 리스트를 사용한다.
선형 리스트의 여러 가지 연산 중에서 add 연산과 delete 연산을 중점적으로 설명하고자 한다.
먼저 연결 리스트의 삽입 함수인 insert_node와 삭제 함수인 remove_node는 함수의 매개 변수로 노드를 가리키는 포인터를 받는다.
사실 연결 리스트에서는 포인터로 여러 가지 처리를 하는 것이 효율적이다.
그러나 리스트 ADT의 정의에서는 함수의 매개 변수가 포인터가 아니고 리스트에서의 항목의 위치가 된다.
따라서 연결 리스트로 리스트를 구현하였을 경우, 리스트 ADT의 연산들은 연결 리스트에서 제공하는 연산들을 이용하여 구현된다.
여기서는 위치를 매개 변수로 받아서 삽입이나 삭제를 하는 함수를 작성해보자.
리스트 ADT의 구현
리스트를 위한 구조체는 다음과 같이 정의된다.
head는 첫 번째 노드를 가리키는 헤드 포인터이고, length는 연결 리스트 내에 존재하는 노드의 개수를 나타낸다.
typedef struct LinkedListType{
ListNode * head;
int length;
}LinkedListType;연결 리스트를 이용한 리스트가 필요하면 언제든지 다음과 같은 문장을 이용하여 리스트를 만들 수 있다.
LinkedListType list1;
is_empty 연산의 구현
int is_empty(LinkedListType* list) {
if (list->head == NULL)return 1;
else return 0;
}get_length 연산의 구현
int get_length(LinkedListType* list) {
return list->length;
}add연산의 구현
선형 리스트 ADT의 연산들 중에서 add연산은 새로운 자료를 선형 리스트에 추가하는 함수이다.
먼저 동적 메모리 할당을 이용하여 노드를 생성한 다음, 노드의 데이터 필드에다 자료를 복사하고, 기존의 노드들 중에서 지정된 노드를 찾아서 지정된 노드의 뒤에 연결을 해주면 된다.
여기서는 get_node_at 함수를 정의하여 사용하였다.
get_node_at 함수는 매개 변수 pos로 위치를 받아서 그 위치에 해당하는 노드의 주소를 반환하는 함수이다.
만약 pos가 음수이면 NULL을 반환한다.
get_node_at 함수가 지정된 위치의 노드의 주소를 반환하면 이 값을 이용하여 insert_node함수를 호출하여 삽입을 수행한다.
add_last 함수와 add_first 함수는 add함수를 이용하여 쉽게 구현된다.
ListNode* get_node_at(LinkedListType* list, int pos) {
//리스트 안에서 pos 위치의 노드를 반환한다
int i;
ListNode* tmp_node = list->head;
if (pos < 0)return NULL;
for (i = 0; i < pos; i++) {
tmp_node = tmp_node->link;
}
return tmp_node;
}
void add(LinkedListType* list, int position, element data) {
//주어진 위치에 데이터를 삽입한다
ListNode* p;
if ((position >= 0) && (position <= list->length)) {
ListNode* node = (ListNode*)malloc(sizeof(ListNode));
if (node == NULL)error("메모리 할당 에러");
node->data = data;
p = get_node_at(list, position - 1);
insert_node(&(list->head), p, node);
list->length++;
}
}
void add_last(LinkedListType* list, element data) {
add(list, get_length(list), data);
}
void add_first(LinkedListType* list, element data) {
add(list, 0, data);
}delete 연산의 구현
삭제 연산은 공백이 아닌 리스트에서 pos 위치의 자료를 삭제한다.
마찬가지로 get_node_at 함수를 사용하여 (pos-1)위치에 해당하는 노드의 주소를 얻은 다음, remove_node 함수를 호출하면 된다.
(pos-1) 위치의 노드 주소를 반환받는 이유는 노드 삭제 시에 그 노드의 선행 노드 주소가 필요하기 때문이다.
void delete(LinkedListType* list, int pos) {
if (!is_empty(list) && (pos >= 0) && (pos < list->length)) {
ListNode* p = get_node_at(list, pos - 1);
ListNode* removed = get_node_at(list, pos);
remove_node(&(list->head), p, removed);
list->length--;
}
}get_entry 연산의 구현
get_entry 연산은 위치 pos에 해당하는 데이터를 반환하는 연산이다.
먼저 pos가 length보다 작은지를 확인하고, 작으면 get_node_at 함수를 이용하여 위치에 해당하는 노드의 주소를 얻은 후에 이 노드가 가지고 있는 데이터 값을 반환하면 된다.
element get_entry(LinkedListType* list, int pos) {
ListNode* p;
if (pos >= list->length)error("위치 오류");
p = get_node_at(list, pos);
return p->data;
}clear 연산의 구현
clear 연산은 모든 노드를 지우는 함수이다. 리스트의 길이만큼 delete 함수를 호출하면 된다.
void clear(LinkedListType* list) {
for (int i = 0; i < list->length; i++) {
delete(list, i);
}
}display 연산의 구현
display 연산은 리스트가 가지고 있는 데이터를 화면에 출력하는 함수로서 list의 헤드 포인터가 가리키는 노드에서부터 NULL을 만날 때까지 노드의 데이터 값을 출력하면 된다.
노드의 데이터 값의 타입에 따라서 출력하는 부분은 변경되어야 한다.
void display(LinkedListType* list) {
ListNode* node = list->head;
printf("( ");
for (int i = 0; i < list->length; i++) {
printf("%d ", node->data);
node = node->link;
}
printf(" )\n");
}is_in_list 연산의 구현
연결 리스트에서 데이터 필드가 item인 노드를 탐색하는 연산이다.
연결 리스트상의 모든 노드를 검색하여 데이터 필드가 item인 노드를 찾는다.
헤드 포인터에서부터 시작하여 NULL을 만날 때까지 while 루프를 수행한다.
이때 헤드 포인터를 직접 사용하면 안되고 반드시 복사하여 사용하여야 한다.
헤드 포인터를 변경하면 연결리스트가 상실된다.
int is_in_list(LinkedListType* list, element item) {
ListNode* p;
p = list->head;
while ((p != NULL)) {
if (p->data == item)
break;
p = p->link;
}
if (p == NULL)return FALSE;
else return TRUE;
}전체 프로그램
#include <stdio.h>
#include <malloc.h>
#include <stdlib.h>
#include <limits.h>
#define FALSE 0
#define TRUE 1
typedef int element;
typedef struct ListNode {
element data;
struct ListNode* link;
}ListNode;
typedef struct LinkedListType{
ListNode * head;
int length;
}LinkedListType;
void error(char* message) {
fprintf(stderr, "%s\n", message);
exit(1);
}
void init(LinkedListType* list) {
if (list == NULL)return;
list->length = 0;
list->head = NULL;
}
void insert_node(ListNode** phead, ListNode* p, ListNode* new_node) {
if (*phead == NULL) { //공백 리스트인 경우
new_node->link = NULL;
*phead = new_node;
}
else if (p == NULL) { //p가 NULL이면 첫 번째 노드로 삽입
new_node->link = *phead;
*phead = new_node;
}
else { //p 다음에 삽입
new_node->link = p->link;
p->link = new_node;
}
}
void remove_node(ListNode** phead, ListNode* p, ListNode* removed) {
if (p == NULL) {
*phead = (*phead)->link;
}
else {
p->link = removed->link;
}
free(removed);
}
int is_empty(LinkedListType* list) {
if (list->head == NULL)return 1;
else return 0;
}
int get_length(LinkedListType* list) {
return list->length;
}
ListNode* get_node_at(LinkedListType* list, int pos) {
//리스트 안에서 pos 위치의 노드를 반환한다
int i;
ListNode* tmp_node = list->head;
if (pos < 0)return NULL;
for (i = 0; i < pos; i++) {
tmp_node = tmp_node->link;
}
return tmp_node;
}
void add(LinkedListType* list, int position, element data) {
//주어진 위치에 데이터를 삽입한다
ListNode* p;
if ((position >= 0) && (position <= list->length)) {
ListNode* node = (ListNode*)malloc(sizeof(ListNode));
if (node == NULL)error("메모리 할당 에러");
node->data = data;
p = get_node_at(list, position - 1);
insert_node(&(list->head), p, node);
list->length++;
}
}
void add_last(LinkedListType* list, element data) {
add(list, get_length(list), data);
}
void add_first(LinkedListType* list, element data) {
add(list, 0, data);
}
void delete(LinkedListType* list, int pos) {
if (!is_empty(list) && (pos >= 0) && (pos < list->length)) {
ListNode* p = get_node_at(list, pos - 1);
ListNode* removed = get_node_at(list, pos);
remove_node(&(list->head), p, removed);
list->length--;
}
}
element get_entry(LinkedListType* list, int pos) {
ListNode* p;
if (pos >= list->length)error("위치 오류");
p = get_node_at(list, pos);
return p->data;
}
void clear(LinkedListType* list) {
for (int i = 0; i < list->length; i++) {
delete(list, i);
}
}
void display(LinkedListType* list) {
ListNode* node = list->head;
printf("( ");
for (int i = 0; i < list->length; i++) {
printf("%d ", node->data);
node = node->link;
}
printf(" )\n");
}
int is_in_list(LinkedListType* list, element item) {
ListNode* p;
p = list->head;
while ((p != NULL)) {
if (p->data == item)
break;
p = p->link;
}
if (p == NULL)return FALSE;
else return TRUE;
}
int main() {
LinkedListType list1;
init(&list1);
add(&list1, 0, 20);
add_last(&list1, 30);
add_first(&list1, 10);
add_last(&list1, 40);
//list1 = (10,20,30,40)
display(&list1);
//list1 = (10,20,30)
delete(&list1, 3);
display(&list1);
//list1=(20,30)
delete(&list1, 0);
display(&list1);
printf("%s\n", is_in_list(&list1, 20) == TRUE ? "성공" : "실패");
printf("%d\n", get_entry(&list1, 0));
return 0;
}
