자료구조 - 단순 연결 리스트

자료구조 - 단순 연결 리스트

1. 구조체 선언

typedef struct _node{

    int value;                                                                      -> 원하는 DATA를 넣어서 구현

    struct _node *next;                                                         -> 다음 node 와 연결 시키기 위해 구현

}node, *nptr;

typedef struct _list{

    nptr head;                                                                    -> head 포인터로 Linked List의 제일 처음 부분을  가르킴

    int count;                                                                     -> Linked List의 길이를 알고자 구현

}list;

2. Init 구현

void init_node(list *lptr)

{

    lptr->head = NULL;                                                        -> head 포인트 초기화

    lptr->count = 0;                                                            -> count 변수 초기화

}

void main()

{

    list *mylist = (list*)malloc(sizeof(list));                                   -> list 구조체 만큼 동적할당

    init_node(mylist);                                       

}

3. node 추가

void insert_node(list *lptr, int _value)

{

    node *new_node = (node*)malloc(sizeof(node));                    -> 새 노드에 메모리 할당

    node *pre_node = lptr->head;                                           -> head노드로 부터 마지막 노드까지 검색하기 위한 변수

    new_node->value = _value;                                               -> 새 노드에 입력할 Data를 대입

    new_node->next = NULL;                                                 -> 새 노드가 가르키는 다음 노드를 NULL로

    lptr->count ++;                                                              -> 노드 갯수 확인용

    if(lptr->head == NULL)                                                     -> head 노드가 아직 없을때 처음 노드를 head 노드로 입력

    {

        lptr->head = new_node;

    }

    else                    

    {

        while(!(pre_node->next == NULL))                                   -> head 노드로 부터 마지막 노드를 확인

        {

            pre_node = pre_node->next;                                     

        }

        pre_node->next = new_node;                                         -> 마지막 노드가 새로운 노드를 가르킴

    }

}

4. node 삭제

void delete_node(list *lptr, int _value)

{

    nptr tmp = lptr->head;                                                        -> head노드로 부터 마지막 노드까지 검색하기 위한 변수

    nptr remove_node;                                                              -> 임시 저장 노드

    while(tmp != NULL)

    {

        if(tmp->next != NULL)

        {

            if(lptr->head->value == _value)                                      -> head 노드의 값과 원하는 값이 같을 때

            {

                lptr->head = lptr->head->next;

                lptr->count --;

                break;

            }

            if(tmp->next->value == _value)                                      -> 원하는 노드를 구했을 때

            {

                remove_node = tmp->next;                                        -> 현재노드의 다음 주소를 임시저장

                tmp->next = remove_node->next;                               -> 임시 저장한 주소를 현재 주소의 next에 저장

                lptr->count --;

                break;

            }

        }

        else

        {

            printf("init number\n");

        }

        tmp=tmp->next;

    }

}

5. node 검색

node * search_node(list *lptr, int _value)

{

    nptr tmp = lptr->head;                                                            -> head노드로 부터 마지막 노드까지 검색하기 위한 변수

    while(tmp != NULL)

    {

        if(tmp->value == _value) return tmp;                                       -> 원하는 node를 찾으면 tmp 노드를 반환

        tmp = tmp->next;

    }

}

6. node 출력

void print_node(list *lptr)

{

    nptr tmp = lptr->head;

    printf("value : ");

    while(tmp != NULL)

    {

        printf("%d ",tmp->value);

        tmp=tmp->next;

    }

    printf("\ncount value : %d\n",lptr->count);

}