C 언어 - linked list

지금까지 이야기한 내용을 토대로 linked list 를 구현해 보자.

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 메모리 할당 해제가 추가되어야 한다.