[자료구조 - C언어] Linked List

Array대신 Linked List를 사용하는 이유는 무엇일까?

예를 들어,

char arr[6] = "linked";

이런 배열이 있다고 하자. 0~5까지의 배열 칸에 알파벳이 하나씩 들어가 있을 것이다.

여기서 'n'을 삭제하려면 'n' 삭제하고 뒤에 있는 나머지 배열 칸의 값들을 전부 복사하여 한 칸씩 앞에 넣어 줘야 한다.

이렇게 배열 인덱스를 바꿔 주는 것은 번거롭고 복잡하기 때문에 "링크드 리스트(Linked List)"를 사용하여 추가, 삭제 등 각 노드의 수정을 용이하게 한다. 

 

연습하기 1

헤드 노드 하나만 생성하여 값을 넣고 다음 노드에는 NULL로 설정하기

<link.h>

#include <stdlib.h>

typedef struct node {
    char value;
    struct node *next_node;
}NODE;

NODE *create_node(char v){
    NODE *mynode;
    mynode = (NODE*)malloc(sizeof(NODE)*1);
    mynode->value = v;
    mynode->next_node = NULL;
    
    return mynode;
}

void print_node(NODE *h){
    printf("value : %c\n", h->value);
}

 

* create_node 

1. struct 멤버 변수를 사용하기 위해 create_node 함수에 'mynode'를 선언한다. 
2. struct 멤버 변수에 값을 넣기 위해 malloc을 통해 동적메모리 할당 받는다.
3. heap영역에 메모리가 할달 되고, 멤버 변수에 값을 넣을 수 있게 된다.
4. mynode를 포인터 변수로 선언하였기 때문에 'mynode->value = v', 'mynode->next_node = NULL' 이렇게 값을 받는다. 
5. 리턴타입이 void가 아니므로 mynode를 리턴해줘야 입력된 값이 전달된다.

 

<main.c>

#include <stdio.h>
#include "link.h"

int main(int argc, char *argv[]){
	struct node *head;
    
    head = create_node('l');
    print_node(head);
    
	return 0;
}

 

<결과>

head 노드 값 출력

 

 

연습하기 2

노드 2개를 연결하기 

<link.h>

#include <stdlib.h>

typedef struct node {
    char value;
    struct node *next_node;
}NODE;

NODE *create_node(char v){
    NODE *mynode;
    mynode = (NODE*)malloc(sizeof(NODE)*1);
    mynode->value = v;
    mynode->next_node = NULL;
    
    return mynode;
}

void print_node(NODE *h){
    printf("value : %c\n", h->value);
}

void append_node(NODE *h, NODE *n){
    h->next_node = n;
    //헤드 노드를 다음 노드로 지정하여 다음 노드에 저장될 값을 받는다. 
}

void print(NODE *h){
    int n = 1;
    //다음 노드가 NULL이 아닐때만 노드의 값을 계속 출력 
    for(int i = n; i <= n; i++){
    	printf("node%d : %c\n", n++, h->value);
        if((h->next_node) == NULL){
        	break;  //NULL이면 반복문 탈출
        }
        h = h->next_node;  //다음 노드에 값이 있을 때, 계속 연결 시켜줌.
    }
}

 

<main.c>

#include <stdio.h>
#include "link.h"

int main(int argc, char *argv[]){
	struct node *head;
    struct node *next;
    
    head = create_node('l');
    print_node(head);
    
    next = create_node('i');
    append_node(head, next);
    print(head);
    
	return 0;
}

 

<결과>

head 노드, next 노드(연결된 노드) 값 출력

 

 

노드의 연결을 코드로 표현하는게 이렇게 어려운지 오늘 알게되었습니다...ㅠㅠ

감사합니다!

 

2021.08.19