(C언어)14.링크드리스트(연결리스트)

<링크드리스트>

배열은 메모리에 값을 연속적으로 저장한다. 그래서 중간에 값을 삭제하거나 추가하려면 변할 값을 기준으로 뒤로 쭉 밀거나 앞으로 쭉 당겨야 한다.

하지만 링크드리스트를 아는 순간부터 "노드"를 이용해서 값을 추가하거나 삭제하는것을 아주 쉽게 할 수 있을것이다.

링크드리스트는 자료구조의 입문이다. 그렇다. 본격적으로 메모리를 다룬다.

대충 이런식이다.

1. 추가하기

<1: 새로운 노드 생성

<2: 새로운 노드의 다음 주소값이 다음 값을 가리키게 함.

<3: 원래 다음 값을 가리켰던 "전 노드"의 다음 주소값을 새로운 노드의 값을 가리키게 함

2. 삭제하기

<1: 삭제할 노드 선택

<2: 삭제할 노드의 값을 가리키고 있던 "전 노드"의 다음 주소값이 원래 삭제할 노드의 다음 주소값이 가리키고 있던 다음 값을 가리키게 함

<3: 삭제할 노드의 동적할당을 free를 이용해서 풀어줌.

3. 출력하기

<0: 출력을 위한 임시 노드 생성

<1: 제일 첫번째(헤드) 노드를 출력, 임시노드=첫번째 노드

<2: 노드의 다음 값을 가리키는 주소를 이용해 다음 값 찾아감

<3: 값 출력

<4: 임시노드가 NULL이 되면 출력을 종료

구현 : 

#include <stdio.h>
#include <stdlib.h>
 
typedef struct _node{
    int i;//노드의 구성요소 첫번째. 값
    struct _node *nextadd;//노드의 구성요소 두번째. 다음 값을 가리키는 주소
}NODE;
 
NODE *firstnode=NULL;//첫번째 노드
NODE *lastnode=NULL;//마지막 노드
 
void add(int num){//맨 뒤에 추가함
    NODE *newnode=(NODE *)malloc(sizeof(NODE));//먼저 생성하고 보자
    newnode->i=num;
    newnode->nextadd=NULL;
    if(firstnode==NULL){//처음으로 이 함수가 실행되면
        firstnode=newnode;
        lastnode=newnode;
    }
    else{//처음이 아니면 뒤에 계속 추가. lastnode가 계속 바뀐다
        lastnode->nextadd=newnode;//원래 lastnode가 가리키는 곳이 새로 생성된 노드의 값을 가리키게 한 후,
        lastnode=newnode;//방금 생성한 노드가 맨 끝자리에 추가했으므로 방금 생성한 노드가 lastnode가 된다.
    }
}
 
void erase(int num){
    NODE *temp=firstnode->nextadd;
    if(firstnode==NULL){
        printf("값이 없는데 지울수 있을까요? => 지울수 없습니다.\n");
        return;
    }
    if(firstnode->i==num){//첫번째 노드의 값==입력값
        
        firstnode=firstnode->nextadd;
        free(temp);
    }
    else{
        NODE *before=firstnode;
        while(1){
            if(temp->i==num){
                NODE *node_free=temp;
                before->nextadd=temp->nextadd;
                free(node_free);
                break;
            }
            else{
                if(temp->nextadd==NULL){
                    printf("값이 없는데요? 이게 어터케 된 일이죠? 네?\n");
                    break;
                }
                before=before->nextadd;
                temp=temp->nextadd;
            }
        }
    }
    return;
}
 
void show(){
    int i;
    if(firstnode==NULL){
        printf("값이 없어용\n");
        return;
    }
    else{
        NODE *temp=firstnode;
        for(i=1; temp!=NULL; ++i){
            printf("%d번째 값 : %d\n", i, temp->i);
            temp=temp->nextadd;
        }
    }
}
 
int main(){
    int select, i, input, input_num;
    while(1){
        printf("\n\n0 : 종료\n");
        printf("1 : 노드 생성\n");
        printf("2 : 노드 삭제\n");
        printf("3 : 노드 보기\n");
        printf("0~3 선택 : ");
        scanf("%d", &select);
 
        if(select==0){
            return 0;
        }
        else if(select==1){
            printf("몇개 생성? : ");
            scanf("%d", &input);
            for(i=1; i<=input; ++i){
                printf("%d번째 생성중입니다....\n값을 입력해주세요 : ", i);
                scanf("%d", &input_num);
                add(input_num);
            }
        }
        else if(select==2){
            printf("몇개 삭제? : ");
            scanf("%d", &input);
            for(i=1; i<=input; ++i){
                printf("%d번째 삭제중입니다....\n지울 값을 입력해주세요 : ", i);
                scanf("%d", &input_num);
                erase(input_num);
            }
        }
        else if(select==3){
            show();
        }
    }
}

