C) 싱글 링크드 리스트 구현 + 메모리 추적

시작하기에 앞서 이걸 왜 하고 있는가?

자바스크립트로만 구현해봤던 자료구조들을 C언어를 이용해서도 구현해보고 싶었다. 메모리단까지 까집어볼 수 있다면 왠지 간지날 것 같아서이다. 지금 하는 이 공부가 현재 내가 하고 있는 프론트엔드 개발에 직접적인 도움을 주지는 않겠지만, 개발에 필요한 사고의 폭과 넓이를 확장시켜줄 수 있지 않을까 생각한다.

 

C를 공부하며 느낀 좋은 점은 절차적인 개발 능력이 향상되는 것 같은 느낌이 든다는 것(?)이다. 메모리의 지역변수와 스택을 고려해볼 수 있게 되었고, 힙에 동적으로 메모리 할당을 하고, 할당한 메모리를 해제해보면서 뭐랄까... 역시 그냥 돌아가는 것은 없구나. 라는 것을 새삼 체감하게 된다.

 

아무튼 아직도 배워가고 있다. 컴퓨터란 것을... 기초라는 것을...

... 아직도 기초를 하고 있냐고 할 수 있지만 뭐... 본인 자체가 슬로우 스타터인만큼 걍 계속 배워보자.

 

각설하고...
이 포스트에서는 USERDATA라는 구조체를 노드 단위로 삼아 싱글 링크드 리스트를 구현해볼 것이다.

 

싱글 링크드 리스트 구현

typedef struct USERDATA
{
	int age;
	char name[32];
	char phone[32];
	struct USERDATA* pNext;
} USERDATA;

 

위의 USERDATA는 자기 참조 구조체로써 자료구조를 생성할 노드 한 개 단위가 된다.

노드는 추상적인 개념이다. 사랑, 우정, 용기같은 단어와 같다고 할 수 있다. 그래서 그냥 머릿속으로 노드라고 생각하는 것 보다는 그림으로 하나씩 그려가며 표현하는게 옳은 공부 방식이다. 이 구조체를 그림으로 표현하자면 아래와 같다.

노드의 추상적인 개념을 그림으로 표현한 것

 

미더덕같이 생긴 이 노드들을 이어붙이면 아래 그림과 같이 된다.

싱글 링크드 리스트

 

노드의 개념을 잡아냈다면 본격적으로 코드로 구현해보도록 하자.

 

구현 순서

자료구조를 보다 안전(?)하게 구현하기 위해서는 몇가지 함수들을 미리 구현해놓는 것이 좋을 수 있다. 집 지을때 아무런 구조도 잡지 않고 바로 공구리부터 치는게 아닌 것 처럼, 자료구조도 나름 구조이므로 어느 정도 구현 순서가 있다고 할 수 있다.

 

그러한 구현 순서는 아래와 같다.

1. 설계 (어떤 방식으로 구현할건지 ?)
2. 자료 구조 내 모든 노드를 순회하며 출력하는 함수 작성
3. 자료구조에 새 노드를 추가하는 함수 작성
4. 자료구조 메모리 해제 함수 작성
5. 테스트 후 필요한 작업 추가

당연하겠지만 0순위로 먼저 간단한 설계를 해야한다. 자료구조를 전역변수에 선언할 것인지 아니면 함수 스코프 내 지역변수에 선언할 것인지, 구조체는 어떤 걸로 할 것인지 등등 말이다.

 

설계가 대충 끝났다면 자료구조 내 모든 노드를 출력하는 함수를 미리 만들어놓아야 한다. 어려운 자료구조들은 작성하면서 중간중간 체크를 해야할 필요성이 있기 때문이다. 다 만들고 디버그를 하는 것보다는 만드는 중간에 디버그를 하는 편이 더 낫다. 그러므로 자료구조 내 모든 데이터를 확인하는 함수를 만드는 것은 1순위 작업이 되어야한다.

 

이 후 노드를 추가하고, 전체 리스트를 삭제하고, 특정 노드를 삭제하는 작업은 디버깅을 해가면서 만들어가면 될 것이다.

 

1. 설계

typedef struct USERDATA
{
	int age;
	char name[32];
	char phone[32];
	struct USERDATA* pNext;
} USERDATA;

int main(void)
{
	USERDATA* pHeadNode = NULL;

	// Input
	AddNewNode(&pHeadNode, 10, "2DC", "010-1111-2222");
	AddNewNode(&pHeadNode, 10, "3DC", "010-2222-2222");
	AddNewNode(&pHeadNode, 10, "4DC", "010-3333-3333");

	// TEST CODE
	PrintList(pHeadNode);
	ReleaseList(&pHeadNode);
	PrintList(pHeadNode);

	return 0;
}

 

