All Articles

C로 자료구조 연결리스트(Linked List) 만들기(use Double Pointer)

자료구조 - 연결리스트에 대해 더블 포인터를 사용해알아보자!
Colin Park (Hong mae)2021년 9월 22일

연결리스트는 노드가 포인터를 가지고 한 줄로 연결되어 있는 방식으로 데이터를 저장하는 자료 구조이다. - 위키백과

여기서 노드는 데이터와 포인터 정보를 담는 공간, 포인터는 다음 노드와의 연결을 뜻한다. 여기서 연결이란 다음 노드의 메모리 주소를 저장한다는 의미이다.

linked_list_base.jpeg 연결 리스트

구조는 root 역할을 하는 노드를 기준으로 생성된다. root 노드를 여기서는 head라고 부르겠다.

이 글에서 더블 포인터를 이용하는 이유는 딱히 없다. 보통 전역 변수로 head를 선언하는데 나는 전역 변수 이용하는 걸 딱히 선호하지 않기 때문이다.

포인터

C언어에서 포인터(Pointer)는 메모리의 주소값을 의미한다. 해당 값을 저장하는 변수를 포인터 변수라고 하며 선언은 *을 통해 선언한다.

int형 포인터 변수는 int*, char형 포인터 변수는 char* 등…

int n = 100;
int* ptr = &n;

pinter.jpeg 포인터 형태

포인터 변수를 선언할때 두가지 방법으로 선언 할 수 있다. int* ptr(자료형 뒤에 *붙이기) 와 int *ptr(변수 명 앞에 *붙이기) 둘다 같은 의미를 가지지만 변수 명만으로 봤을 때 전자는 int형인지 int형 포인터 변수인지 모르기 때문에 후자를 많이 선택하지만 나는 전자를 많이 이용했기 때문에 전자를 사용했다.

더블 포인터(이중 포인터)

그렇면 포인터 변수도 메모리를 가지고 있는데, 포인터 변수를 가지고있는 포인터 변수는 없을까? 당연히 있다. 이를 더블 포인터(이중 포인터) 라고 부른다.

#include <stdio.h>
int main() {
int n = 100;
int* p = &n;
int** p2 = &p;
printf("n: %d, &n: %p\n", n, &n);
printf("p: %p, &p: %p *p: %d\n", p, &p, *p);
printf("p2: %p, &p2: %p *p2: %p, **p2: %d\n", p2, &p2, *p2, **p2);
return 0;
}
view raw double_pointer.c hosted with ❤ by GitHub

double_pointer.png 더블 포인터

주소를 출력할때는 %p를 사용하면 된다.

결과 사진을 분석해보자. 우선 4~6번째 줄을 확인하면 정수형 n을 100으로 초기화하고 포인터 p에 정수형 n의 주소값을, 더블 포인터 p2에는 포인터 p의 주소값을 선언했다.

double_pointer_img.jpeg

p의 값을 출력하면 n의 주소값이 나오고 p가 참조하는 값(*p)을 출력하면 n의 값인 100이 나온다. 이는 p는 n을 참조하고 있기 때문이다.

p2의 값을 출력하면 p의 주소값이 나오고 p2가 참조하는 값(*p2)을 출력하면 p의 값이 나오고 p2가 참조하는 값의 참조하는 값(**p2)을 출력하면 n의 값인 100이 나온다.

이를 토대로 간단하게 표현하자면 포인터는 주소값을 저장하고 이를 표현하기 위해서는 *를 붙히면 된다. 더블 포인터는 포인터를 참조하는 포인터이다.라고 표현할 수 있다. 근데 무슨 뜻인지 이해하기 어려울 수 있다.. 근데 더 쉽게 표현할 방법을 모르겠다.

노드 구조체 선언

노드를 구성하는 구조체는 다음과 같이 선언한다. 추가적인 정보가 있으면 더 넣어도 되지만 지금은 간단하게 작업할 예정이니 데이터는 int 자료형 하나만 선언한다.

typedef struct Node{
int value;
struct Node* next;
} Node;
view raw singly_linked_list.c hosted with ❤ by GitHub

새로운 노드 생성

새로운 노드는 생성은 다음과 같다. 동적 메모리 생성(malloc)을 통해 새로운 노드(cNode) 초기화하고 다음 노드(cNode -> Next)는 NULL로 초기화 한다.

초기값이 설정된 새로운 노드(cNode)의 포인터형을 반환하는 것으로 새로운 노드 생성은 끝난다.

참고로 구조체에서 내부 변수를 접근할 때에는 화살표 접근자 (->)를 이용하여 접근 할 수 있다.

Node* create_node () {
Node* cNode = (Node*)malloc(sizeof(Node));
cNode -> next = NULL;
return cNode;
}
view raw singly_linked_list.c hosted with ❤ by GitHub

기존 노드에 새로운 노드 연결하기

함수 인자로 헤드의 주소값을 받기 때문에 더블 포인터와 값을 받는다.

