Written by nodejs-style
on 2021-08-19

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

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

예를 들어,

char arr[6] = "linked";

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

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

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

연습하기 1

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

#include 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

", h->value); }

* create_node

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

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

<결과>

head 노드 값 출력

연습하기 2

노드 2개를 연결하기

", 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++, h->value); if((h->next_node) == NULL){ break; //NULL이면 반복문 탈출 } h = h->next_node; //다음 노드에 값이 있을 때, 계속 연결 시켜줌. } }

#include #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

from http://yjchoi010517.tistory.com/47 by ccl(A) rewrite - 2021-08-19 17:59:59

Top