나는 USERDATA 구조체를 이용해 main 함수 지역변수 내에서 싱글 링크드 리스트를 만들고 싶다. 설계 단계에서는 필요한 함수 시그니처들을 미리 작성 해본다. 뭘 구현할건지 미리 생각해놓는 것은 중요하다.

 

2. 리스트 내 노드를 출력하는 함수 작성

이후 디버깅에 필수적인 노드 출력 함수를 작성한다.

void PrintList(const USERDATA* pNode)
{
	while (pNode != NULL)
	{
		printf("[%p] %d, %s, %s [%p]\n",
       		pNode, pNode->age, pNode->name, pNode->phone, pNode->pNext);
		pNode = pNode->pNext;
	}
	puts("출력완료");
}

• 싱글 링크드 리스트를 이루는 노드의 주소를 받아 링크를 순회하며 값을 출력하는 함수이다.

싱글 링크드 리스트 출력은 노드를 줄줄이 사탕처럼  출력하면 되므로 기능 자체는 어렵지 않다.

 

3. 노드를 추가하는 함수 작성

이 단계부터는 바로 정답이 안나온다. 계속 디버깅을 해가면서 필요한 부분을 만들어야한다. 

무턱대고 코드부터 작성하는 것은 코드 구현의 시간을 기하급수적으로 늘릴 수 있으므로, 내가 구현하고자 하는 것을 미리 글로 한번 써보는 것이 바람직하다.

 

1. 자료구조의 원형과 나이, 이름, 폰번호를 매개변수로 받는 함수를 만든다.
2. USERDATA 노드 만큼의 메모리를 힙 영역에 동적할당한다.
3. 매개변수로 받은 나이, 이름, 폰 번호를 동적할당한 영역에 각각 추가한다.
4. 만든 노드를 자료구조 원형에 부착해야한다.
5. 만약 미리 선언된 Head가 없다면 방금 만든 노드를 Head로 만든다.
6. Head가 있다면 방금 만든 노드의 pNext에 현재 Head를 연결하고, 현재 Head를 방금 만든 노드로 바꾼다.

구현할 것을 다 글로 적었다면 코드로 옮겨보자

 

void AddNewNode(const USERDATA** pHead, int age, const char* pszName, const char* pszPhone)
{
	USERDATA* pNewNode = (USERDATA*)malloc(sizeof(USERDATA));

	if (pNewNode == NULL) {
		puts("메모리 할당 실패");
		return;
	}
	
	pNewNode->age = age;
	strcpy_s(pNewNode->name, sizeof(pNewNode->name), pszName);
	strcpy_s(pNewNode->phone, sizeof(pNewNode->phone), pszPhone);
	pNewNode->pNext = NULL;

	if (*pHead == NULL)
		*pHead = pNewNode;
	else
	{
		pNewNode->pNext = *pHead;
		*pHead = pNewNode;
	}
}

 

먼저 힙 영역을 사용하기 위해서는 동적인 메모리 할당이 필요하다. 동적 메모리 할당을 하려면 malloc을 사용해야 한다. 여기서 사용한 malloc은 USERDATA 만큼의 메모리 크기를 힙 영역에 할당한 후, 할당된 포인터 주소값을 USERDATA 포인터 자료형을 가진 pNewNode에 전달한다. 즉 pNewNode를 역참조하면 방금 힙에 할당된 메모리가 나온다.

 

나는 노드 추가 함수를 완전 함수처럼 이용하고 싶었으므로, 싱글 링크드 리스트 노드 추가에 필요한 모든 기능들을 매개변수화했다. 복잡해보이는 부분은 이중 포인터 **pHead인데, 기존 자료구조 원형이 바라보는 포인터값을 바꾸기 위해서는 아무래도 이중 포인터를 사용할 수밖에 없었다. 말이 참 어려운데 아래 그림을 보자.

USERDATA* pHeadNode = &someUserData 또는 USERDATA* pHeadNode = USERDATA*SomeUserDataPointer

 

포인터를 다루기가 어려울때는 그림을 그려보면 된다.

현재 작성중인 함수는 USERDATA** pHead를 매개변수로 받는다. 즉 역참조를 두번하면 USERDATA에 접근할 수 있다는 소리다. 그렇다면 역참조를 한번만 하면 *pHead가 참조하고 있는 USERDATA의 구조체를 가리키는 포인터 변수를 바꿀 수 있을 것이다.

포인터가 잘 이해가 가지 않는다면 메모리 참조의 관계를 그려보자.

 

*pHead로 접근하면 포인터변수 pHeadNode에 접근할 것이다. 즉 pHeadNode가 참조하는 USERDATA 구조체 포인터 값을 바꿀 수 있다.

 

마지막으로 pHead의 조건에 따라 헤더 노드를 설정하면 된다.