void insert_new_node_last (Node** node, int value) {
Node* new_node = create_node();
new_node -> value = value;
if(*node == NULL) {
*node = new_node;
} else {
Node* insert = *node;
while(insert -> next != NULL) {
insert = insert -> next;
}
insert -> next = new_node;
}
};
view raw singly_linked_list.c hosted with ❤ by GitHub

27번째 줄에서 새로운 노드를 생성하고, 28번째 줄에서 인자로 받은 값을 대입하여 새로운 노드를 완성시켰다.

30~31번째 줄에서 *node === NULL의 뜻은 헤드 노드가 있지만 NULL(아무것도 없는 값)이라면 새로운 노드를 헤드 노드로 적용한다.

33번째 줄에서 헤드 노드를 Node* insert로 따로 저장하는 이유는 마지막 노드에 연결하기 위해서는 노드를 계속 재선언해야하는데 이를 헤드 노드에 할 경우 이전 노드들이 사라진다. 이를 방지하기 위해 따로 저장한다.

35~37번째 줄은 마지막 노드에 새로운 노드를 연결해야하기 때문에 insert노드를 마지막 노드가 될때까지 반복해서 재선언한다.

38번째 줄에서는 마지막 노드인 insert에 다음 노드에 새로운 노드를 선언함으로 연결을 완료한다.

노드 전체 출력하기

void print_node (Node** node) {
Node* print = *node;
while(print != NULL) {
printf("%d -> ", print -> value);
print = print -> next;
}
printf("NULL\n");
}
view raw singly_linked_list.c hosted with ❤ by GitHub

10번째 줄에서 헤드 노드를 *print에 따로 저장후 출력한다. 위에서 말했듯이 헤드 노드의 변조를 막기 위해서이다.

12~15번째 줄에서는 print가 NULL이 될때까지 반복하고 노드의 값을 출력한다.

17번째 줄은 마지막 노드가 가르키는 다음 노드는 NULL이기 때문에 이를 표시하기 위해 만들었다. 굳이 필요없다

특정 노드 삭제하기

void delete_node (Node** node, int target) {
Node* prev;
Node* del = *node;
if(del != NULL && del -> value == target) {
*node = del -> next;
delete(del);
return;
}
while(del != NULL && del -> value != target) {
prev = del;
del = del -> next;
}
if(del == NULL) {
printf("Didn't have Node -> Value is %d\n\n", target);
}
else {
prev -> next = del -> next;
delete(del);
}
}
view raw singly_linked_list.c hosted with ❤ by GitHub

72~73번째 줄에서 이전 노드 정보를 저장하는 prev, 전체 노드를 저장하는 del을 선언한다.

75-79번째 줄에서 만약 삭제할 특정 노드가 헤드인 경우에는 헤드 노드를 다음 노드로 연결하고 헤드 노드 정보를 지운다(delete함수). 여기서 delete 함수는 동적 메모리로 정의된 변수를 메모리 해제를 해야한다. 안그러면 사용하지 않는 메모리가 계속 자리만 차지하고 있기 때문이다.

81~84번째 줄은 특정 노드가 될 때까지 반복해서 del을 다음 노드로 재선언한다. 그와 동시에 현재 del 정보(이전 노드)를 prev에 저장한다.

86~93번째 줄에서 만약 del이 NULL이라면 특정 노드가 없는 상태이므로 찾을 수 없다고 반환하고, 그게 아니라면 이전 노드의 다음(prev -> next)에 삭제 예정인 노드의 다음 노드(del -> next)를 연결한다. 그리고 del 노드는 delete!

번외 - 중간에 새로운 노드 넣기

노드 출력과 삭제를 통해 생각할 수 있는건 중간에 새로운 값을 넣을 수 도 있지 않을까? 라는 생각이 들었다.

void insert_new_node_middle (Node** node, int tValue, int iValue) {
Node* search = *node;
Node* next;
Node* new_node = create_node(); // create new node
new_node -> value = iValue;
while(search != NULL && search -> value != tValue) {
search = search -> next;
}
if(search == NULL) {
printf("NOT FOUND NODE VALUE IS %d\n\n", tValue);
return;
}
next = search -> next;
search -> next = new_node;
new_node -> next = next;
}
view raw singly_linked_list.c hosted with ❤ by GitHub

42번째 줄은 특정 노드 검색을 위해 헤드 노드를 *search에 따로 선언한다.

43번째 줄은 특정 노드의 다음 노드(search -> next)를 저장하기 위해 next를 선언한다.

44~45번째 줄은 새로운 노드(new_node)를 만들고 그 노드에 새로운 값(iValue)을 대입한다.

47~49번째 줄은 search 노드에 노드 값(search -> value)이 특정 값(tValue)이랑 같을 때까지 재선언한다.

51~54번째 줄은 만약 특정 값을 가지는 노드가 없을 경우 값이 없다고 반환한다.

