#2-3. 연결 리스트의 삽입과 삭제: 이중 연결 리스트를 곁들인,,

이전 포스팅에서는 연결리스트의 생성을 알아보았다.

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

#2-2. 단일 연결 리스트의 생성

해당 포스팅에서는 연결리스트의 생성과정을 다시 복습하고 연결리스트의 삽입과 삭제함수에 대해 알아보자.

연결리스트의 생성

연결리스트 생성의 순서는 다음과 같다.

1. 연결리스트의 구조체 선언: 인자로는 데이터 값을 저장할 변수, 다음 노드의 구조체 포인터를 가진다.(단일 연결리스트)
2. 메인 함수에서 연결리스트 구조체를 참조하여 헤드 노드 생성
3. 새로운 노드를 생성하고 값을 저장. 이후 앞과 뒤 노드를 연결

1. 연결리스트의 구조체 선언

typedef int element;

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

2/3. 헤드 노드 생성

ListNode* head = (ListNode*)malloc(sizeof(ListNode)); //헤드 노드 생성
head->next = NULL;
ListNode* ListNode1 = (ListNode*)malloc(sizeof(ListNode)); //node1 이라는 새로운 노드를 새로 할당

• 1번째 줄: 연결리스트 구조체 자료형을 가진 head 변수를 선언하고 해당 변수에 ListNode* 자료형이며 메모리의 크기가 ListNode로 초기화한다.
• 헤드 노드의 다음 값을 null로 초기화한다. 이는 아직 새로운 노드를 연결하기 전 오류를 방지하기 위함이다.
• 헤드 노드를 생성할 때와 마찬가지로 동적할당을 통해 연결리스트를 저장할 구조체와 같은 크기로 노드를 생성한다.

연결리스트의 삽입

연결리스트의 삽입 알고리즘은 다음과 같다. 이전 포스팅에서 다룬 insert는 이 포스팅의 add와 의미가 다르다.

이때 아래의 알고리즘은 이중 연결리스트가 가능하도록 각 노드의 앞과 뒤의 방향을 선언했다.

• 해당 노드의 앞을 지칭하는 next
• 해당 노드의 뒤를 지칭하는 pre

/*cord 3-4*/
#include  <stdio.h>
#include  <string.h>
#include  <stdlib.h>

typedef int element;

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

ListNode* add(ListNode *head, int rank, int value){//구조체 함수
    /*list의 순위 r에 원소 e를 추가해야함으로 순위r까지 반복한 후 해당 위치에 원소 e를 추가하도록한다.*/
    int cnt = 0;
    ListNode* check = head->next; //순회용 노드 생성
    while(check != NULL){
	    cnt ++;
	    check = check->next;
    }free(check);

    printf("cnt = %d\n",cnt);

    if(cnt < rank) {printf("invalid position");return 0;}
    else{
        ListNode* curr = head; //순회용 노드 생성
        for(int i=0;i<rank;i++) curr = curr->next;
        //위 반복문을  통해 이미 순위가 r인 노드까지 이동함.(ㄱ)
        ListNode *p =(ListNode *)malloc(sizeof(ListNode));//추가할 노드를 동적할당한다.

        p->data = value;
        (curr->pre)->next = p;
        p->next = curr;
       
        printf("랭크 %d의 추가된 노드의 데이터는 %d입니다.\n",rank,p->data);
        // return head; //다음 노드의 위치를 반환함.
    }
    
    return head;
}

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

    ListNode* NewNode[100];
    for(int i=0;i<100;i++) NewNode[i] = (ListNode*)malloc(sizeof(ListNode));
    head->next = NewNode[0];
    // NewNode[0] ->data = 10;//node1의 데이터 업데이드

    for(int i=0;i<9;i++) NewNode[i]->next = NewNode[i+1];
    for(int i=1;i<9;i++) NewNode[i+1]->pre = NewNode[i];
    for(int i=0;i<10;i++) NewNode[i]->data = (i+1);
    NewNode[9]->next = NULL;
   
    add(head,5,150);

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

    free(head);
	return 0;
}

코드 설명: main()

사실 위의 코드는 단일 연결리스트가 아니라 각각의 노드의 앞과 뒤의 노드가 선언돼 있는 이중 연결리스트이다.

필자는 이전에 사용한 연결리스트의 함수를 그대로 가져와 add 함수가 작동하기 위해서는 이중 연결리스트의 개념과 next, pre 구조체 변수가 필요했다.

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

그렇기 때문에 위 코드에서 볼 수 있듯, 이중 연결리스트를 단일 연결리스트의 추가함수로 사용하기 위해 연결리스트 구조체 변수를 배열로 선언하고 각각을 동적할당 및 저장된 값을 초기화했다.

 

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

ListNode* NewNode[100];
for(int i=0;i<100;i++) NewNode[i] = (ListNode*)malloc(sizeof(ListNode));
head->next = NewNode[0];
// NewNode[0] ->data = 10;//node1의 데이터 업데이드

