[C] Linked List - 삽입, 삭제, 순회

insert_node()

void insert_node(ListNode **phead, ListNode *p, ListNode *new_node)

# phead: 헤드포인터 head에 대한 포인터
# p : 삽입될 위치의 선행노드를 가리키는 포인터(이 노드 다음에 삽입)
# new_node : 새로운 노드를 가리키는 포인터

 

삽입의 3가지 경우

1) head가 NULL인 경우: 공백 리스트에 삽입

2) p가 NULL인 경우 : 리스트의 맨 처음에 삽입

3) 일반적인 경우: 리스트의 중간에 삽입

 

왜 head포인터를 바로 전달하지 않고 head포인터의 주소인 phead를 인자로 전달하는지?

그것은 C언어에서 함수를 호출할때 Call by vallue로 인자를 전달하기 때문에 head포인터를 그냥 전달해 버리면 값이 copy 되서 전달이 되버린다. 원래 값을 바꿔줘야 하기 때문에 phead를 인자로 전달한다.

 

 

3) head와 p가 NULL이 아닌경우 즉 리스트의 중간에 삽입하는 경우

 

new_node의 링크는 p가 가르키는 노드의 다음 노드를 가리키도록

new_node->link = p->link;

p가 가르킬 노드의 링크는 new_node의 링크를 가리키도록

p->link = new_node;

 

2) p가 NULL인 경우 즉 새 노드를 리스트의 맨 앞에 삽입하는 경우

 

new_node의 링크가 기존 리스트의 첫번째 노드를 가리키도록

new_node->link = head;

head포인터가 새로운 노드를 가리키도록

head = new_node;

 

1) head가 NULL인 경우 즉 현재 리스트가 비어있는 경우

삽입하려는 노드가 첫 번째 노드가 된다.

 

새로 만들려는 노드의 링크를 NULL로

new_node->link = NULL;

head포인터가 새로운 노드를 가리키도록

head = new_node;

 

 

이중 포인터 사용 이유

위 코드는 C언어에선 정상적으로 작동하지 않는다.

이유는 함수의 인자로 넘어갈때 call by value 로 값이 복사되기 때문이다.

이를 해결하려면 다음과 같다.

 

1) head가 NULL인 경우

새로운 노드의 링크는 NULL이 되고

head포인터는 NULL이 아닌 새로운 노드를 가리키게 된다.

insert_node(...){
...
new_node->link = NULL;
head = new_node;
...
}

void main(){
	...head....
    insert_node(head,...);
}

 

main 함수에서 head를 이중포인터가 아닌 일반 포인터를 insert_node 함수에 매개변수로 전달했다고 해보자

insertnode에 copy되서 전달된 head는 새로운 노드를 가리키지만 main함수의 head포인터는 영향을 받지 않는다.

 

이 문제를 해결하기 위해 head포인터를 인자로 전달하는게 아닌 head포인터의 포인터를 매개변수로 전달해야 한다.

new_node->link = NULL;
*phead = new_node;

 

2) p가 NULL인 경우

선행 노드를 가리킬게 없다 즉 새로운 노드가 기존 노드의 첫번째 노드로 삽입되는 경우이다.

새로운 노드가 기존 리스트의 첫번째 노드를 가르켜야 한다.

head 의 주소는 새로운 노드를 가리켜야 한다.

 

이 경우에도 head의 포인터를 전달해줘야 하기 때문에 매개변수로 포인터 head의 포인터 변수를 사용한다.

new_node->link = *phead;
*phead = new_node;

 

 

 

insert_node() 함수

// phead: 리스트의 헤드 포인터의 포인터
// p : 선행 노드
// new_node : 삽입될 노드
void insert_node(ListNode **phead, ListNode *p, ListNode *new_node){
	if (*phead == NULL){ // 리스트가 비어있는 경우
    	new_node->link = null;
        *phead = new_node;
    }
    else if (p==NULL){ // 첫번째 노드로 삽입할때
    	new_node->link = *phead;
        *phead = new_node;
    }
    else {  // p 다음에 삽입할때
    	new_node->link = p->link;
        p->link = new_node;
    }
}

 

