C 언어 - linked list에서 node를 추가할 때 예외처리

 노드를 추가하는 경우 이 linked list가 어떤 형태를 취하고 있느냐에 따라서 달라진다. 우선, 단일 linked list의 경우

Artist* add_artist(char *name) {
    Artist *ptr_artist = create_artist_instance(name);
 
    Artist *p = artist_directory[(unsigned char)name[0]];// first node
    Artist *q = NULL;
    while (p != NULL && strcmp(p->name, name) < 0) {
        q = p;
        p = p->next;
    }
    if (p == NULL && q == NULL) // unique node
        artist_directory[(unsigned char)name[0]] = ptr_artist;
    else if(q == NULL){ //add at the front
        ptr_artist->next = artist_directory[(unsigned char)name[0]];
        artist_directory[(unsigned char)name[0]] = ptr_artist;
    }
    else { //add after q
        ptr_artist->next = p;
        q->next = ptr_artist;
    }
    return ptr_artist;
}

while (p != NULL && strcmp(p->name, name) < 0) 

단일이기 때문에 순회를 하면서 들어갈 위치를 찾아야 할 것이다. 알파벳 순으로 추가하고 싶어서 이렇게 사용한다고 할 경우 

A B C E 사이에 D node를 넣고 싶다고 가정하자.

while문을 빠져나올 때에는 p가 E노드를 가리키고 있을 것이다. 그래서 p노드 뒤에 추가를 해 주어야 하는데 단일 연결이 되어 있어서 뒤로 돌아갈 수가 없어진다. 이럴 때 쓰는 기법이다. 

    while (p != NULL && strcmp(p->name, name) < 0) {

        q = p;

        p = p->next;

    }

 이렇게 계속 이전 노드를 가리키는 포인터를 생성한다. 

 하여튼 들어갈 위치를 찾아서 넣으려고 하는데 경우가 3가지가 존재하게 된다.

1. 아무것도 없을 때 처음으로 추가

2. 맨 앞에 추가

3. 중간에 추가

 그런데 사실 굳이 1번과 2번을 나눌 필요는 없다. 아래처럼 하면 된다.

Artist* add_artist(char *name) {
    Artist *ptr_artist = create_artist_instance(name);
 
    Artist *p = artist_directory[(unsigned char)name[0]];// first node
    Artist *q = NULL;
    while (p != NULL && strcmp(p->name, name) < 0) {
        q = p;
        p = p->next;
    }
    if(q == NULL){ //add at the front
        ptr_artist->next = artist_directory[(unsigned char)name[0]];// case1 이어도 어차피 이게 NULL 이니까 상관 없음
        artist_directory[(unsigned char)name[0]] = ptr_artist;
    }
    else { //add after q
        ptr_artist->next = p;
        q->next = ptr_artist;
    }
    return ptr_artist;
}

 그럼 만약 이중 linked list일 때는??

void insert_node(Artist *ptr_artist, SNode *ptr_snode) {
    SNode *p = ptr_artist->head;
    while (p != NULL && strcmp(p->song->title, ptr_snode->song->title) < 0)
        p = p->next;
 
    // add ptr_node before p
    // 1. empty 2. at the front 3. at the end 4. in the middle
    if (ptr_artist->head == NULL) { // empty
        ptr_artist->head = ptr_snode;
        ptr_artist->tail = ptr_snode;
    }
    else if (p == ptr_artist->head) { // at the front
        ptr_snode->next = ptr_artist->head;
        ptr_artist->head->prev = ptr_snode;
        ptr_artist->head = ptr_snode;
    }
    else if (p == NULL) { // at the end
        ptr_snode->prev = ptr_artist->tail;
        ptr_artist->tail->next = ptr_snode;
        ptr_artist->tail = ptr_snode;
    } // order problem...
    else { // in the middle before p
        ptr_snode->next = p;
        ptr_snode->prev = p->prev;
        p->prev->next = ptr_snode;
        p->prev = ptr_snode;
    }
}

1. 아무것도 없을 때 처음으로 추가

2. 맨 앞에 추가 head

3. 맨 뒤에 추가 tail

4. 중간에 추가 - 이 때는 q가 필요 없다. prev로 접근할 수 있으므로...