(c lang) linked-list 구현

연결리스트 구현

노드 구현(node_t형 구조체)

• 노드 구조체는 int 형 val멤버와 다음 노드를 가리키는 node_t형 포인터 next멤버를 갖는다

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

linked-list 초기화

• node_t *head = NULL;
• node_t형 포인터로 초기화

  // initialize head(node_t pointer)
  node_t * head = NULL;

print_list함수

• print_list(node_t *head);
• 첫 노드부터 마지막 노드까지 val 멤버를 출력
• 예외1: 노드가 없는 경우

  // print out value of all nodes
  int print_list(node_t * head){
    node_t *curr = head;
    // exception case: no node
    if (curr == NULL){
        printf("there is no node!\n");
        return -1;
    }
    // print until curr node is NULL
    while (curr != NULL){
        printf("%d ", curr->val);
        curr = curr->next;
    }
    printf("\n");
    return 1;
  }

add_last함수

• add_last(node_t **ptr_head, int val);
• 새 노드 생성 후 연결리스트의 마지막에 첨가
• 이중포인터를 인자로 받는 이유: 노드가 없는 경우(head == NULL) head가 가리키는 주소를 새로 할당해야하므로 head의 주소값(&head <-- node_t**형)을 함수 인자로 받는다
• 연결리스트의 마지막 노드로 이동하여 마지막 노드가 새로운 노드를 가리키게 한다
• 예외1: 노드가 없는 경우 head의 주소값(ptr_head)로 접근해 head의 값을 변경(*ptr_head = new_node)

// add node to last of linked-list
void add_last(node_t **ptr_head, int val){
    node_t *curr = *ptr_head;
    // make new node with given value
    node_t *new_node = (node_t *)malloc(sizeof(node_t));
    new_node->val = val;
    new_node->next = NULL;

    // exception case: no node --> make head to point new_node
    if (curr == NULL){
        *ptr_head = new_node;
    } 
    else{
        // move to last node
        while (curr->next != NULL){
            curr = curr->next;
        }
        // add new node to curr
        curr->next = new_node;
    }
}

push_head함수

• push_head(node_t **ptr_head, int val);
• 연결리스트의 맨 앞에 새로운 노드 삽입
• 새로운 노드를 생성하고 원래 첫 노드를 가리키게 한다. 그리고 원래의 head가 새로운 노드를 가리키게 한다(head를 바꾸기 위해 &head로 접근: node_t **형을 함수 인자로 받음)
• 예외1: 노드가 없는 경우 add_last함수를 실행하면 동일한 효과를 얻는다

  // push node in front of linked-list
  void push_head(node_t **ptr_head, int val){
    // exception case: no node: just append
    if (*ptr_head == NULL){
        add_last(ptr_head, val);
    }
    else {
        // new_node
        node_t *new_node = (node_t *)malloc(sizeof(node_t));
        new_node->val = val;
        // head points to new_node and new_node points to node that head pointed to
        new_node->next = *ptr_head;
        *ptr_head = new_node;
    }
  }

pop_last함수

• pop_last(node_t **ptr_head)
• 연결리스트의 마지막 노드를 pop하고 그 값을 반환
• 노드가 0개, 1개, 그 이상으로 케이스를 나눔
• 노드가 2개 이상일 경우 마지막에서 2번째 노드로 이동하여 마지막 노드 삭제(free로 동적 할당 해제)

  // pop last node
  int pop_last(node_t **ptr_head){
    int return_val;
    node_t *curr = *ptr_head;
    // exception case1: no node
    if (curr == NULL){
        printf("there is no node!\n");
        return -1;
    }
    // exception case2: 1 node
    if (curr->next == NULL){
        return_val = curr->val;
        free(curr);
        *ptr_head = NULL;
    } else{
        // move to second last node
        while (curr->next->next != NULL){
            curr = curr->next;
        }
        return_val = curr->next->val;
        // delete target node
        free(curr->next);
        curr->next = NULL;
    }
    return return_val;
  }

pop_head함수

• pop_head(node_t **ptr_head)
• 연결리스트의 첫 노드를 pop하고(동적 할당 해제) 그 값을 반환
• 노드가 0개, 1개, 그 이상으로 케이스를 나눔
• 노드가 1개일 경우 pop_last함수와 동일한 효과

  // pop out head or linked list
  int pop_head(node_t **ptr_head){
    int return_val;
    node_t* head = *ptr_head;
    // exception case1: no node
    if (head == NULL){
        printf("there is no node!");
        return -1;
    }
    // exception case1: one node
    if (head->next == NULL){
        return pop_last(ptr_head);
    }
    else{
        // make mead to point second node
        *ptr_head = head->next;
        return_val = head->val;
        // delete target node
        free(head);
        return return_val;
    }
  }

remove_by_index함수

• remove_by_index(node_t **ptr_head, int idx)
• 주어진 idx+1번째 노드를 pop(동적 할당 해제)하고 그 값을 반환
• 노드가 0개, 1개, 그 이상으로 케이스를 나눔
• idx-1번째 노드로 이동하여 idx번째 노드 삭제
• idx가 연결리스트의 길이 이상이면 -1 반환

  int remove_by_index(node_t **ptr_head, int idx){
    int return_val;
    node_t *curr = *ptr_head;
    // exception case1: no node
    if (curr == NULL){
        printf("there is no node!");
        return -1;
    }
    // exception case2: idx == 0
    if (idx == 0){
        return pop_head(ptr_head);
    }
    // move curr to node[idx-1]
    for (int i=0; i<idx-1; i++){
        // check if curr->next is NULL; check node[idx] is existing
        if (curr->next == NULL){
            printf("given index exceed the length of linked-list!\n");
            return -1;
        }
        curr = curr->next;
    }
    // target node: node[idx]
    node_t *target = curr->next;
    // check if target_node is NULL
    if (target == NULL){
        printf("given index exceed the length of linked-list!\n");
        return -1;
    }
    return_val = target->val;
    // make curr(node[idx-1]) to point node([idx+1])
    curr->next = target->next;
    // delete target node
    free(target);
    return return_val;
  }