재미삼아 만들어본 Double Linked List (이중 연결 리스트)

역시 이론으로 알고있는 것과 실제로 경험해보는 것은 큰 차이가 있다는 것을 실감.

구현하는 것은 어렵지 않았으나, 사소한 것 하나하나에 대한 궁금증이 태어남.
대표적인 것이 "Double pointer(다중 포인터)를 왜 사용하는가?"의 질문.
이에 대한 답은 지역변수의 특징과 관련이 있다는 것을 파악.
지역변수는 함수가 리턴하는 순간 함수와 함께 사라진다는 특징이 있음.
함수에 전달하는 매개변수가 포인터라 하더라도 결국은 지역변수와 비슷한 성격을 보임.
포인터 매개변수는 주소를 전달받아 그것을 가리키는 포인터로 이용한다는 특징이 있을뿐
이외에 것은 일반 변수와 같음.

잡설을 그만두고 코드를 까보자. 코드는 리스트와 테스트로 구분되있다.

<이중 연결 리스트>
-- list.h --

#define true 1
#define false -1


typedef struct _node {
int data;
struct _node* prev;
struct _node* next;
} node;


typedef struct d_linked_list {
node* head;
node* tail;
int count;
int sorted;
} d_linked_list;


void del_list(d_linked_list* _list);


void ins_data(int _data, d_linked_list** _list);


node* search_data(int _data, d_linked_list* _list);


int del_data(int _data, d_linked_list* _list);


void show_all(d_linked_list* _list);

-- list.c --

#include
#include
#include "list.h"


void init_list(int _data, d_linked_list** _list) {
(*_list) = (d_linked_list*)malloc(sizeof(d_linked_list));
(*_list)->head = (node*)malloc(sizeof(node));
(*_list)->head->data = _data;
(*_list)->head->prev = NULL;
(*_list)->head->next = NULL;


(*_list)->tail = (*_list)->head;
(*_list)->count = 1;
(*_list)->sorted = true;
}


void del_node(d_linked_list* _list, node* _node) {
node* prev_node;
node* next_node;


prev_node = _node->prev;
next_node = _node->next;


if(_list->head == _node) {
_list->head = _node->next;
} 
if(_list->tail = _node) {
_list->tail = _node->prev;
}

if(prev_node != NULL) {
prev_node->next = next_node;
} 


if(next_node != NULL) {
next_node->prev = prev_node;
}


free(_node);


_list->count--;
}


void del_list(d_linked_list* _list) {
if(_list->head == NULL) {
if(_list->count != 0) {
printf("# ERROR: incorrect data in list \
information\n");
exit(1);
}
if(_list->tail != NULL) {
printf("# ERROR: incorrect data in list\
information\n");
exit(1);
}
return;
}


while(_list->head != NULL) {
_list->tail = _list->tail->prev;
del_node(_list, _list->tail->next);
}
}


void ins_data(int _data, d_linked_list** _list) {
if(*_list == NULL) {
init_list(_data, _list); 
return;
}


node* new;
new = (node*)malloc(sizeof(node));
new->data = _data;
new->next = NULL;
new->prev = (*_list)->tail;


if((*_list)->count == 0)
(*_list)->head = (*_list)->tail;


(*_list)->tail->next = new;
(*_list)->tail = new;
(*_list)->count++;
(*_list)->sorted = false;
}


node* search_data(int _data, d_linked_list* _list) {
if(_list->sorted == true) {

} else {
node* trace;
trace = _list->head;
while(trace != NULL) {
if(trace->data == _data)
return trace;


trace = trace->next;
}
}
return NULL;
}


int del_data(int _data, d_linked_list* _list) {
node* select;
select = search_data(_data, _list);


if(select == NULL)
return false;


del_node(_list, select);


return true;
}


void show_all(d_linked_list* _list) {
node* trace;
trace = _list->head;


if(trace == NULL) {
printf("List is NULL\n");
return;
}


printf("\n");
printf("=======================================\n");


int i = 1;
while(trace != NULL) {
printf("%3dst node = %d\n", i++, trace->data);
trace = trace->next;
}
printf("=======================================\n");
}

<테스트 코드>
-- test --

#include
#include "list.h"


int main() {
int data;
int command;


d_linked_list* list;
list = NULL;


while(1) {
printf("insert data = (1) \n");
printf("delete data = (2) \n");
printf("delete list = (3) \n");
printf("show all    = (4) \n");
printf("Input command and data:  \n");
scanf("%d %d", &command, &data);


switch(command) {
case 1:
ins_data(data, &list);
break;
case 2:
del_data(data, list);
break;
case 3:
del_list(list);
break;
case 4:
show_all(list);
break;
}


printf("\n");
}


return 0;
}

<컴파일>

$ gcc -c list.c

$ gcc test.c list.o

=====================================================

이 코드는 혹시 나중에라도 필요해졌을때 재사용하기 위함이지, 누군가의 숙제를 대신해주기 위함이 아님을 숙지하자. 이제 정렬 알고리즘들을 구현해서 적용해봐야지.