링크드리스트를 이용한 예제 : 전화번호부 구현

add(~)는 전화번호부 뒤쪽에 순서대로 추가, insert(~)는 전화번호부 중간에 삽입.

//linked_list_namecard
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
 
typedef struct namecard{
    char name[10];
    char phoneNumber[12];
    int callCount;
    struct namecard *next;
}NAMECARD;
 
NAMECARD *firstnamecard=NULL;
NAMECARD *lastnamecard=NULL;
 
void add(char name[], char phoneNumber[], int callCount){
    NAMECARD *newnode=(NAMECARD *)malloc(sizeof(NAMECARD));
    if(firstnamecard==NULL){
        strcpy(newnode->name, name);
        strcpy(newnode->phoneNumber, phoneNumber);
        newnode->callCount=callCount;
        newnode->next=lastnamecard;
        firstnamecard=newnode;
        lastnamecard=newnode;
    }
    else{
        lastnamecard->next=newnode;
        strcpy(newnode->name, name);
        strcpy(newnode->phoneNumber, phoneNumber);
        newnode->callCount=callCount;
        newnode->next=NULL;
        lastnamecard=newnode;
    }
}
 
void insert(char name[], char phoneNumber[], int callCount, int index){
    int i;
    NAMECARD *newnode=(NAMECARD *)malloc(sizeof(NAMECARD));
    NAMECARD *temp;
    if(index==1){
        strcpy(newnode->name, name);
        strcpy(newnode->phoneNumber, phoneNumber);
        newnode->callCount=callCount;
        newnode->next=firstnamecard->next;
        firstnamecard->next=newnode;
 
    }
    else{
        for(i=1; i<index; ++i){
            temp=temp->next;
        }
        strcpy(newnode->name, name);
        strcpy(newnode->phoneNumber, phoneNumber);
        newnode->callCount=callCount;
        newnode->next=temp->next;
        temp->next=newnode;
    }
}
 
void delete(char name[]){
    int i;
    NAMECARD *temp;
    NAMECARD *prev;
    temp=firstnamecard;
    if(strcmp(temp->name,name)==0){
        firstnamecard=temp->next;
        free(temp);
    }
    else{
        for(i=0; strcmp(temp->name, name)!=0; ++i){
            if(i==1){
                prev=firstnamecard;
            }
            temp=temp->next;
            if(i!=0){
                prev=prev->next;
            }
        }
        prev->next=temp->next;
        free(temp);
    }
}
 
void show(){
    int i;
    if(firstnamecard==NULL){
        printf("값이 없어용\n");
        return;
    }
    else{
        NAMECARD *temp=firstnamecard;
        for(i=1; temp!=NULL; ++i){
            printf("%d번째 :\n", i);
            printf("\t이름 : %s\n", temp->name);
            printf("\t전화번호 : %s\n", temp->phoneNumber);
            printf("\t전화횟수 : %d\n\n", temp->callCount);
            temp=temp->next;
        }
    }
}
 
void call(){
    int i, input;
    NAMECARD *temp;
    temp=firstnamecard;
    printf("\n\n다음은 전화번호부입니다.\n\n");
    show();
    fflush(stdin);
    printf("몇번에 전화하실껍니까? : ");
    scanf("%d", &input);
    for(i=1; i<input; ++i){
        temp=temp->next;
    }
    if(temp==NULL){
        printf("\n없습니다\n");
        return;
    }
    printf("\n이름 : %s, 전화번호 : %s에게 전화했습니다.\n", temp->name, temp->phoneNumber);
    temp->callCount=temp->callCount+1;
}
 
 
 
int main(){
    int input;
    char input_name[10];
    char input_phonenumber[12];
    int input_callcount;
    int input_insert;
    printf("NAMECARD!!~\n\n\n\n");
    while(1){
        printf("0 : exit\n");
        printf("1 : add\n");
        printf("2 : insert\n");
        printf("3 : delete\n");
        printf("4 : search and call\n");
        printf("5 : show\n");
        printf("choose : 0~5 : ");
        scanf("%d", &input);
        if(input==0){
            return 0;
        }
        else if(input==1){
            printf("name : ");
            scanf("%s", input_name);
            printf("phoneNumber : ");
            scanf("%s", input_phonenumber);
            input_callcount=0;
            add(input_name, input_phonenumber, input_callcount);
        }
        else if(input==2){
            printf("몇번 뒤에 추가? : ");
            scanf("%d", &input_insert);
            printf("name : ");
            scanf("%s", input_name);
            printf("phoneNumber : ");
            scanf("%s", input_phonenumber);
            input_callcount=0;
            insert(input_name, input_phonenumber, input_callcount, input_insert);
        }
        else if(input==3){
            printf("지울 이름 입력 : ");
            scanf("%s", input_name);
            delete(input_name);
        }
        else if(input==4){
            call();
        }
        else if(input==5){
            show();
        }
    }
    return 0;
}