본문 바로가기
C programming/[Algorithm problem]

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

old-cast1e 2023. 9. 6.
728x90
반응형

지난 포스팅에서는 add 함수를 이용해서 원하는 순서에 원하는 데이터를 저장하는 코드를 짜보았다.

코드는 정상적으로 작동했지만 현재 단일 연결리스트를 다루는 것에 비해 add 함수는 이중 연결리스트를 기준으로 작성된 코드라서 불필요한 요소가 존재했고 알고리즘이 다소 복잡했다. 이번 포스팅에서는 가장 간결하고 단순한 단일 연결리스트의 삽입 알고리즘을 짜보도록하자.

 

단일 연결리스트의 생성 로직은 다음과 같다.

  1. 단일 연결리스트의 구조체 선언
  2. 헤드 노드의 동적할당
  3. 기본 노드의 동적할당 및 데이터 저장
  4. 새로운 노드를 추가할 plus 함수/ insert 함수 작성
plus 함수 연결리스트의 요소와 관계 없이 가장 마지막에 삽입
insert 함수 특정 조건에 의해 새로운 노드를 특정 위치에 삽입

이때 plus 함수와  insert 함수의 차이점은 조건에 따라 노드를 삽입하는 위치의 유무이다. 따라서 insert 함수가 조금 더 복잡해진다.

plus 함수 작성

plus 함수의 로직은 다음과 같다.

1. 인자로 연결리스트의 헤드 노드와 추가할 데이터를 받는다.

2. 기존의 연결리스트 마지막 노드의 다음 노드를 동적할당하고 인자로 받은 데이터를 저장한다.

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

typedef char element;

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

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;
}

int main(){
    /*노드를 메모리 동적 할당으로 생성하기*/
    ListNode* head = (ListNode*)malloc(sizeof(ListNode)); //헤드 노드 생성
    head->next = NULL;
    
    ListNode* ListNode1 = (ListNode*)malloc(sizeof(ListNode)); //node1 이라는 새로운 노드를 새로 할당
    ListNode1->next = head->next;//node1의 꼬리를 (기존)헤드의 꼬리로 연결
    head->next = ListNode1;
    ListNode1->data = 'A';//node1의 데이터 업데이드

    ListNode* ListNode2 = (ListNode*)malloc(sizeof(ListNode)); //node1 이라는 새로운 노드를 새로 할당
    ListNode1->next = ListNode2;//node1의 꼬리를 (기존)헤드의 꼬리로 연결
    ListNode2->data = 'B';//node1의 데이터 업데이드

    ListNode* ListNode3 = (ListNode*)malloc(sizeof(ListNode)); //node1 이라는 새로운 노드를 새로 할당
    ListNode2->next =ListNode3;//node1의 꼬리를 (기존)헤드의 꼬리로 연결
    ListNode3->data = 'C';//node1의 데이터 업데이드

    Plus(head,'D');

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

    free(head);
	free(ListNode1);
	return 0;
}

먼저 연결리스트를 생성하고 각각 'A', 'B', 'C'를 저장한다. 이때 Plus 함수를 이용해 연결리스트의 마지막에 'D'라는 데이터를 추가한다. 이때 중요한 것은 순회용 노드를 마지막 데이터가 저장된 인덱스까지만 반복해야한다는 것이다. 일반적으로 순회용 노드는 NULL값을 가지는 노드에 최종적으로 머물기 때문에 마지막 값이 저장된 '실제' 노드까지 반복하고, 새로운 노드에 연결해야한다는 점을 주의하자.

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;
}

Insert 함수 작성

insert 함수의 로직은 다음과 같다.

  1. 인자로 추가할 노드를 받는다.
  2. 특정한 조건이 성립할 동안 순회 알고리즘을 통해 순회한다. 이때 조건은 입력받은 노드의 데이터가 확인한 노드의 다음 노드의 데이터보다 작을 때 종료한다.
  3. 새로운 노드를 동적할당하고 해당 노드와 연결한다. 
#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* ListNode1 = (ListNode*)malloc(sizeof(ListNode)); //node1 이라는 새로운 노드를 새로 할당
    ListNode1->next = head->next;//node1의 꼬리를 (기존)헤드의 꼬리로 연결
    head->next = ListNode1;
    ListNode1->data = 'A';//node1의 데이터 업데이드

    ListNode* ListNode2 = (ListNode*)malloc(sizeof(ListNode)); //node1 이라는 새로운 노드를 새로 할당
    ListNode1->next = ListNode2;//node1의 꼬리를 (기존)헤드의 꼬리로 연결
    ListNode2->data = 'B';//node1의 데이터 업데이드

    ListNode* ListNode3 = (ListNode*)malloc(sizeof(ListNode)); //node1 이라는 새로운 노드를 새로 할당
    ListNode2->next =ListNode3;//node1의 꼬리를 (기존)헤드의 꼬리로 연결
    ListNode3->data = 'D';//node1의 데이터 업데이드
}

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;
	}
    return head;
}

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

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

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

    free(head);
	return 0;
}

 

Insert 함수를 작성할 때 유의할 점으로는 비교의 조건이다.

연결리스트를 순회할 때 현재의 노드의 다음 노드의 데이터가 새로 추가할 노드의 데이터보다 큰 경우, 즉 알파벳 순서가 더 늦은 알파벳인 경우 반복을 종료하고 현재 노드 앞에 새로운 노드를 추가해야한다.

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;
	}
    return head;
}

Initailize는 기본 연결리스트를 생성하기 위한 함수로 가독성을 위해 따로 작성했다. 해당 코드는 연결리스트 배열을 이용해 좀 더 간결하게 표현할 수 있다.

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

코드

Plus 함수와 Insert 함수를 모두 정리한 코드는 다음과 같다.

#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[3];
    for(int i=0;i<3;i++) NodeArr[i] = (ListNode*)malloc(sizeof(ListNode));
   
    for(int i=0;i<3;i++){    
        if(i==0) head->next = NodeArr[0];
        else NodeArr[i-1]->next = NodeArr[i];//node1의 꼬리를 (기존)헤드의 꼬리로 연결
        NodeArr[i]->data = 'A'+ i;
        // if(i!=2)NodeArr[i]->data = 'A'+ i;
        // else  NodeArr[i]->data = 'A'+ i + 1;       
    }   
}
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;
	}
    return head;
}

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

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

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

    free(head);
	return 0;
}
728x90
반응형
저작자표시

'C programming > [Algorithm problem]' 카테고리의 다른 글

#2-4. 이중 연결 리스트의 생성  (0) 2023.09.07
#2-3. 연결 리스트의 삽입과 삭제(2) : 삭제  (0) 2023.09.07
#2-3. 연결 리스트의 삽입과 삭제: 이중 연결 리스트를 곁들인,,  (1) 2023.09.05
#2-2. 단일 연결 리스트의 생성  (0) 2023.09.04
#2-1. 연결 리스트  (0) 2023.09.04

'C programming/[Algorithm problem]' 관련글

댓글

티스토리툴바