55번째 줄은 특정 노드의 다음 노드(search -> next)를 따로 선언한 next 노드에 저장한다.

58~59번재 줄은 특정 노드의 다음 노드(search -> next)에 새로운 노드(newnode)를 연결하고, newnode에 따로 저장한 다음 노드(next)를 연결한다.

변경 - 헤드 노드 변경하기

이번엔 헤드 노드를 새롭게 연결해보자.

void insert_new_node_forward(Node** node, int value) {
Node* head = create_node();
head -> value = value;
head -> next = *node;
*node = head;
}
view raw singly_linked_list.c hosted with ❤ by GitHub

63~64번째 줄은 새로운 해드 노드가 될 head를 생성하고 새로운 값을 대입한다.

65번째 줄 새로운 헤드 노드의 다음을 현재 헤드 노드로 연결한다

67번째 줄에서 현재 헤드 노드를 새롭게 만든 헤드 노드로 재선언한다.

마치며

C언어를 배울때 많이 포기하는 부분인 포인터, 구조체를 이용해 선형 연결리스트를 만들어 봤다. 이 이외에 원형, 이중, 이중 원형 리스트가 있다.

이는 선형 연결리스트 마지막 노드를 헤드 노드로 연결하면 원형 연결리스트, 노드에 이전 노드 정보까지 같이 저장하면 이중 연결리스트, 헤드 노드의 이전 노드에 마지막 노드를, 마지막 노드에 다음 노드를 헤드 노드에 연결하면 이중 원형 연결리스트가 된다.

이번 포스트를 제대로 이해했다면 방금 설명을 바탕으로 금방 코딩할 수 있을 것이다.

전체 코드

#include <stdio.h>
#include <stdlib.h>
typedef struct Node{
int value;
struct Node* next;
} Node;
void print_node (Node** node) {
Node* print = *node;
while(print != NULL) {
printf("%d -> ", print -> value);
print = print -> next;
}
printf("NULL\n");
}
Node* create_node () {
Node* cNode = (Node*)malloc(sizeof(Node));
cNode -> next = NULL;
return cNode;
}
void insert_new_node_last (Node** node, int value) {
Node* new_node = create_node();
new_node -> value = value;
if(*node == NULL) {
*node = new_node;
} else {
Node* insert = *node;
while(insert -> next != NULL) {
insert = insert -> next;
}
insert -> next = new_node;
}
};
void insert_new_node_middle (Node** node, int tValue, int iValue) {
Node* search = *node;
Node* next;
Node* new_node = create_node(); // create new node
new_node -> value = iValue;
while(search != NULL && search -> value != tValue) {
search = search -> next;
}
if(search == NULL) {
printf("NOT FOUND NODE VALUE IS %d\n\n", tValue);
return;
}
next = search -> next;
search -> next = new_node;
new_node -> next = next;
}
void insert_new_node_forward(Node** node, int value) {
Node* head = create_node();
head -> value = value;
head -> next = *node;
*node = head;
}
void delete_node (Node** node, int target) {
Node* prev;
Node* del = *node;
if(del != NULL && del -> value == target) {
*node = del -> next;
delete(del);
return;
}
while(del != NULL && del -> value != target) {
prev = del;
del = del -> next;
}
if(del == NULL) {
printf("Didn't have Node -> Value is %d\n\n", target);
}
else {
prev -> next = del -> next;
delete(del);
}
}
int main() {
Node* head = NULL;
printf("새로운 노드 생성...\n\n");
insert_new_node_last(&head, 1);
insert_new_node_last(&head, 2);
insert_new_node_last(&head, 3);
insert_new_node_last(&head, 4);
insert_new_node_last(&head, 5);
print_node(&head);
printf("\n");
printf("헤드 노드 삭제...\n\n");
delete_node(&head, 1);
printf("마지막 노드 삭제...\n\n");
delete_node(&head, 5);
printf("중간 노드 삭제(Node -> Value === 3)...\n\n");
delete_node(&head, 3);
print_node(&head);
printf("\n");
printf("값이 2인 노드에 값이 3인 새로운 노드 연결\n\n");
insert_new_node_middle(&head, 3, 2);
printf("값이 3인 노드에 값이 2인 새로운 노드 연결\n\n");
insert_new_node_middle(&head, 2, 3);
printf("값이 4인 노드에 값이 5인 새로운 노드 연결\n\n");
insert_new_node_middle(&head, 4, 5);
print_node(&head);
printf("\n");
printf("헤드 노드 앞에 값이 1인 새로운 노드 연결\n\n");
insert_new_node_forward(&head, 1);
print_node(&head);
printf("\n");
return 0;
}
view raw singly_linked_list.c hosted with ❤ by GitHub

singly_linked_list.png

출처 및 참조

Published Sep 22, 2021

Nothing great was ever achieved without enthusiasm. - 랠프 월도 에머슨Colin Park (Hong mae) on Github