#2-3. 연결 리스트의 삽입과 삭제(2) : 삭제

지난 포스팅에서는 단일 연결리스트의 삽입에 대해 알아보았다. 이번 포스팅에서는 연결리스트의 삭제에 대해 알아보도록 하자.

https://udangtangtang-cording-oldcast1e.tistory.com/182

#2-3. 연결 리스트의 삽입과 삭제(1) : 삽입

단일 연결리스트의 삭제 알고리즘

삭제 알고리즘은 삽입 알고리즘의 변형이라고 생각하면 된다. 

단일 연결리스트의 삭제 알고리즘의 로직은 다음과 같다.

1. 삭제하고 싶은 데이터를 가진 노드를 선언하고 초기화한다.
2. 기존의 연결리스트를 순회하고, 삭제할 조건이 맞는 노드를 찾는다.
3. 삭제할 노드의 이전 노드의 다음 노드 방향을 삭제할 노드의 다음 노드 방향으로 설정한다.
4. 삭제하고 싶은 데이터를 가진 노드를 동적 해제한다.

ListNode* Delete(ListNode *head, ListNode *del){
    ListNode* curr = head->next; 
	while(curr->next != NULL){ //연결리스트 출력
        // printf(">> %c\n", curr->data);
        if((curr->next)->data == del->data){
            // printf("<< %c | %c >>\n", curr->next->data,curr->next->next->data);
            curr->next = (curr->next)->next;
            break;
        }
		curr = curr->next;
	} //free(curr);
    
    ListNode* cnt = head->next; 
    printf("연결리스트의 삭제 함수 실행 후 "); 
	Print(head);
    return head;
}

[알고리즘 문제 풀이 전략]의 책에 따른 코드는 삽입/삭제 함수의 인자로 삽입/삭제 대상 함수만을 받지만 필자는 해당 조건을 충족하기 위해 인자를 하나만 넣었을 때 오류가 발생했다. 이는 web 개발툴의 문제인지 코드의 오류인지 분석할 시간이 부족해 head를 저장하는 구조체 포인터를 함께 인자로 넣어 작성했다.

해당 버그를 찾기 위해서 코드의 답을 인터넷에 찾아보았지만 찾을 수 없었고 군대 특성상 코드를 스캔할 수 없고 정해진 시간 내에 진도를 나가야 하므로 디버깅은 다음으로 미루도록 한다.

최종 코드

이전 포스팅에서 추가로 수정한 코드는 다음과 같다.

• 연결리스트의 노드 추가
• Initailize 함수의 간결화
• 노드를 출력할 Print 함수 생성
• Delete 함수 생성 및 실행 후 동적 할당 제거

#include  <stdio.h>
#include  <string.h>
#include  <stdlib.h>

typedef char element;

typedef struct ListNode {
	element data;
	struct ListNode *next;
}ListNode;

void Initialize(ListNode *head){
    ListNode* NodeArr[6];
    for(int i=0;i<6;i++) NodeArr[i] = (ListNode*)malloc(sizeof(ListNode));
   
    for(int i=0;i<5;i++){    
        if(i==0) head->next = NodeArr[0];
        else NodeArr[i-1]->next = NodeArr[i];//node1의 꼬리를 (기존)헤드의 꼬리로 연결
        NodeArr[i]->data = 'A'+ i;      
    }   
    NodeArr[5]->next = NULL;
}

void Print(ListNode *head){
    ListNode* cnt = head->next; 
    // printf("연결리스트의 함수 실행 후"); 
	while(cnt != NULL){ //연결리스트 출력
		printf("%c ", cnt->data);
		cnt = cnt->next;
	}printf("\n");
}

ListNode* Plus(ListNode *head, char value){
    ListNode* curr = head->next; 
	while(curr->next != NULL){ //연결리스트 출력
		// printf(">> %c\n", curr->data);
		curr = curr->next;
	}
    ListNode* p = (ListNode*)malloc(sizeof(ListNode)); //헤드 노드 생성
    p->data = value;
    curr->next = p; p->next = NULL;
    // if(curr == NULL)printf("N U L L\n");
    return head;
}

ListNode* Insert(ListNode *head, ListNode *new){
    ListNode* curr = head->next; 
	while(curr->next != NULL){ //연결리스트 출력
        if((curr->next)->data > new->data){
            new->next = curr->next;
            curr->next = new;
            break;
        }
		// printf(">> %c\n", curr->data);
		curr = curr->next;
	}
    printf("연결리스트의 삽입 함수 실행 후 "); 
    Print(head);
    return head;
}

ListNode* Delete(ListNode *head, ListNode *del){
    ListNode* curr = head->next; 
	while(curr->next != NULL){ //연결리스트 출력
        // printf(">> %c\n", curr->data);
        if((curr->next)->data == del->data){
            // printf("<< %c | %c >>\n", curr->next->data,curr->next->next->data);
            curr->next = (curr->next)->next;
            break;
        }
		curr = curr->next;
	} //free(curr);
    
    ListNode* cnt = head->next; 
    printf("연결리스트의 삭제 함수 실행 후 "); 
	Print(head);
    return head;
}

int main(){
    /*노드를 메모리 동적 할당으로 생성하기*/
    ListNode* head = (ListNode*)malloc(sizeof(ListNode)); //헤드 노드 생성
    head->next = NULL;
    Initialize(head);

    /*순회용 노드*/
    ListNode* cnt = head->next;
    printf("[기본 연결리스트의 값] "); 
	while(cnt != NULL){ //연결리스트 출력
		printf("%c ", cnt->data);
		cnt = cnt->next;
	}printf("\n");

    ListNode* del = (ListNode*)malloc(sizeof(ListNode)); //node1 이라는 새로운 노드를 새로 할당
    del->data = 'C';
    Delete(head,del); free(del);

    ListNode* new = (ListNode*)malloc(sizeof(ListNode)); //node1 이라는 새로운 노드를 새로 할당
    new->data = 'C';
    Insert(head,new);
    free(head);
	return 0;
}