C언어 단일 연결리스트 질문드립니다.

우선 아래의 코드는 제가 짜본 단일 연결리스트 입니다.

#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>

typedef struct Node Node;
struct Node {

	Node* next;
	int value;
};

Node* head;

void InitList() {

	head = (Node*)malloc(sizeof(Node));
	if (head != NULL) {

		head->next = NULL;
	}
}

Node* Insert_Node(Node* Target, Node* aNode) {

	Node* New;

	New = (Node*)malloc(sizeof(Node));
	if (New != NULL) {

		*New= *aNode;

		New->next = Target->next;
		Target->next = New;
		return New;
	}
	return NULL;
}
/*1. Target : 0x01164680*/
bool Delete_Node(Node* Target) {
	/*1. Del : 0xcccccccc*/
	Node* Del;
	/*1. Target : 0x01164680*/
	/*1. Target->next : 0x011646b8*/
	/*2.  두번째 Target->next의 값 : 0x01164dc8 이전 Target->next와 동일한걸 확인함*/
	Del = Target->next;
	/*1. Del : 0x011646b8*/
	if (Del == NULL) {
		return false;
	}

	Target->next = Del->next;
	/*1. Target : 0x01164680*//*Target->next : 0x01164dc8*/
	free(Del);
	/*1. Del 주소 : 0x011646b8*/
	/*1. Del->next : 0xdddddddd*/
	return true;
}

void UnInit_List() {

	static int Delete_Count = 1;
	/*
		1. head : 0x01164680
	*/
	/*
		2. head : 0x01164680
	*/
	while (Delete_Node(head)) { 
		printf("%d\n",Delete_Count++); 
	}

	printf("Delete Head\n");
	free(head);
	head = NULL;
}

int main() {

	int i;

	Node* Now, Temp;

	InitList();

	Now = head;
	for (i = 1; i <= 5; i++) {
		Temp.value = i;
		Now = Insert_Node(Now, &Temp);
	}

	//Delete_Node(head->next);

	/*for (Now = head->next; Now; Now = Now->next) {

		printf("%d\n", Now->value);
	}*/
	printf("\n");

	UnInit_List();
}

제가 질문 드리고 싶은 코드는 위 코드에서 Delete_Node ()코드입니다.

/*1. Target : 0x01164680*/
bool Delete_Node(Node* Target) {
	/*1. Del : 0xcccccccc*/
	Node* Del;
	/*1. Target : 0x01164680*/
	/*1. Target->next : 0x011646b8*/
	/*2.  두번째 Target->next의 값 : 0x01164dc8 이전 Target->next와 동일한걸 확인함*/
	Del = Target->next;
	/*1. Del : 0x011646b8*/
	if (Del == NULL) {
		return false;
	}

	Target->next = Del->next;
	/*1. Target : 0x01164680*//*Target->next : 0x01164dc8*/
	free(Del);
	/*1. Del 주소 : 0x011646b8*/
	/*1. Del->next : 0xdddddddd*/
	return true;
}

void UnInit_List() {

	static int Delete_Count = 1;
	/*
		1. head : 0x01164680
	*/
	/*
		2. head : 0x01164680
	*/
	while (Delete_Node(head)) {
		printf("%d\n", Delete_Count++);
	}

	printf("Delete Head\n");
	free(head);
	head = NULL;
}

위의 코드는 메모리를 해제하는 역할을 하는 코드이고, 메모리 해제를 하기 전 5개의 연결리스트를 만들었다고 가정하고 각각의 노드들이 1부터 1씩 증가하는 값을 가지고 있다는 가정하게 그림을 그려보면 아래와 같습니다.

위 그림에서 위에잇는 박스들은 스택에 서 연결리스트를 만들기위해 만든 구조체 포인터 변수들이고 실제 힙에 생성된 메모리는 그 아래에 그렸습니다. 연결리스트구조로 연결하게 되면 아래와 같을 것을 예상합니다. 각 번지는 이해하기 쉽게 100단위로 그려넣었습니다.(동적할당 후 실제 할당되는 메모리를 리턴해서 각 노드들이 메모리르 가리키고있는중.)

그럼 이제 UnInit_Node()함수에서 메모리를 해제하기위해 Delete_Nod()함수로 head실인수를 넘기기는 그림을 그려보면 아래와 같습니다.

Delete_Node() 함수에서 형식인수 Target으로 실인수 head의 head->next의 값을 가지게 되었고 위의 그림처럼 이제 Del은 head->next 가 가리키는 메모리를 같이 가리키게 됩니다. 하지만 Del과 Target은 현제 Delete_Node() 함수에서의 지역변수이기에 이 스코프를 빠져 나가게 되면 둘은 사라지게 됩니다. 그러므로 현재 Delete_Node() 함수 내에서 Del변수로 head->next 가 가리키는 메모리를 해제 할 순 있지만

Del = Target->next;

Target->next = Del->next;

free(Del) 