최초에 pHead가 NULL이라면 pHead 자체에 newNode를 할당하고, pHead가 있었다면 pHead의 앞에 새 노드를 가져다 붙이고, 포인터를 연결해준 후 pHead를 최신 노드로 변경해주면 노드 추가 함수의 기능 구현은 끝난다.

 

4. 자료구조 메모리 해제 함수 작성

이제 전체 리스트 내 노드를 삭제하는 함수를 작성해보자.

완성 코드는 아래와 같다.

void ReleaseList(const USERDATA** ppHead) {
	USERDATA* pHead = *ppHead;
	USERDATA* pDelete;
	while (pHead != NULL)
	{
		pDelete = pHead;
		pHead = pDelete->pNext;
		printf("Delete : [%p] %d, %s, %s [%p]\n", pDelete, pDelete->age, pDelete->name, pDelete->phone, pDelete->pNext);
		free(pDelete);
	}
	*ppHead = NULL;
	puts("삭제완료");
}

 

 

노드 추가 함수처럼 이 함수도 완전 함수식으로 구성하고 싶었으므로 매개변수로 싱글 링크드 리스트의 이중 포인터를 받는다. 그래야 마지막에 자료구조의 헤드가 참조하고 있는 메모리 주소를 깔끔하게 비워줄 수가 있다. 만약 단일 포인터로만 자료구조에 접근 한다면 마지막에 자료구조의 헤드 포인터를 참조할 수 없게 된다.

 

이 함수는 약간의 설명이 필요하다.

• 먼저 pHead라는 변수에 최초의 자료구조 헤드 포인터를 넘긴다.
• pDelete라는 USERDATA 포인터 변수를 생성한다. 이 변수는 temporary 기능을 수행하며 지워질 메모리를 의미한다.
• while문에서는...
• pDelete에 현재 헤더 포인터를 할당한다. (매번 헤더가 지워질 것이므로)
• pHead에는 pDelete가 참조하고 있는 다음 노드를 할당한다.
• pDelete를 메모리 해제한다.
• 반복한다.
• while문이 끝난 후에는 싱글 링크드 리스트의 헤더에 남아있는 쓰레기값을 제거해준다. (이중 포인터 필요)

 

5. 테스트

다 만들었으면 테스트를 해보자.

일단 단순 실행화면이다.

값은 잘 출력이 되고, 메모리 삭제도 잘 되는 것 처럼 보인다.

빌드 때 에러메세지는 없었을까?

 

 

에러메세지를 보니 const 한정자를 붙여놓았으면서 왜 const 처럼 사용하지 않냐는 워닝 메세지를 띄워준다.

ReleaseList 함수와 AddNewNode 함수에서 이중포인터로 사용한 매개변수를 내가 직접 수정하고 있음에도 불구하고 const 한정자를 붙였기 때문에 나온 에러로 보인다. 각 함수의 const 한정자를 제거해보자.

 

매개변수의 const 한정자를 제거해보자.

 

 

제거 한 후에는 아무런 에러 메세지가 출력되지 않았다.

 

6. 메모리 추적

디버거 모드를 통해 메모리를 추적해보자.

 

먼저 노드 추가가 잘 되는지 테스트 해볼 것이다.

 

 

첫 노드가 추가된 후, pHeadNode가 참조하는 주소가 바뀌었음을 알 수 있다. (빨간 부분)

포인터 변수의 값에는 메모리 주소가 할당되므로 포인터 변수에 할당된 메모리 주소를 추적해보자.

내가 사용하는 인텔 프로세서는 x64이므로 리틀 엔디안 규칙을 따라 pHeadNode가 가리키는 메모리 주소는

0000022A95B151F0 이 된다.

 

 

메모리 주소를 따라와보니 USERDATA 구조체가 보인다. 0a 는 10이고, 이름도 잘 들어가 있으며, 전화번호도 잘 들어가 있다.

 

F10을 눌러 다음 메모리 주소를 추적해보자.

 

 

pHeadNode의 주소는 3DC를 가리키게 된다.

싱글 링크드 리스트에 노드를 추가할 때 헤드 방향으로 하나씩 붙기 때문이다.

같은 이유로 3DC 노드의 pNext 변수에는 2DC 노드의 메모리 주소인 0000022A95B151F0이 할당되어 있다.

 

노드 추가는 아무 문제 없는 듯 하다.

싱글 링크드 리스트에 할당된 메모리를 해제해보자.

 

 

ReleaseList(자료구조 해제 함수)의 실행이 완료된 후의 2DC 노드 메모리 주소를 살펴보면 깔끔하게 해제가 되어있다.

 

 

이로써 싱글 링크드 리스트의 메모리단 구현과 디버그가 끝났다. 짝짝짝