연결 리스트(linked list) - 단순 연결 리스트

연결 리스트에는 단순 연결 리스트, 원형 연결 리스트, 이중 연결 리스트, 이중 원형 연결 리스트가 있다.

                                                    단순 연결 리스트는 단순히 연결만 되어있는 연결 리스트이다.

그럼 단순 연결 리스트를 구현해보겠다.

struct ListNode {
 
    int data; 
    struct ListNode *link; 
};

                                                        이 부분은 노드와 노드의 데이터 필드와 링크 필드를 선언 해주는 부분이다.

struct ListNode *p1; 
 
    p1 = (struct ListNode*)malloc(sizeof(struct ListNode)); 
    p1->data = 10; 
    p1->link = NULL; 

                       

                                                                  이 부분은 p1이라는 노드를 만들고, p1에 메모리를 동적할당 한다.

                                                                  그리고 p1의 데이터와 링크 필드에 값을 넣어준다.

struct ListNode *p2; 
 
    p2 = (struct ListNode*)malloc(sizeof(struct ListNode)); 
    p2->data = 20; 
    p2->list = NULL;
    p1->list = p2; 

 

                                                               여기서는 p2라는 노드를 만들고 데이터, 링크 필드에 값을 넣어주고, 

                                                               p2의 링크필드를 p1의 링크 필드에 넣어줌으로써 p1노드와 p2노드를 연결한다.

 

                                                               이번엔 연결 리스트의 삽입 연산을 구현 해보겠다.

      단순 연결리스트의 삽입 연산에는 3가지 경우가 있다.

(1) 리스트가 공백리스트인 경우(아예 노드가 없는 경우)

(2) 리스트는 있는데 리스트의 맨 앞에 삽입하는 경우

(3) 리스트 중간에 노드를 삽입하는 경우

void insert_node(struct ListNode **phead, struct ListNode *p, struct ListNode *new_node)
{
    if (*phead == NULL) {
        new_node->link = NULL;
        *phead = new_node;
    }
    else if (p == NULL) {
        new_node->link = *phead;
        *phead = new_node;
    }
    else
    {
        new_node->link = p->link;
        p->link = new_node;
 
    }
}

                                                    리스트의 삭제 연산을 구현해보겠다.

                                        

                                                   리스트의 삭제 연산에는 두 가지 경우가 있다.

(1) 리스트의 맨 앞의 노드를 삭제하는 경우

(2) 리스트의 중간 노드를 삭제하는 경우

   

                                                   그리고 포인터를 이용해 연결을 바꿔준 후 free로 노드를 삭제해준다.

void remove_node(struct ListNode **phead, struct ListNode *p, struct ListNode *removed)
{
    if (p == NULL)
    {
        *phead = (*phead)->link;
     }
    else
    {
        p->link = removed->link;
    }
    free(removed);
}