Linked list
List 는 목록을 의미하고 linked 는 각 항목들이 연결되어 있다는 의미다.
특징으로는 프로그램 실행 중 동적으로 항목을 추가하고 제거하고 특정 항목에 접근이 가능하다.
배열은 선언시 크기가 정해지지만 linked list 는 미리 제약을 두지 않는다.
heap 메모리를 이용한다.
node
각 항목들은 node 라는 형태의 구조체에 담긴다.
typedef struct _node_t {
int data;
struct _node_t * next;
} node_t;
- data : 사용자가 지정할 값
- next : 또 다른 node_t 포인터
포인터와 heap 메모리에 대한 설명을 떠올려 보면 예상할 수 있겠지만
새로운 node_t 메모리를 할당하여 next 포인터에 대입시켜 list 에 항목을 추가해 나간다.
node 구조 설계
위에서 data 타입을 int 로 지정하였기 때문에 int 외에 다른 타입의 list 를 원한다면 node_t struct 부터 다시 작성하고 추가 삭제 함수를 다시 작성하여야 하는 문제가 있다.
data 타입을 특정 짓게 되면 node 추가/삭제/탐색 코드에 종속성이 생긴다.
data 타입이 바뀌면 줄줄이 수정해야 하는 코드가 발생하게 됨을 의미한다.
우리는 늘 이러한 종속성을 제거하려고 노력해야 한다.
이러한 종속성은 자바 ArrayList 를 사용해 보았다면 언어 자체에서 지원해 주는 편이 개발자에게는 편하다는 사실을 알 수 있다.
자바 ArrayList 는 꽤나 오랜 세월동안 꽤나 많은 개발자들에 의해 그 사용성이나 실용성에 대한 검증을 받았다.
C 언어의 void 포인터의 특성을 이용해서 이러한 종속성을 해결할 수 있다.
void * (void 포인터) 와 cast
void 는 함수의 파라메터나 리턴값이 없음을 의미했다.
void * 는 모든 타입 포인터를 대입할 수 있다.
void * data;
int num;
char ch;
data = (void*)#
data = (void*)&ch;
cast 는 포인터 타입 변환을 통한 데이터 접근 방법을 명시하는 기능이다.
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
typedef struct _header_t {
char magic[2];
int length;
} header_t;
int main(int argc, char *args[]) {
char data[1024] = {0,};
{
// write data
header_t * header = (header_t*)data;
header->magic[0] = 'M';
header->magic[1] = 'Z';
strcpy((char*)(data + sizeof(header_t)), "Hello World");
header->length = strlen((char*)(data + sizeof(header_t))) + 1;
}
{
// read data
header_t * header = (header_t*)data;
int length = header->length;
char * text = (char*)malloc(length);
strncpy(text, (char*)(data + sizeof(header_t)), length);
printf("MAGIC: %c%c, LENGTH: %d, TEXT: %s\n", header->magic[0], header->magic[1], length, text);
}
return 0;
}
위 예제를 통해 데이터 뭉터기를 어떤 타입 포인터에 cast 하느냐에 따라 데이터 접근 방법이 달라진다는 특징을 알 수 있다.
이 말은 실제로 데이터 뭉터기이가 배열인지 문자열인지 개발자가 신경써야 한다는 의미다.
head node
시작 node 는 list 의 첫번째 node 를 가리키는 포인터이다.
node_t * head = NULL;
node 생성
static node_t * s_create_node(int data) {
node_t * node = (node_t *)malloc(sizeof(node_t));
memset(node, 0, sizeof(node_t));
node->data = data;
return node;
}
node 추가
static void s_add_node(node_t ** head, node_t * node) {
node_t * temp = *head;
if (!*head) {
*head = node;
return;
}
for (;temp && temp->next; temp = temp->next) {}
temp->next = node;
}
node 탐색
tatic node_t * s_find(node_t * head, int data) {
node_t * temp = head;
for (; temp; temp = temp->next) {
if (temp->data == data) {
return temp;
}
}
return NULL;
}
node 제거
static void s_remove_node(node_t ** head, node_t * node) {
node_t * temp = *head;
if (*head == node) {
*head = (*head)->next;
return;
}
for (;temp && temp->next; temp = temp->next) {
if (temp->next == node) {
temp->next = node->next;
free(node);
break;
}
}
}
list.c
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
typedef struct _node_t {
int data;
struct _node_t * next;
} node_t;
static node_t * s_create_node(int data) {
node_t * node = (node_t *)malloc(sizeof(node_t));
memset(node, 0, sizeof(node_t));
node->data = data;
return node;
}
static void s_add_node(node_t ** head, node_t * node) {
node_t * temp = *head;
if (!*head) {
*head = node;
return;
}
for (;temp && temp->next; temp = temp->next) {}
temp->next = node;
}
static void s_remove_node(node_t ** head, node_t * node) {
node_t * temp = *head;
if (*head == node) {
*head = (*head)->next;
return;
}
for (;temp && temp->next; temp = temp->next) {
if (temp->next == node) {
temp->next = node->next;
free(node);
break;
}
}
}
static void s_destroy(node_t ** head) {
node_t * temp = *head;
while(temp) {
node_t * next = temp->next;
free(temp);
temp = next;
}
*head = NULL;
}
static int s_size(node_t * head) {
int i = 0;
node_t * temp = head;
for (; temp; temp = temp->next, i++) {}
return i;
}
static node_t * s_get(node_t * head, int index) {
int i = 0;
node_t * temp = head;
for (; temp && i != index; temp = temp->next, i++) {}
return temp;
}
static node_t * s_find(node_t * head, int data) {
node_t * temp = head;
for (; temp; temp = temp->next) {
if (temp->data == data) {
return temp;
}
}
return NULL;
}
static void s_print_list(node_t * list) {
int i;
int size = s_size(list);
for (i = 0; i < size; i++) {
node_t * node = s_get(list, i);
int data = node->data;
printf("%d ", data);
}
printf("\n");
}
int main(int argc, char *args[]) {
node_t * list = NULL;
int i;
int size;
for (i = 0; i < 10; i++) {
s_add_node(&list, s_create_node(i * 5));
}
s_print_list(list);
s_remove_node(&list, s_get(list, 5));
s_remove_node(&list, s_get(list, 2));
s_print_list(list);
s_destroy(&list);
return 0;
}
만약 data 타입을 void * 형태로 한다면 data 에 대한 heap 메모리 할당 해제가 추가되어야 한다.
댓글 없음:
댓글 쓰기