[자료구조]링크드리스트 삽입 삭제 (C언어)

단일 링크드 리스트에 의기본 구조를 꼭 알고 가자

typedef struct list {
    list *next;
    int val;
};

이것을 가지고 동적으로 메모리를 할당하고 '->'연산자를 이용하여 리스트를 형성할 수 있다.

그렇다면 이 list를 삽입, 삭제하는 코드를 보자

요정도 내용까지는 우리가 짚고 넘어갈 수 있으면 좋다. 코드를 보고 따라해보면서 눈과 머리 그리고 손으로 익히도록 하자.

#include<iostream>
#include<stdio.h>
#include<malloc.h>
#include<stdlib.h>
using namespace std;
 
typedef struct list {
    list *next;
    int val;
};
 
void display(list *head) {
    list *tmp = head;
    while (tmp != NULL) {
        printf("%d -> ", tmp->val);
        tmp = tmp->next;
    }
    printf("NULL");
}
 
void insert2(list *h, int find, int bal) {// 삽입 - 찾는 값 뒤에 삽입   h는 시작할 노드를 가져옴
    list *New = (list*)malloc(sizeof(list)); //삽입하기위한 노드 생성
    list *cur;
    cur = h;  //탐색을 진행할 현재노드
    New->val = bal; //새로 삽입할 노드는 bal값 가짐
    New->next = NULL;    
    while (cur->next != NULL) {
        cur = cur->next;
        if (cur->val == find) {
            New->next = cur->next;  //삽입할 노드는 현재 노드가 가리키는걸 가리킴
            cur->next = New;        //현재 노드는 삽입할 노드 가리킴
            break;
        }
                    //반복을 위함
    }
}
 
 
void insert(list *cur,int bal) {// 삽입 - 어떤노드앞에 새 노드 삽입
    list *New = (list*)malloc(sizeof(list)); //삽입할 노드 생성
 
    New->val = bal;
    New->next = cur->next; // 추가할 노드가 가리키는 것은 cur노드가 가리키고 있는것으로 대입
    cur->next = New;       // 현재 가리키고 있는것을 New 노드로 가리킴
}
 
 
 
void Delete(list *h, int find) {
    list *s;
    list *p = (list*)malloc(sizeof(list));
    p->val = 0;
    p->next = NULL;
    s = h;
    if (s == NULL) {
        printf("No\n");
        return;
    }
 
    while (s->next != NULL) {
        p = s;   //p노드를 탐색하기위한 s노드로 계속 생신
        s = s->next;
        if (s->val == find) {
            //메모리 해제시 꼭 free할 위치에 가서 지움
            //지우기전 지울 내용의 전링크에 내용 복사
            p->next = s->next;
            free(s);
            break;
        }
    }
}
 
int main()
{
    list* node = (list*)malloc(sizeof(list)); //------------------------------------------
    node->val = 100;
    node->next = NULL;
 
    list* node2 = (list*)malloc(sizeof(list));
    node2->val = 200;
    node2->next = node->next;
    node->next = node2;
 
    list* node3 = (list*)malloc(sizeof(list));
    node3->val = 300;
    node3->next = node2->next;
    node2->next = node3;
 
    list* node4 = (list*)malloc(sizeof(list));
    node4->val = 400;
    node4->next = node3->next;
    node3->next = node4;                      //---------노드 생성 및 연결-----------------
                                              //노드 생성을 함수로 만들어도 
 
 
    //list node10;         **메모리가 동적으로 생성되지 않았기때문에 free()에서 에러
    //node10.val = 1000000;
    //node10.next = node4->next;
    //node4->next = &node10;
 
    display(node);
    printf("\n");
 
    insert(node3,350);
    insert2(node,300, 1230);
 
    display(node);
    printf("\n");
 
 
    Delete(node, 200);
    Delete(node, 300);
    display(node);
    // 메모리를 할당했다면 언제나 해제시켜줘야한다!!!!
    // malloc 및 free함수를 호출하기 위해서는 Node를 동적메모리로 꼭 할당해야한다
    // ***list node 형태로 값을 넣으면 메모리 헤제에서 문제가 발생함***
    return 0;
}