[Linked List] 구현

zeo·2021년 9월 3일
0
#include <stdio.h>
#include <stdlib.h>

// node_t 구조체 생성
typedef struct node {
    int val;
    struct node *next;
} node_t;


// functions
int print_list(node_t *head); 
void add_node(node_t **ptr_head, int val);
void push_head(node_t **ptr_head, int val);
int pop_last(node_t **ptr_head);
int pop_head(node_t **ptr_head);
int remove_by_index(node_t **ptr_head, int idx);

int main(void) {
    //head 설정
    node_t *head = NULL;

    //노드 추가
    add_node(&head, 0);
    add_node(&head, 1);
    add_node(&head, 2);
    add_node(&head, 3);
    add_node(&head, 4);
    add_node(&head, 999);

    //노드 출력
    print_list(head);

    remove_by_index(&head, 3);
    print_list(head);

    return 0;
}

// list 내 노드 출력
int print_list(node_t *head) {
    node_t *curr = head;

    if(curr == NULL) {
        printf("fail\n");
        return -1;
    } 

    while(curr != NULL) {
        printf("%d ", curr -> val);
        curr = curr -> next;
    }
    printf("\n");

    return 0;
}


// 노드 추가(뒤)
void add_node(node_t **ptr_head, int val) {
    node_t *curr = *ptr_head;
    node_t *new_node = (node_t *) malloc(sizeof(node_t));
    new_node -> val = val;
    new_node -> next = NULL;

    if (curr == NULL) {
        *ptr_head = new_node;
    }
    else { //마지막 노드까지 이동
        while (curr->next != NULL) {
            curr = curr -> next;
        }
        curr -> next = new_node;
    }
}

// 노드 추가(앞)
void push_head(node_t **ptr_head, int val) {
    if (*ptr_head == NULL) {
        add_node(ptr_head, val);
    }
    else {
        node_t * new_node = (node_t *) malloc(sizeof(node_t));
        new_node -> val = val;
        new_node -> next = *ptr_head;
        *ptr_head = new_node;
    }
}

// 노드 제거(뒤)
int pop_last(node_t **ptr_head) {
    int return_val;
    node_t *curr = *ptr_head;

    // no node
    if (curr == NULL) {
        printf("fail\n");
        return -1;
    }

    // 1 node
    if (curr -> next == NULL) {
        return_val = curr -> val;
        free(curr);
        *ptr_head = NULL;
    }

    else {
        while (curr -> next -> next != NULL) {
            curr = curr -> next;
        }
        return_val = curr -> next -> val;
        free(curr -> next);
        curr -> next = NULL;
    }

}

// 노드 제거(앞)
int pop_head(node_t **ptr_head) {
    int return_val;
    node_t *head = *ptr_head;

    if (head == NULL) {
        printf("fail!");
        return -1;
    }

    if (head -> next == NULL) {
        pop_last(ptr_head);
    }

    else {
        *ptr_head = head -> next;
        return_val = head -> val;
        free(head);
        return return_val;
    }

}

// 특정 노드 제거
int remove_by_index (node_t **ptr_head, int idx) {
    int return_val;
    node_t *curr = *ptr_head;

    if (curr == NULL) {
        printf("fail\n");
        return -1;
    }

    if (idx == 0) {
        // pop_last(ptr_head);
        pop_head(ptr_head);
    }

    else { //idx-1 까지 이동
        for (int i=0; i < idx-1; i++) {
            if (curr-> next == NULL) {
                printf("fail\n");
                return -1;
            } 
            curr = curr -> next;
        }
    }
    node_t *target = curr -> next; //target이 가리키는 포인터 값은 curr의 next값

    if (target == NULL) {
        printf("fail\n");
        return -1;
    }

    return_val = target -> val;
    curr -> next = target -> next;
    free(target);
    return return_val;
}

참고 링크

0개의 댓글