Target이 다음의 Del->next의 값을 가리키게 되는 것은 이 Delete_Node()함수내에서의 Target이지 실제 head->next의 값이 바뀌는 것이 아니므로 이 함수를 빠져나가게 되면 while 문에서 다시 이 함수로 들어올떄도똑같이 head->next는 이전의 head->next 와 동일한 값을 가져야 할것으로 예상 했지만 실제 디버깅을 해본 결과 head의 값은 바뀌지 않았지만 head->next 가 가리키는 값이 이전 Delete_Node 함수에서의 Target->next의 값과 동일했고 그럼 실제로 head->next의 값이 바뀌었다는 이야기가 됩니다. 하지만 제가 공부하기론 아래의 코드처럼

#include <stdio.h>

void Func(char* p_str);

int main() {

	char str[] = "Hello, World!";

	printf("Before : %s\n", str);

	Func(str);

	printf("After : %s\n", str);

	return 0;
}

void Func(char* p_str) {

	p_str += 3;
	printf("Func : %s\n", p_str);
}

이런식으로 실인수의 값이 바뀐게 아니라 함수내에서의 형식인수의 값만 바뀌었기 떄문에 제가 질문드린 코드에서도 마찬가지로 head->next의 값은 변함이 없어야 하는게 아닌가 라는 생각을 했습니다. 그럼 결국 while문에서 계속 head를 호출하고 head->next 는 이미 해제 된 메모리인데 또해제를 하기에 그리고 NULL번지를 가리키지 안히에 런타임 오류가 발생해야 한다고 생각했습니다.

그래서 결론은 왜 위의 코드에서 head->next 의 값이 실제 다음 노드를 가리키게 되는지가 궁급합니다! 독학으로 코딩을 하고있어서 항상 궁금한건 많은데, 짜잘한것들도 다 질문하면 끝도 없어서 최대한 스스로 해결해보고 안되면 이런식으로 그림을 그려서 제가 여지껏 공부한 개념이 맞는지 보여드리고 있는데, 혹시 제 그림이 이상하거나 예시로 든 코드 내용이라든가 문제점도 같이 지적해주시면 감사드리겠습니다!

조금 더 덧붙이자면 위 코드에서 head->next 의 값이 변하지 않을 것으로 예상해서 짜본 코드는 아래와 같습니다!

#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>

typedef struct Node Node;

struct Node {

	Node* next;
	int value;
};

Node* head;

void Init_Node() {

	head = (Node*)malloc(sizeof(Node));
	if (head != NULL) {

		head->next = NULL;
	}
}

Node* Insert_Node(Node* Target) {

	static unsigned Count = 1;

	Node* New = (Node*)malloc(sizeof(Node));
	if (New != NULL) {

		New->value = Count++;
		New->next = Target->next;
		Target->next = New;
		return New;
	}
	return NULL;
}

void Print_Node() {

	for (Node* Move = head->next; Move; Move = Move->next)
		printf("%d ", Move->value);
	printf("\n");
}

Node* Delete_Node(Node* Target) {

	static unsigned Count = 1;
	Node* Move = Target;

	if (Move == NULL)return NULL;
	else {

		Target = Move->next;
		free(Move);
		printf("%d ", Count++);
		return Target;
	}
}

void UnInit_Node() {

	while (head = Delete_Node(head));

	return;
}

int main() {

	Init_Node();

	Node* Target = head;
	for (int i = 0; i < 10; i++) {

		Target = Insert_Node(Target);
	}

	Print_Node();

	UnInit_Node();

	return 0;
}

그래서 이런식으로 코드를 짰었는데…ㅠ 디버깅을 해보니 또 위 코드도 되더라구요 그래서 질문 드렸습니다!

수고가 많으십미다. 연결리스트는 코톡에 아마도 가장 많이 올라온 주제가 아닐까 추측해 봅니다.

한번 살펴보세요.

https://www.codentalks.com/search?context=topic&context_id=7745&q=%EC%97%B0%EA%B2%B0&skip_context=true

1 Like

답변을 드리자면 아래 소스에서 Delete_Node()를 통해 home 의 next가 바뀌는게 맞습니다.

while (Delete_Node(head)) { 
	printf("%d\n",Delete_Count++); 
}

Delete_Node()의 이 부분이 바꿔주고 있고요.

Target->next = Del->next;

우선 말씀하신 것 처럼 C언어에서 매개변수를 넣어 함수를 호출 했을 때 함수 내에서 형식인수를 바꾼다고 실인수가 바뀌진 않습니다. 함수를 호출할 때 실인수의 값을 그대로 복사해서 사용하기 떄문이죠.

포인터도 마찬가지입니다. 포인터 변수가 저장한 값은 주소이고 함수를 호출할 때 저장된 주소를 복사하고 함수 내에서 이를 역참조하여 해당 주소에 저장된 값들을 쓰는 것이고요.

님 말대로 Delete_Node()의 형식인수인 Target과 실인수인 head가 서로 별개의 변수인 건 맞습니다. 그런데 Target에 저장된 주소와 head에 저장된 주소가 같기 때문에 Target을 역참조하나 head를 역참조하나 두 포인터 변수를 통해 수정하는 값은 동일하겠지요? 둘 다 InitList()에서 할당해서 head에 저장한 주소를 참조하니깐요.

정리하면 아래 코드는 형식인수를 수정한 것이 아니라 형식인수가 가지고 있는 주소를 역참조하여 주소에 저장된 값을 수정한 것 입니다.

Target->next = Del->next;    /* Target과 head가 가지고 있는 주소는 동일하므로 head->next = Del->next 와 같다 */