for(int i=0;i<9;i++) NewNode[i]->next = NewNode[i+1];
for(int i=1;i<9;i++) NewNode[i+1]->pre = NewNode[i];
NewNode[0]->pre = head;

for(int i=0;i<10;i++) NewNode[i]->data = (i+1);
NewNode[9]->next = NULL;

add 함수를 사용하기 위해서는 먼저 헤드 노드를 생성했다.

 

이때 선언한 연결리스트 구조체를 보면 100개를 선언했고 각각을 동적할당했다. 이때 해당 코드에서 사용하는 공간은 10개로, 먼저 헤드 노드와 1번째 (0번째 인덱스)를 연결했다.

 

이후로 코드를 보면, 먼저 각각의 노드의 다음 노드를 선언했다. 이때 우리는 10개의 노드만 사용하므로 반복은 9번을 사용한다. 10번째 (9번째 인덱스)는 연결리스트의 마지막으로 사용할 것이므로 나중에 NULL값을 선언한다.

마찬가지로 각각의 노드의 이전 노드를 선언한다. 이때 주의할 점으로 첫 번째 노드의 이전 노드는 헤드 노드이므로 따로 정의한다.

 

마지막으로 각각의 노드에 데이터를 저장한다. 이후 마지막 노드의 다음 노드를 NULL로 선언한다.

add(head,5,150);

• 5번째 순서에 150을 저장하는 노드를 추가한다.

코드 설명: add()

ListNode* add(ListNode *head, int rank, int value){//구조체 함수
    /*list의 순위 r에 원소 e를 추가해야함으로 순위r까지 반복한 후 해당 위치에 원소 e를 추가하도록한다.*/
    int cnt = 0;
    ListNode* check = head->next; //순회용 노드 생성
    while(check != NULL){
	    cnt ++;
	    check = check->next;
    }free(check);

    printf("cnt = %d\n",cnt);

    if(cnt < rank) {printf("invalid position");return 0;}
    else{
        ListNode* curr = head; //순회용 노드 생성
        for(int i=0;i<rank;i++) curr = curr->next;
        //위 반복문을  통해 이미 순위가 r인 노드까지 이동함.(ㄱ)
        ListNode *p =(ListNode *)malloc(sizeof(ListNode));//추가할 노드를 동적할당한다.

        p->data = value;
        (curr->pre)->next = p;
        p->next = curr;
       
        printf("랭크 %d의 추가된 노드의 데이터는 %d입니다.\n",rank,p->data);
        // return head; //다음 노드의 위치를 반환함.
    }
    
    return head;
}

자세한 해석

int cnt = 0;
ListNode* check = head->next; //순회용 노드 생성
    while(check != NULL){
        cnt ++;
        check = check->next;
    }free(check);

printf("cnt = %d\n",cnt);

• 해당 로직은 인자로 받은 연결리스트의 노드 개수를 cnt에 저장하는 로직이다.
• cnt의 값은 나중에 rank의 오류를 판단하는 데 사용된다.

if(cnt < rank) {printf("invalid position");return 0;}
    else{ ... 생략

• cnt의 값이 rank보다 크다는 것은 추가할 대상의 순서가 연결리스트가 전체 노드 수보다 많다는 것을 의미하므로, 잘못된 입력이라는 것을 출력하고 0을 반환한다.
• 다시 말해 사용자의 잘못된 입력을 방지하는 로직이다.

...생략

ListNode* curr = head; //순회용 노드 생성
for(int i=0;i<rank;i++) curr = curr->next;
//위 반복문을  통해 이미 순위가 r인 노드까지 이동함.(ㄱ)
ListNode *p =(ListNode *)malloc(sizeof(ListNode));//추가할 노드를 동적할당한다.

p->data = value;
(curr->pre)->next = p;
p->next = curr;

printf("랭크 %d의 추가된 노드의 데이터는 %d입니다.\n",rank,p->data);
// return head; //다음 노드의 위치를 반환함.

• 새로운 순회용 노드를 생성하고 인자로 받은 노드의 추가를 원하는 노드로 이동한다.
• 이동이 끝났다면 값을 저장하고 노드를 연결하기 위해 임의의 노드 p를 생성한다.
• 임의의 노드를 생성했다면 노드를 이어 붙인다.

이번 포스팅에서 다룬 알고리즘은 사실 이전에 필자가 작성한 알고리즘을 토대로 수정하려 하다 보니 더 조건이 많고 복잡한 알고리즘을 수행하기 위해서 사용한 변수와 확인 알고리즘이 필요했기에 복잡한 알고리즘을 사용했고, 이를 유지하기 위해서 복잡한 로직을 사용했다.

 

다음 포스팅에서는 이러한 단점을 해결하고 단일 연결리스트의 삽입과 삭제에 대해 배워보자.