Chapter 08. 연결 리스트(Linked List)

0. 연결리스트

  - 연결되지 않은 메모리를 사용함. 배열과 정반대의 장단점.

    이때문에, 중간 삽입 중간 삭제가 아주 쉬움.

 

  - 단점은 N번째 방을 바로 찾을수가 없음. 배열과 다름.

    즉, Random Access가 불가능함.

 

1. 기본 코드

#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>
#include <assert.h>
#include <stdlib.h>

enum {
    FALSE = 0,
    TRUE = 1,
    INVALID_INDEX = -1
};

typedef struct node {
    int             nData;
    struct node*    pNext;
    /* struct node_t* 라고 적으면 안됨. */
} node_t;

void destroy(node_t* _pHeadNode);
void recursively_destroy(node_t* _pCurrentNode);
void insert_front(node_t** _dpHeadNode, int _nData);
void orderly_insert_front(node_t** _dpHeadNode, int _nData);
void insert_back(node_t** _dpHeadNode, int _nData);
void remove_node(node_t** _dpHeadNode, int _nData);
void print(node_t* _pHeadNode);

int main(void)
{
    node_t* my_linked_list_head = (node_t*)malloc(sizeof(node_t));
    my_linked_list_head->nData = 0;
    my_linked_list_head->pNext = NULL;

    insert_front(&my_linked_list_head, 1);
    insert_front(&my_linked_list_head, 9);

    printf("The result of insert_front(1) and insert_front(9).\n");
    print(my_linked_list_head);
    printf("\n\n");

    insert_back(&my_linked_list_head, 8);
    insert_back(&my_linked_list_head, 3);
    print(my_linked_list_head);
    printf("\n\n");

    orderly_insert_front(&my_linked_list_head, 4);
    orderly_insert_front(&my_linked_list_head, 10);
    print(my_linked_list_head);
    printf("\n\n");

    insert_back(&my_linked_list_head, 100);
    insert_back(&my_linked_list_head, 120);
    print(my_linked_list_head);
    printf("\n\n");

    remove_node(&my_linked_list_head, 4);
    print(my_linked_list_head);
    printf("\n\n");

    destroy(my_linked_list_head);

    return 0;
}

void destroy(node_t* _pHead)
{
    printf("destroy() has been called. -> ");
    recursively_destroy(_pHead);
    printf("Close to destroy.\n\n");
}
void recursively_destroy(node_t* _pCurrentNode)
{
    if (NULL == _pCurrentNode)
    {
        return;
    }
    recursively_destroy(_pCurrentNode->pNext);
    printf("[%d] has been Deleted. -> ", _pCurrentNode->nData);
    free(_pCurrentNode);
}

void insert_front(node_t** _dpHeadNode, int _nData)
{
    node_t* pNewNode = (node_t*)malloc(sizeof(node_t));
    pNewNode->nData = _nData;
    pNewNode->pNext = (*_dpHeadNode)->pNext;
    (*_dpHeadNode)->pNext = pNewNode;
}

void orderly_insert_front(node_t** _dpHeadNode, int _nData)
{
    node_t** dpCurrentNode = _dpHeadNode;
    node_t* pNewNode = (node_t*)malloc(sizeof(node_t));
    pNewNode->nData = _nData;

    while (NULL != *dpCurrentNode)
    {
        if (pNewNode->nData <= (*dpCurrentNode)->nData)
        {
            break;
        }
        dpCurrentNode = &((*dpCurrentNode)->pNext);
        /* *dpCurrentNode = ((*dpCurrentNode)->pNext); 하면 안됨. */
    }
    pNewNode->pNext = *dpCurrentNode;
    *dpCurrentNode = pNewNode;
    /* pp = &pNewNode; 하면 안됨. */
}

void insert_back(node_t** _dpHeadNode, int _nData)
{
    node_t** dpCurrentNode = _dpHeadNode;
    node_t* pNewNode = (node_t*)malloc(sizeof(node_t));
    pNewNode->nData = _nData;
    pNewNode->pNext = NULL;

    while (NULL != *dpCurrentNode)
    {
        dpCurrentNode = &((*dpCurrentNode)->pNext);
    }
    *dpCurrentNode = pNewNode;
}

void remove_node(node_t** _dpHeadNode, int _nData)
{
    node_t** dpCurrentNode = _dpHeadNode;
    while (NULL != *dpCurrentNode)
    {
        if (_nData == (*dpCurrentNode)->nData)
        {
            node_t* pTempNode = *dpCurrentNode;
            *dpCurrentNode = (*dpCurrentNode)->pNext;
            free(pTempNode);
            break;
        }
        dpCurrentNode = &(*dpCurrentNode)->pNext;
    }
}

void print(node_t* _pHead)
{
    node_t* pCurrentNode = _pHead;
    while(NULL != pCurrentNode)
    {
        printf("[%d:%p]->", pCurrentNode->nData, (void*)pCurrentNode->pNext);
        pCurrentNode = pCurrentNode->pNext;
    }
    printf("[NULL]\n");
}