Week 3-2 : Linked List

< 180412 >

1) 노드 추가하기.

#include <stdio.h>
#include <stdlib.h>
 
typedef struct node {
    int data;
    struct node *link;
} ListNode;
 
ListNode* create_node(int data, ListNode* link)
{
    ListNode *newNode = (ListNode*)malloc(sizeof(ListNode));
    newNode->data = data;
    newNode->link = link;
    return newNode;
}
 
void addNode(ListNode** phead, ListNode* newNode)
{
    if(*phead == NULL) *phead = newNode;
    else {
        newNode->link = *phead;
        *phead = newNode;
    }
}
 
int main()
{
    ListNode *head = NULL;
    addNode(&head, create_node(10, NULL)); 
    addNode(&head, create_node(20, NULL)); 
     
    return 0;
}

>> 19 : 메인함수에서의 head 가 NULL 인경우 바로 뉴노드를 연결하면 된다.

>> 20-23 : head 가 어떤 노드를 가지고 있다면, 새로운 노드가 그 노드를 가리키고, head 가 뉴노드를 가리키도록 한다.

>> 이런식으로 진행이 된다.

2) 노드 추가하기 2 (교재처럼..) 

#include <stdio.h>
#include <stdlib.h>
 
typedef struct node {
    int data;
    struct node *link;
} ListNode;
 
ListNode* create_node(int data, ListNode* link)
{
    ListNode *newNode = (ListNode*)malloc(sizeof(ListNode));
    newNode->data = data;
    newNode->link = link;
    return newNode;
}
 
void addNode2(ListNode **phead, ListNode *p, ListNode *newNode)
{
    if(*phead == NULL) *phead = newNode;
    else if(p == NULL) {
        newNode->link = *phead;
        *phead = newNode;
    }
    else {
        newNode->link = p->link;
        p->link = newNode;
    }
}
 
void display(ListNode *phead)
{
    while(phead) {
        printf("%d ", phead->data);
        phead = phead->link;
    }
}   
 
int main()
{
    ListNode *head = NULL;
    ListNode *node;
    addNode2(&head, NULL, create_node(10, NULL)); 
    node = create_node(20, NULL);
    addNode2(&head, NULL, node); 
    addNode2(&head, NULL, create_node(30, NULL)); 
    display(head); puts("");
 
    addNode2(&head, node, create_node(40, NULL));
    display(head); 
    return 0;
}

>> addNode2() 를 보자.  

>> 첫번째 매개변수는 메인함수의 head 의 주소를, p 에는 새로 삽입할 노드의 이전 노드를, 마지막은 새로 삽입할 노드를 가리킨다.

>> 19 : 헤드가 비어있는 경우,

>> 20 : p == NULL 이란 것은 맨 왼쪽에 노드를 삽입하는 경우

>> 그 외의 경우는 p 노드의 다음자리에 새로운 노드를 삽입하는 경우 이다.

>> 실행결과

30 20 10 

30 20 40 10

>> 그림으로 보면 아래와 같다.

- 45 라인까지의 실행결과.

- 48 라인에서 addNode2() 가 호출된 직후의 상황

>> phead 는 *phead 라고 생각하는게 나을것 같다.

- addNode2() 가 호출된 다음, 함수가 종료되기 직전의 상황.

>> phead 는 *phead 라고 생각하는게 나을것 같다.

3) display() 함수 (30-36 라인)

>> display() 함수를 보쟈. 함수의 내용은 어렵지 않을 것이다. 하지만 addNode() 와 비교해보면, 이중포인터로 받지 않는다는 것이 차이점이다.

>> 이것은 main() 의 head 가 가리키는 노드가 변경될 가능성이 있을 경우에는 이중포인터로 받아야 하지만, 

     display() 는 그럴필요가 없기 때문에 이중포인터로 받을 필요가 없다..!!

4) 노드의 삭제