씨언어 Linkied lists 익히는 중

A linked list is held using a local pointer variable which points to the first item of the list. If that pointer is also NULL, then the list is considered to be empty.

    ------------------------------              ------------------------------
    |              |             |            \ |              |             |
    |     DATA     |     NEXT    |--------------|     DATA     |     NEXT    |
    |              |             |            / |              |             |
    ------------------------------              ------------------------------

//노드의 구조?는 이렇게 생겼다(데이터를 가지고 잇고/넥스트 라는 주소값?저장?을 통해..먼말인지..암튼 감잡는 중!)

Let's define a linked list node:

typedef struct node {
    int val;
    struct node * next;
} node_t;

Node_t 라는 node구조를 정의함

(int val이랑(데이터의역할) 그리고 넥스트의역할(주소값을 가지는 next를 주소값에 포인터를 향하게 한다, 이를통해 값이 어디에 잇는지 알수잇는것)

Notice that we are defining the struct in a recursive manner, which is possible in C. Let's name our node type node_t.

Now we can use the nodes. Let's create a local variable which points to the first item of the list (called head).

node_t * head = NULL;
head = malloc(sizeof(node_t));
if (head == NULL) {
    return 1;
}

head->val = 1;
head->next = NULL;

head라고 불리는 지역변수를 node_t가 포인터를 향하게 한다 아직 값이 없으므로 NULL지정

그리고 그 head의 사이즈를 지정함(프리사이즈)

만약 head변수가 NULL이면 아무것도 없다는 뜻이므로(return 1 실패?를 반환함)

그리고 head->val, head->next 헤드의 첫번째 밸류는 1이고 넥스트가 향하는 포인터는 없으므로 NULL이라고 꼭 해줘야 함

We've just created the first variable in the list. We must set the value, and the next item to be empty, if we want to finish populating the list. Notice that we should always check if malloc returned a NULL value or not.

To add a variable to the end of the list, we can just continue advancing to the next pointer:

node_t * head = NULL;
head = malloc(sizeof(node_t));
head->val = 1;
head->next = malloc(sizeof(node_t));
head->next->val = 2;
head->next->next = NULL;

//늘릴때마다 메모리할당하고 마지막 밸류 끝에는 NULL

This can go on and on, but what we should actually do is advance to the last item of the list, until the next variable will be NULL.

Iterating over a list

Let's build a function that prints out all the items of a list. To do this, we need to use a current pointer that will keep track of the node we are currently printing. After printing the value of the node, we set the current pointer to the next node, and print again, until we've reached the end of the list (the next node is NULL).

void print_list(node_t * head) {    //node_t에서 head를 값으로?받고
    node_t * current = head;        //그 head를 node_t가 현재 가르키고 있는 current 포인터의 값임

    while (current != NULL) {      //current가 null이 아닌이상 
        printf("%d\n", current->val);    //head인 current(..)가 가지고 있는 value를 프린트한다 
        current = current->next;          //그리고 current는 next로 넘어가는게 현재의 current가됨
    }
}

Adding an item to the end of the list

//아이템을 리스트 끝에 넣어보자!

To iterate over all the members of the linked list, we use a pointer called current. We set it to start from the head and then in each step, we advance the pointer to the next item in the list, until we reach the last item.

void push(node_t * head, int val) {      //node_t가 가르키는 헤더, int val을 받음
    node_t * current = head;             //head는 node_t의 current가 가르키고 있는 값(주소)이다
    while (current->next != NULL) {      //current의 next값이 null이 아닌이상
        current = current->next;           //current의 next값으로 current가 가르키는 값이 이동
    }

    /* now we can add a new variable */
    current->next = malloc(sizeof(node_t));    //current의 next값 메모리 할당

    current->next->val = val;       //current의 next의 val에 val을 저장
    current->next->next = NULL;      //current의 next의 next는 null
}

Adding an item to the beginning of the list (pushing to the list)

//첫번째 리스트 전에 아이템 넣어보기(아이템 밀기)

To add to the beginning of the list, we will need to do the following:

1. Create a new item and set its value
2. Link the new item to point to the head of the list
3. Set the head of the list to be our new item

This will effectively create a new head to the list with a new value, and keep the rest of the list linked to it.

Since we use a function to do this operation, we want to be able to modify the head variable. To do this, we must pass a pointer to the pointer variable (a double pointer) so we will be able to modify the pointer itself.

//더블 포인터= 헤드 값을 수정하려면 더블포인터 써야됨

void push(node_t ** head, int val) {          //더블 포인터
    node_t * new_node;                          //new_node라는 noed_t값을 정의
    new_node = malloc(sizeof(node_t));          //new_node 메모리 할당
   
    new_node->val = val;                        //val값을 new_node가 가르키는 val공간에 저장
    new_node->next = *head;                     //현재 가지고 있던 head가 new_node가 가르키는 next가 됨

    *head = new_node;                           //그리고 그 head랑 붙인 new_node가 새 head가됨
}

Removing the first item (popping from the list)

(첫번쨰 아이템 제거!)

To pop a variable, we will need to reverse this action:

1. Take the next item that the head points to and save it
2. Free the head item
3. Set the head to be the next item that we've stored on the side

Here is the code:

int pop(node_t ** head) {            //int를 반환하는 pop(head를 받음)
    int retval = -1;                 //int retval값 -1
    node_t * next_node = NULL;        //next_node라는 값을 node_t안에 정의하고 null로 값을가짐

    if (*head == NULL) {           //head포인터변수가 null이라면 return -1
        return -1;
    }

    next_node = (*head)->next;        //head포인터변수의 next를 next_node로 저장
    retval = (*head)->val;            //head포인터변수의 val을 retval로 저장
    free(*head);                      //동적할당공간 더이상 쓸일이 없으면 free를 쓴다고 한다
    *head = next_node;                //next_node를 새로운 head포인터변수로 대체

    return retval;                    //retval을 리턴함 -1리턴은 무슨의미지
}

Removing the last item of the list

(마지막 아이템 제거)

Removing the last item from a list is very similar to adding it to the end of the list, but with one big exception - since we have to change one item before the last item, we actually have to look two items ahead and see if the next item is the last one in the list:

int remove_last(node_t * head) {             //head변환필요없음
    int retval = 0;                                //int retval을 0으로 설정 왜?
    /* if there is only one item in the list, remove it */        
    if (head->next == NULL) {             //만약 head의 next가 null이면
        head->val                         //head의 val 값(뭐 어쩌라고..)
        free(head);                         //head 공간 해제?
        head = NULL;                       //head는 null이다
        return retval;                    //0을 리턴하라
    }

    node_t * current = head;                  //만약 값이 1개 이상이라면 커렌트 포인터변수는 헤드를

    while (current->next->next != NULL) {     //current의 다음 다음이상 존재한다면
        current = current->next;              //current의 nextnext가 null을 가르킬때까지 돌린다
    }
}

//여기에 current->next = Null을 넣어야 할 것 같은데 모르겠다....뭐지.........

Removing a specific item

To remove a specific item from the list, either by its index from the beginning of the list or by its value, we will need to go over all the items, continuously looking ahead to find out if we've reached the node before the item we wish to remove. This is because we need to change the location to where the previous node points to as well.

Here is the algorithm:

1. Iterate to the node before the node we wish to delete
2. Save the node we wish to delete in a temporary pointer
3. Set the previous node's next pointer to point to the node after the node we wish to delete
4. Delete the node using the temporary pointer

There are a few edge cases we need to take care of, so make sure you understand the code.

int remove_by_index(node_t ** head, int n) {    //인덱스에 따라 제거, head, int n
    int i = 0;                                  //int i 는 0
    int retval = -1;                            //int retval은 -1의 값을 가진다
    node_t * current = *head;                   //head포인터 값은 current포인터 값으로 정의
    node_t * temp_node = NULL;                  //temp_node포인터 값은 현재로써 null

    if (n == 0) {                               //만약 n=0이라면
        return pop(head);                       //head맨첨에 잇는 값을 반환 pop이 아마 내장코드
    }

    for (int i = 0; i < n-1; i++) {             //i가0인데 i가 n-1보다 작을동안 i++하면서
        if (current->next == NULL) {            //만약 current->next가 null이라면 return -1
            return -1;                          
        }
        current = current->next;                //아니라면 current->next값이 curent임 
    }                                           //n번째 노드를 찾는 것
 
    temp_node = current->next;                  //current->next값을 temp_node라고 함
    retval = temp_node->val;                    //temp_node의 val값이 retval에 저장
    current->next = temp_node->next;            //temp_node->next 값을 current->next에 저장
    free(temp_node);

    return retval;

}

어렵다

ㅠ_ㅠ