1108-TIL(doubly linked list, ifelse VS if else)

coretime - pointer 연습 위한 doubly linked list 구현하기

#include <stddef.h>
#include <stdlib.h>

typedef struct node_t {
    int value;
    struct node_t* prev;
    struct node_t* next;
} node_t;

typedef struct {
    node_t* head;
    size_t len;
} list;

// list pointer를 반환
list* list_init(){
    // 빈 리스트를 초기화
    list* p = (list*)calloc(1, sizeof(list));
    p->head = NULL;
    p->len = 0;
    return p;
}

// 노드 포인터를 반환
node_t* make_node__(int val) {
    // 노드 초기화
    node_t* p = (node_t*)calloc(1, sizeof(node_t));
    p->value = val;
    p->prev = NULL;
    p->next = NULL;
    return p;
}

void list_append_right(list* list, int value) {
    node_t* new_node_p = make_node__(value);
    node_t* cur = list->head;
    if (list->head == NULL) { // 이거 안넣으면 head가 널이라서 밑에서 에러남
        list->head = new_node_p;
        list->len += 1;
        return;
    }

    while (cur->next != NULL) {
        cur = cur->next;
    }

    cur->next = new_node_p;
    new_node_p->prev = cur;
    list->len += 1;
}

void list_append_left(list* list, int value) {
    node_t* new_node_p = make_node__(value);
    // head가 new_node_p가 된다
    if (list->head == NULL) {
        list->head = new_node_p;
        list->len += 1;
        return;
    }

    new_node_p->prev = NULL;
    new_node_p->next = list->head;
    list->head->prev = new_node_p;
    list->head = new_node_p;
    list->len += 1;
}


node_t* find(list* list, int value) {
    // list->head->next를 하나씩 전부 뒤져가며 같은 val 찾기
    node_t* cur_node = list->head;
    // node의 next가 널이 아닐때까지
    while (cur_node != NULL) {
        if (cur_node->value == value) {
            return cur_node;
        } else {
            cur_node = cur_node->next; // 여기 못함
        }
    }

    return NULL;
}

// head node 지우기
void delete_left(list* list) {
    // 헤드노드의 다음 노드의 prev를 NULL로 바꾸기
    node_t* cur_node = list->head;
    if (cur_node == NULL) {
        return;
    }

    if (cur_node->next == NULL) {
        free(cur_node);
        list->head = NULL; // <- next가 없으면
        list->len -= 1;
        return;    
    }

    cur_node->next->prev = NULL;
    list->head = cur_node->next;
    list->len -= 1;
    free(cur_node);
}

// 맨끝 노드 지우기
void delete_right(list* list) {
    node_t* cur_node = list->head;
    if (cur_node == NULL) {
        return;
    }


    while (cur_node->next != NULL){
        cur_node = cur_node->next;
    }

    if (cur_node->prev == NULL) {
        list->head = NULL; // 원소가 하나일떄
        list->len -= 1;
        free(cur_node);
        return;
    }
    // cur_node 끝까지 옴
    // cur 전 노드의 넥스트를 널로
    cur_node->prev->next = NULL;
    list->len -= 1;
    free(cur_node);
}

// n노드 오른쪽에 insert하기
void insert_node(list* list, node_t* n, int value) {
    node_t* inserting_node = make_node__(value);
    
    inserting_node->next = n->next;
    if (n->next != NULL) {
        n->next->prev = inserting_node;
    }   
    n->next = inserting_node;
    inserting_node->prev = n;

    list->len += 1;

}

int main() {
    list* lst = list_init();
    list_append_left(lst, 99);
    list_append_right(lst, 111);
    list_append_right(lst, 111111);
    list_append_left(lst, 99123);
    node_t* found_one = find(lst, 99);
    insert_node(lst, found_one, 88);
    delete_left(lst);
    delete_right(lst);
}

하면서 깨닳았는데 해당 노드가 가지고 있는 다음 노드를 가르키는 next pointer 를 사용해서 while문으로 하나씩 탐색하는거를 잘 못했다.

정확히는 cur_node = cur_node->next;
그러니까 cur_node라는 포인터에 cur_node 다음 노드가 올 수 있게 하는 부분을 어려워했다. (지금 생각하면 너무 이해되는 원리인데..)

의사코드 -> c로 옮길 때 ifelse VS if else

Introduction to algorithm 교재에 나와있는 의사코드는 파스칼이라는 문법으로 알아보기 힘든 부분이 있었는데 그 중에서도 단연 ifelse와 if else의 차이였다.

이것 때문에 else문 안이 아니라 바깥에 잘못쳤던 코드가 있었는데 그게 잘못된지 모르고 코드 내용만 계속 확인하면서 많은 시간과 팀원들이 달라붙어도 한시간넘게 찾지 못했었다.

이 둘의 차이는 아래와 같다.

• elseif 그러니까 else와 if가 붙어있는 경우는 그냥 else if(조건문) 이렇게 사용하면 된다.
• else if는 else { } if (조건문) { } 이런 식으로 사용해야한다.

elseif 예시

이러한 수도코드가 있을 때는 아래와 같이 작성하면 된다.

void delete_transplant__(rbtree *t, node_t *u, node_t *v) {
  if (u->parent == t->nil) {
    t->root = v;
  } else if (u == u->parent->left) {
    u->parent->left = v;
  } else {
    u->parent->right = v;
    
  }
  v->parent = u->parent;
}

else if 예시

} else {
    if (w->right->color == RBTREE_BLACK) {
        w->left->color = RBTREE_BLACK;
        w->color = RBTREE_RED;
        right_rotation__(t, w);
        w = x->parent->right;
    }
    w->color = x->parent->color;
    x->parent->color = RBTREE_BLACK;
    w->right->color = RBTREE_BLACK;
    left_rotation__(t,x->parent);
    x = t->root;
}

a단락이 if문 안에 들어가고 b단락이 if문이 끝나고 else문에 들어가는 모습을 볼 수 있다.