remove_node

void remove_node(ListNode **phead, ListNode *p)

# phead: 헤드 포인터 head의 포인터
# p: 삭제될 노드의 선행 노드를 가리키는 포인터

 

삭제의 2가지 경우

1) p가 NULL인 경우 : 맨 앞의 노드를 삭제

2) p가 NULL이 아닌 경우 : p 다음의 노드를 삭제

 

 

2) P가 NULL이 아닌 경우

삭제할 노드를 임시 포인터 변수 removed에 담기

removed = p->link;

포인터 변수 p가 가르키는 노드의 다음 노드를 삭제할 노드의  다음 노드로 변경

p->link = removed->link;

링크 연결을 끊은 노드의 메모리를 반환

free(removed);

 

1) P가 NULL인 경우

삭제할 노드를 임시 포인터 변수 removed에 담기

removed = head;

head가 삭제할 노드의 다음 노드를 가리키도록 변경

head = head->link;

링크 연결을 끊은 노드의 메모리를 반환

free(removed);

 

insert_node 함수와 마찬가지로 인자로 이중포인터가 아닌 head포인터를 그대로 가져오면 값이 복사될 뿐 메인 함수의 head가 변경되지 않는다. 그렇기 때문에 head를 모두 *phead로 바꿔줘야 한다.

removed = *phead;
*phead = (*phead)->link;
free(removed);

 

remove_node 함수

void remove_node(ListNode **phead, ListNode *p){
    ListNode *removed;
    
    if(p==NULL) {
    	removed = *phead;
        *phead = (*phead)->link;
    } else {
    	removed = p->link;
        p->link = removed->link;
    }
	free(removed);
}

 

Traversal

방문 연산: 리스트 상의 노드를 순차적으로 방문

반복과 재귀를 모두 사용 가능하다

특정 값을 검색하거나 삭제하는등의 응용이 가능

 

반복

void display_iterative(ListNode *head){
    ListNode *p = head;  //각 노드를 방문하는 포인터
    while(p != NULL) {
    	printf("%d ", p->data);
        p = p->link;
    }
}

재귀

void display_recursive(ListNode *head){
    ListNode *p=head;
    if(p != NULL){
    	printf("%d ", p->data);
        display_recursive(p->link);
    }
}

 

search

특정한 데이터 값을 가진 노드를 찾는 함수

ListNode *search(ListNode *head, int num){
	ListNode *p;
    p = head;
    while(p != NULL){
    	if(p->data == num) {
        	return p; // 탐색 성공 시 주소 반환
        }
        p = p->link;
    }
    return p; // 탐색 실패 시 마지막 노드의 link의 값인 NULL 반환
}

 

concat

2개의 리스트를 합하는 연산

ListNode *concat(ListNode *head1, ListNode *head2){
	ListNode *p;
    if (head1 == NULL){
    	return head2;
    }
    else if (head2 == NULL){
    	return head1;
    }
    else {
    	p = head1;
        while(p->link != NULL){ //p가 마지막 노드를 가리킬때 == NULL직전
        	p = p->link;
        }
        p->link = head2;
        return head1;
    }
}

 

reverse

리스트의 노드를 역순으로 만드는 함수

ListNode *reverse(ListNode *head){
	//순회 포인터로 p, q, r을 사용
    ListNode *p, *q, *r;
    p = head; // 역순으로 만들 리스트
    q = NULL; // 역순으로 만들 노드
    while (p != NULL){
    	r = q; // r은 역순으로 된 리스트, r은 q, q는 p를 차례로 따라간다.
        q = p;
        p = p->link;
        q->link = r; // q의 링크 방향을 바꾸기
    }
    return q; // 역순으로 바뀐 리스트의 헤드 포인터
}