Linked List 구현

 

Linked List 는 굉장히 유용한 자료 구조이다. 

이를 c 언어로 구현한 예제 이다. 

 

각 노드는  다음 노드의 주소를 가지고 

자신의 값 (data)  를 가지고 있다 .

 

첫 노드는 무조건 0 을 data 로 갖는다. 

 

malloc 함수와 free 함수를 써 볼 수 있는 유용한 예제이다.

#include<stdio.h>

#define TRUE 1
#define FALSE 0

typedef struct list_node
{
    int data;
    struct list_node* next;
}LINKED_LIST;

LINKED_LIST* init_list();// 연결 리스트 초기화
LINKED_LIST* make_node();// 빈 노드 생성

int insert_node(LINKED_LIST*, int, int); // 노드 삽입
int add_node(LINKED_LIST*, int); // 맨끝에 노드 추가 
int delete_node(LINKED_LIST*, int); // 노드 1개 삭제 
int delete_all(LINKED_LIST*);// 모든 리스트 삭제 
void print_list(LINKED_LIST*); // 모든 리스트 출력


LINKED_LIST* init_list()
{
    LINKED_LIST* head;
    head = make_node();
    head->data = 0;
    head->next = NULL;
    return head;
}

LINKED_LIST* make_node()
{
    LINKED_LIST* temp;
    temp = (LINKED_LIST*)malloc(sizeof(LINKED_LIST));// 동적 할당 

    if (!temp)
    {
        printf("unable  to make new node");
        return NULL;
    }
    return temp;
}

int insert_node(LINKED_LIST* list,int data, int key)
{
   LINKED_LIST* temp, * p;
   
   if (!list) // 리스트가 없는경우 
   {
      printf("this list is not initialized");
      exit(0);
   }

   p = list;
   while (p)
   {
       if (p->data == key)
       {
           temp = make_node();
           temp->data = data;
           temp->next = p->next;
           p->next = temp;
           break;
       }
       p = p->next;
   }
   if (!p)
   {
       printf("Unable to find the key node  by key : %d\n", key);
       return FALSE;
   }
   return TRUE;
}

int add_node(LINKED_LIST* list, int data)
{
    LINKED_LIST* p, * temp, * prev=0;

    if (!list) // 리스트가 없는경우 
    {
        printf("this list is not initialized");
        exit(0);
    }
    p = list;
    while (p)
    {
        prev = p;
        p = p->next;
    }
    temp = make_node();
    if (!temp)
    {
        printf("Unable to add a new node");
        return FALSE;
    }
    temp->data = data;
    temp->next = NULL;
    prev->next = temp;
    return TRUE;
}

int delete_node(LINKED_LIST* list, int key)
{
    LINKED_LIST* p,  * prev=0;
    
    if (!list) // 리스트가 없는경우 
    {
        printf("this list is not initialized");
        exit(0);
    }
    
    p = list;

    while (p)
    {
        if (p->data == key)
        {
            prev->next = p->next;
            free(p);
            break;
        }
        prev = p;
        p = p->next;
    }

    if (!p)
    {
        printf("Unable to find key node %d", key);
        return FALSE;
    } 
    return TRUE;
}

int delete_all(LINKED_LIST* list)
{
    LINKED_LIST* p, * prev;
    if (!list) // 리스트가 없는경우 
    {
        printf("this list is not initialized");
        exit(0);
    }
    p = list;
    while (p)
    {
        prev = p;
        p = prev->next;
        free(prev);
    }
    return TRUE;

}

void print_list(LINKED_LIST* list)
{
    LINKED_LIST* p;
    if (!list) // 리스트가 없는경우 
    {
        printf("this list is not initialized");
        exit(0);
    }

    p = list->next; //처음 노드는 값을 저장하는 용도가 아님 

    while (p)
    {
        if (p->next == NULL)
        {
            printf("%d \n", p->data);
        }
        else
        {
            printf("%d ->", p->data);
        }
        p = p->next;
    }
}

int main()
{
    LINKED_LIST* myLIst;
    myLIst = init_list();
    add_node(myLIst, 100);
    print_list(myLIst);
    add_node(myLIst, 200);
    print_list(myLIst);
    add_node(myLIst, 300);
    print_list(myLIst);
    add_node(myLIst, 400);
    print_list(myLIst);
    add_node(myLIst, 500);
    print_list(myLIst);
    insert_node(myLIst, 250, 200);
    print_list(myLIst);
    delete_node(myLIst, 300);
    print_list(myLIst);

    delete_all(myLIst);
    print_list(myLIst);
    return 0;

}