들어가기 전에
지난 강의에서 연결 리스트의 정의와 리스트의 기본 단위가 되는 구조체를 정의하는 방법을 배웠습니다. 이번 강의에서는 이 구조체를 이용하여 실제로 연결 리스트를 구현하고 사용해보도록 하겠습니다.
학습 목표
연결 리스트를 구현하고 사용할 수 있습니다.
핵심 단어
- 연결 리스트
강의 듣기
4) 연결 리스트: 코딩
앞서 정의한 구조체를 활용해서 실제로 연결 리스트를 구현해보도록 하겠습니다.
아래 코드의 내용과 각 주석을 따라가 보세요.
#include <stdio.h>
#include <stdlib.h>
//연결 리스트의 기본 단위가 되는 node 구조체를 정의합니다.
typedef struct node
{
//node 안에서 정수형 값이 저장되는 변수를 name으로 지정합니다.
int number;
//다음 node의 주소를 가리키는 포인터를 *next로 지정합니다.
struct node *next;
}
node;
int main(void)
{
// list라는 이름의 node 포인터를 정의합니다. 연결 리스트의 가장 첫 번째 node를 가리킬 것입니다.
// 이 포인터는 현재 아무 것도 가리키고 있지 않기 때문에 NULL 로 초기화합니다.
node *list = NULL;
// 새로운 node를 위해 메모리를 할당하고 포인터 *n으로 가리킵니다.
node *n = malloc(sizeof(node));
if (n == NULL)
{
return 1;
}
// n의 number 필드에 1의 값을 저장합니다. “n->number”는 “(*n).numer”와 동일한 의미입니다.
// 즉, n이 가리키는 node의 number 필드를 의미하는 것입니다.
// 간단하게 화살표 표시 ‘->’로 쓸 수 있습니다. n의 number의 값을 1로 저장합니다.
n->number = 1;
// n 다음에 정의된 node가 없으므로 NULL로 초기화합니다.
n->next = NULL;
// 이제 첫번째 node를 정의했기 떄문에 list 포인터를 n 포인터로 바꿔 줍니다.
list = n;
// 이제 list에 다른 node를 더 연결하기 위해 n에 새로운 메모리를 다시 할당합니다.
n = malloc(sizeof(node));
if (n == NULL)
{
return 1;
}
// n의 number와 next의 값을 각각 저장합니다.
n->number = 2;
n->next = NULL;
// list가 가리키는 것은 첫 번째 node입니다.
//이 node의 다음 node를 n 포인터로 지정합니다.
list->next = n;
// 다시 한 번 n 포인터에 새로운 메모리를 할당하고 number과 next의 값을 저장합니다.
n = malloc(sizeof(node));
if (n == NULL)
{
return 1;
}
n->number = 3;
n->next = NULL;
// 현재 list는 첫번째 node를 가리키고, 이는 두번째 node와 연결되어 있습니다.
// 따라서 세 번째 node를 더 연결하기 위해 첫 번째 node (list)의
// 다음 node(list->next)의 다음 node(list->next->next)를 n 포인터로 지정합니다.
list->next->next = n;
// 이제 list에 연결된 node를 처음부터 방문하면서 각 number 값을 출력합니다.
// 마지막 node의 next에는 NULL이 저장되어 있을 것이기 때문에 이 것이 for 루프의 종료 조건이 됩니다.
for (node *tmp = list; tmp != NULL; tmp = tmp->next)
{
printf("%i\n", tmp->number);
}
// 메모리를 해제해주기 위해 list에 연결된 node들을 처음부터 방문하면서 free 해줍니다.
while (list != NULL)
{
node *tmp = list->next;
free(list);
list = tmp;
}
}
생각해보기
연결 리스트의 중간에 node를 추가하거나 삭제하는 코드는 어떻게 작성할 수 있을까요?
comment
- list = n;
현재 포인터 n이 가리키고 있는 메모리 공간을 포인터 list가 가리키게 됩니다.
- n = malloc(sizeof(node));
포인터 n이 현재 가리키고 있는 메모리 공간을 가리키는 것을 멈추고 새로운 메모리 공간(구조체 node)을 만들어 가리킵니다.
- list->next->next = n;
마지막 노드는 포인터 n과 list가 같은 메모리 공간을 가리키는 형태가 됩니다. malloc()으로 포인터 n의 메모리 공간을 새로 설정하지 않았기 때문입니다. 그래서 마지막 for문에서 free(list)를 하게되면 포인터 list가 가리키는 메모리 공간과 포인터 n이 가리키는 메모리 공간이 같기 때문에 메모리 공간이 해제되어 포인터 list와 n은 해제된 메모리 공간을 가리키 됩니다.
- 해제된 메모리 공간을 가리키는 포인터를 댕글링 포인터(dangling pointer) 라고 합니다. 그래서 메모리를 해제한 포인터는 null을 할당합시다.
임시적으로 연결이 끊어지지 않게 중복 연결 후 재배열 -> 임시 연결 해제
중간에 node를 삽입하거나 삭제하는 경우, 연결되어있는 포인터의 연결이 끊어지지 않게 임시적으로 중복연결을 유지한 후 연결을 다시 변경해 줍니다.
추가
: 추가 노드 앞의 노드가 가리키는 노드 주소값을 추가 노드가 가리키게 설정
-> 추가 노드 앞의 노드가 가리키는 노드 주소값이 추가 노드 주소값을 가리키게 설정
삭제
: 삭제 예정 노드 앞의 노드가 가리키는 노드 주소값이 삭제 예정 노드가 가리키는 주소값을 가리키게 설정
-> 삭제 예정 노드 삭제
이해가 안 돼서 다른 블로그도 보고 있는데
왜 node *list나 node *next를 node* list나 node* next라고 표기하는 걸까요?
*표기를 node 뒤에 표기하는 의미가 무엇인지 궁금해요.
node 뒤에 나오는 단어의 주소를 가리키는 뜻인가요?
너무 헷갈린다ㅠ 다들 어떻게 이해하는 거임?
1. 추가 하려는 노드가 현재 노드가 가르키는 노드를 주소를 가르키도록 설정 한 뒤 현재 노드는 추가한 노드의 주소를 가르키도록 변경한다.
2. 삭제 하려는 노드의 이전 노드는 삭제 하려는 노드의 다음 주소를 가르키도록 수정 한 후 삭제 하려는 노드를 삭제한다.
node를 추가하거나 삭제할 때 항상 다음 연결을 끊지 않도록 주의해야 한다. 예를 들어 node를 추가할 때는 num을 저장 후 그다음 이어질 next를 수정하고, 그 다음 앞에 올 메모리가 새로 만든 node를 가리키도록 해야 한다.
추가: 추가하려고 하는 위치 이전 위치가 현재 노드라고 할때 추가할 노드가 현재 노드의 다음 노드를 가르키게하고 현재 노드는 추가 노드를 가르키게 한다.
삭제: 삭제하려는 노드 이전의 위치가 현재 노드라고 하면 현재 노드의 다음 노드(삭제할 노드)를 임시 노드 포인터가 가르키게 하고, 현재 노드는 기존 현재 노드의 다음 다음 노드(삭제 노드의 다음 노드)를 가르키게 한다. 그리고 삭제하는 노드의 메모리 누수를 방지하기 위해 임시 노드 포인터에 담아둔 노드의 메모리를 해제시켜준다.
삽입: 삽입할 위치 양쪽 node의 포인터를 p와 q, 새로 할당한 node를 new라 하면, p->next = new; new->next = q;
삭제: 삭제할 위치 양쪽 node의 포인터를 p, q, r이라 하면 p->next = r; free(q);
1. 중간에 node 추가
#include <stdio.h>
#include <stdlib.h>
//연결 리스트의 기본 단위가 되는 node 구조체를 정의합니다.
typedef struct node
{
int number;
struct node *next;
}
node;
int main(void)
{
node *list = NULL;
node *n = malloc(sizeof(node));
if (n == NULL)
{
return 1;
}
n->number = 1;
n->next = NULL;
list = n;
// 첫 번째 노드의 number 확인
printf("number : %i
",list->number );
// n에 새로운 메모리를 다시 할당
n = malloc(sizeof(node));
if (n == NULL)
{
return 1;
}
n->number = 2;
n->next = NULL;
list->next = n;
// 두 번째 노드의 number 확인
printf("number : %i
", list->next->number);
// 다시 n에 새로운 메모리 할당
n = malloc(sizeof(node));
if (n == NULL)
{
return 1;
}
n->number = 3;
n->next = NULL;
list->next->next = n;
// 세 번째 노드의 number 확인
printf("number : %i", list->next->next->number);
// 두 번째 노드와 세 번째 노드 사이에 노드 추가하기
node *tmp = malloc(sizeof(node));
if (tmp == NULL){
return 1;
}
// 새로 추가된 노드 구분을 위해 3대신 33을 추가
tmp->number = 33;
// 먼저 tmp에 세번 째 노드를 가리키도록 설정
tmp->next = n;
// 세 번째노드(미래 네번째 노드)에 잘 연결되었는지 확인
printf("number check : %i
", tmp->number);
// 두 번째 노드 다음에 새로 추가한 노드와 연결
list->next->next = tmp;
// 새로워진 네 번째 노드에 number 4로 교체후 next NULL로 교체
n->number = 4;
n->next = NULL;
// 두 번째 노드와 세 번째 노드(새로 추가된)가 잘 연결되어 네 번째 노드 까지 출력이 되는지 확인
printf("number : %i
", list->next->next->number);
// 최종 전체 list 확인
for (node *tmps = list; tmps != NULL; tmps = tmps->next)
{
printf("%i
", tmps->number);
}
// 메모리 해제
while (list != NULL)
{
node *tmp1 = list->next;
free(list);
list = tmp1;
}
}
2. 중간 노드 제거
#include <stdio.h>
#include <stdlib.h>
//연결 리스트의 기본 단위가 되는 node 구조체를 정의합니다.
typedef struct node
{
int number;
struct node *next;
}
node;
int main(void)
{
node *list = NULL;
node *n = malloc(sizeof(node));
if (n == NULL)
{
return 1;
}
n->number = 1;
n->next = NULL;
list = n;
// 첫 번째 노드의 number 확인
printf("number : %i
",list->number );
// n에 새로운 메모리를 다시 할당
n = malloc(sizeof(node));
if (n == NULL)
{
return 1;
}
n->number = 2;
n->next = NULL;
list->next = n;
// 두 번째 노드의 number 확인
printf("number : %i
", list->next->number);
// 다시 n에 새로운 메모리 할당
n = malloc(sizeof(node));
if (n == NULL)
{
return 1;
}
n->number = 3;
n->next = NULL;
list->next->next = n;
// 세 번째 노드의 number 확인
printf("number : %i
", list->next->next->number);
// 두 번째 노드 제거
list->next = list->next->next;
// 만약 마지막에 메모리 제거를 해주지 않을 때
// node* temp = list->next->next;
// free( list->next);
// list->next = temp;
// 최종 전체 list 확인
for (node *tmps = list; tmps != NULL; tmps = tmps->next)
{
printf("%i
", tmps->number);
}
// 메모리 해제
while (list != NULL)
{
node *tmp1 = list->next;
free(list);
list = tmp1;
}
}
추가
1. 새 노드를 생성합니다.
2. 다음에 추가 하고 싶은 노드를 찾습니다.
3. 새 노드의 next 노드를 찾은 노드의 next 노드로 가르킵니다.
4. 찾은 노드의 next 노드를 새 노드로 가르킵니다.
삭제
1. 삭제할 노드의 전 노드를 찾습니다.
2. 임시 포인터가 찾은 노드의 next 노드를 가르킵니다.
3. 찾은 노드의 next 노드를 임시 포인터의 next 노드를 가르킵니다.
4. 임시 포인터를 해제합니다.
#include <stdio.h>
#include <stdlib.h>
typedef struct node
{
int number;
struct node *next;
} node;
int main()
{
node *head = NULL;
//첫 노드 생성(헤드)
node *n = malloc(sizeof(node));
n -> number = 1;
n -> next = NULL;
head = n;
printf("head num: %d
", head -> number);
//노드 2 생성
n = malloc(sizeof(node));
n -> number = 2;
n -> next = NULL;
head -> next = n;
for(node *tmp = head; tmp != NULL; tmp = tmp -> next) {
printf("%d ", tmp -> number);
}
printf("
");
//1과 2 사이에 3 추가
n = malloc(sizeof(node));
n -> number = 3;
n -> next = NULL;
for(node *tmp = head; tmp != NULL; tmp = tmp -> next) {
if(tmp -> number == 1) {
n -> next = tmp -> next;
tmp -> next = n;
break;
}
}
for(node *tmp = head; tmp != NULL; tmp = tmp -> next) {
printf("%d ", tmp -> number);
}
//3 삭제
for(node *tmp = head; tmp != NULL; tmp = tmp -> next) {
if(tmp -> next -> number == 3) {
node *t = tmp -> next;
tmp -> next = tmp -> next -> next;
free(t);
break;
}
}
for(node *tmp = head; tmp != NULL; tmp = tmp -> next) {
printf("%d ", tmp -> number);
}
while(head != NULL) {
node *tmp = head -> next;
free(head);
head = tmp;
}
}
// Add a node in the middle of a linked list
void add_node_in_middle(struct node *head, int data) {
// Create a new node
struct node *new_node = (struct node *)malloc(sizeof(struct node));
new_node->data = data;
new_node->next = NULL;
// Find the node before the insertion point
struct node *current = head;
while (current->next != NULL && current->next->data < data) {
current = current->next;
}
// Insert the new node
new_node->next = current->next;
current->next = new_node;
}
// Delete a node in the middle of a linked list
void delete_node_in_middle(struct node *head, int data) {
// Find the node to be deleted
struct node *current = head;
struct node *prev = NULL;
while (current != NULL && current->data != data) {
prev = current;
current = current->next;
}
// If the node was not found, return
if (current == NULL) {
return;
}
// If the node is the head, update the head
if (prev == NULL) {
head = current->next;
} else {
prev->next = current->next;
}
// Free the memory of the deleted node
free(current);
}
typedef struct node
{
int number;
struct node *next;
}
node;
int main(void)
{
node *list = NULL;
node *n = malloc(sizeof(node));
if (n == NULL)
{
return 1;
}
n-> number = 1;
n-> next = NULL;
list = n;
node *n = malloc(sizeof(node));
if (n == NULL)
{
return 1;
}
n-> number = 2;
n-> next = NULL;
list->next = n;
node *n = malloc(sizeof(node));
if (n == NULL)
{
return 1;
}
n-> number = 3;
n-> next = NULL;
list->next->next = n;
// 중간인 2를 삭제
node* temp = list->next->next;
free( list->next);
list->next = temp;
// 1과 3 사이에 2추가
n = malloc(sizeof(node));
if (n == NULL)
{
return 1;
}
n-> number = 2;
n-> next = list->next;
list->next = n;
}
1. 추가
노드에 부여하려는 앞선 순서의 포인터를 저장하고 저장 후 중복하여 뒷 선서를 가리키는 노드에 넣으려는 노드를 가리키는 포인터를 부여한다.
2. 삭제
삭제하려는 노드의 앞선 노드의 포인터를 삭제하려는 노드의 다음 노드를 가리키는 포인터로 부여한다면 삭제하려는 노드의 포인터에 널 값을 부여한 다음 메모리에 free를 선언해 노드를 삭제한다.
//노드 만드는 과정
node *list = NULL; //node, list(시작) 포인터 만들기
node *n = malloc(sizeof(node)); //node, n(number,*next 그릇) 포인터 만들기(1)
if (n == NULL)
{
return 1;
}
n->number = 0;
n->next = NULL;
list = n; //n의 사항을 list에 넣기
n = malloc(sizeof(node)); //node, n(number,*next 그릇) 포인터 만들기(2)
if (n == NULL)
{
return 1;
}
n->number = 2;
n->next = NULL;
list->next = n; //0->2
n = malloc(sizeof(node)); //node, n(number,*next 그릇) 포인터 만들기(3)
if (n == NULL)
{
return 1;
}
n->number = 1;
n->next = NULL;
n->next = list->next; //0->2 값을, 1->2 로 변환
list->next = n; //0->1
//추가 노드 삭제
node *tmp = list; //0을 가르키는 tmp
tmp->next = n->next; //1->2를 0->2로 바꾸기
n->next = NULL; //기존의 1->2 값을 NULL로 변환.
free(n); //number가 1이었던 n값을 삭제.
연결하고 있는 node를 중복으로 합니다. 그리고 추가하거나 삭제하고자 하는 코드를 다시 연결합니다. 그리고 연결리스트를 재배열합니다.
#include <stdio.h>
#include <stdlib.h>
typedef struct node
{
int number;
struct node *next;
}
node;
int main(void)
{
//make list
node *list = NULL;
//make n
node *n = malloc(sizeof(node));
if(n == NULL)
{
return 1;
}
n->number = 1;
n->next = NULL;
//list list to node1
list = n;
n = malloc(sizeof(node));
if(n == NULL)
{
return 1;
}
n->number = 2;
n->next = NULL;
list->next = n;
//add node0
n = malloc(sizeof(node));
if(n == NULL)
{
return 1;
}
n->number = 0;
n->next = list;
list = n;
//delete node1
list->next = list->next->next;
free(list->next->next);
for(node *tmp = list;tmp!=NULL;tmp = tmp->next)
{
printf("%i
",tmp->number);
}
while(list != NULL)
{
node *tmp = list->next;
free(list);
list = tmp;
}
}
1. 첫번째 노드와 두번째 노드 사이에 새로운 노드(새롭게 두번째 노드가 될 데이터)를 추가하는 코드
//새로운 노드 만들기
n = (node*)malloc(sizeof(node));
if (n == NULL)
{
return 1;
}
n -> number = 1;
n -> next = NULL;
//포인터 연결하기
//step1. 새로운 노드와 그 다음 노드 연결하기
tmp = list;
for (int i = 0; i < 1; i++)
{
tmp = tmp->next;
}
n->next = tmp;
//step2. 새로운 노드와 그 전 노드 연결하기
tmp = list;
tmp->next = n;
2. 위에서 추가했던 노드 삭제 (2번째 노드 삭제)
node *pre = list;
node *remove = list;
// for (int i = 0; i < n-2; i++){pre = pre->next} => 지우고자 하는 (n번째)노드 바로 전의 노드를 pre가 가리키도록 함. 지금의 경우 n=2여서 이 과정 생략
remove = pre->next;
pre->next = remove->next; //n-1번째 노드와 n+1번째 노드 연결
free(remove); //n번째 노드 삭제