🔊 해당 포스팅은인프런의 널널한 개발자님의 독하게 C를 배운 사람을 위한 선형 자료구조 강의를 듣고 개인적인 복습 목적 하에 작성된 글입니다. 해당 포스팅에 사용된 모든 자료는 필자가 직접 재구성하였음을 알립니다.
이번 포스팅에서는 가장 기본적인 선형 자료구조 중 하나인 연결 리스트(Linked List) 자료구조를 C 언어로 구현해 보도록 하자. 이번 포스팅에서 구현할 것은 성능 개선과 같은 것들을 고려하지 않고 정말 구현에 초점을 맞추어 본다.
1. 연결 리스트 자료구조
구현에 앞서서 연결 리스트가 어떤 자료구조인지 알아보아야 한다. 흔히 연결 리스트라는 자료구조를 구글링 해보면 아래와 같은 그림이 등장한다.
위 그림 속 하나의 data 와 next 가 같이 들어있는 것을 하나의 '노드(Node)' 라고 표현한다. 그리고 하나의 노드 안에는 data 와 next 라는 것으로 구성된다. data는 말 그대로 해당 노드 안에 실질적으로 담겨 있는 데이터를 의미하고, next 는 해당 노드와 '연결'되어 있는 다른 노드의 위치 정보를 의미한다. 여기서 '위치 정보' 라고 한다면 '메모리 주소'가 되고, C 언어에서는 메모리 주소가 담겨있는 변수인 포인터 변수가 된다.
그러한 관점에서 위 그림 속 자료구조를 해석해 보면 11이라는 data가 담긴 노드는 next에 200이라는 위치 정보를 갖고 있는데, 이 200이라는 위치 정보는 해당 노드와 연결되어 있는 다른 노드의 위치 정보이다. 즉, 18이라는 data가 담긴 노드의 위치 정보이다.
그리고 위 연결 리스트 자료구조에서 맨 앞쪽(왼쪽)에 있는 노드를 Head 노드, 맨 끝쪽(오른쪽)에 있는 노드를 Tail 노드라고도 부른다.
우리는 이제 위와 같은 연결 리스트 자료구조를 만들고 어떤 행동들을 취해볼 것이다. 여기서 '어떤 행동들'이라 함은 연결 리스트 자료구조에 데이터를 추가(add) 하고, 데이터를 검색(search) 하고, 또 데이터를 삭제(remove) 하기도 해볼 것이다. 먼저 데이터를 추가(add) 하는 방법부터 알아보자.
2. 연결 리스트에 데이터 추가(Add) 해보기
연결 리스트에 데이터를 추가하는 기능을 구현해보자. 먼저 추가할 데이터를 C 언어의 구조체로 아래처럼 선언해 두자.
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
typedef struct USERDATA {
int age;
char name[32];
char phone[32];
struct USERDATA *pNext;
} USERDATA;
USERDATA* g_pHead = NULL;
USERDATA라는 자료형의 구조체를 선언했고, 해당 구조체 안에는 USERDATA 라는 자기 자신의 구조체를 또 정의했고, 이를 포인터 변수인 pNext로 정의했다. 이 포인터 변수가 하는 역할은 1번 목차에서 알아본 '노드 들간의 연결'의 기능을 수행한다.
그리고 Head 노드가 어떤 메모리 주소에 담겨있는지 가리키는 포인터 변수를 전역변수로 g_pHead라는 값으로 선언했고, 가장 최초에는 연결 리스트 자료구조에 어떤 데이터도 만들어지지 않은 상태이기에 NULL로 할당했다.
이제 본격적으로 연결 리스트 자료구조를 만들면서 데이터를 추가해 보자. 먼저 데이터를 추가할 때의 경우의 수가 어떤 것들이 있는지 생각해 볼 필요가 있다.
Case1 은 연결 리스트에 데이터가 아예 없을 경우이다. 이런 경우는 Head 노드를 가리키는 포인터 변수는 g_pHead가 NULL일 것이다. 또 다른 Case2로는 이미 연결 리스트에 데이터가 존재할 경우이다. 물론 이 Case2에서 데이터를 추가한다는 것은 항상 반드시 연결 리스트의 Tail 부분에 새로운 데이터를 추가하는 것(append)만을 의미한다.(기존에 존재하는 데이터들 사이에 끼워 삽입하는 경우는 여기서 제외한다)
Case1의 구현은 생각보다 간단하다. g_pHead 값이 NULL 인지 여부만 따지고 NULL이라면 새롭게 추가할 데이터를 연결 리스트에 넣어주기만 하면 된다.
Case2의 구현은 한 가지 생각해 볼 점이 있다. 먼저 새롭게 추가할 데이터가 확보되면 이 새로운 데이터를 현재 연결 리스트의 Tail 노드의 끝(오른쪽)에 넣어야 한다. 즉, 그림으로 표현하면 아래와 같다.
위처럼 Tail 노드에 append 하려면 우리는 무엇을 알아내야 할까? 바로 현재 연결 리스트의 Tail 노드가 어디인지를 알아내야 한다. 이를 알아내기 위해서는 어떻게 해야 할까? 단순하게 연결 리스트의 Head부터 하나씩 순회(traverse)하면 된다. 하나씩 순회하면서 연결 리스트의 특정 데이터(노드)가 Tail 노드인지 여부는 어떻게 확인할 수 있을까? 바로 해당 노드의 next(포인터 변수)가 NULL을 가리키면 그 노드가 Tail 노드임을 알 수 있다.
위와 같은 사고과정을 거쳐 Case1, Case2를 반영한 코드를 작성하면 아래와 같다. 참고로 C 언어에서는 데이터를 추가하기 위해 malloc 함수를 이용해 동적 메모리 할당을 활용해 추가한다.
void AddElement(int age, const char* pName, const char* pPhone) {
// 연결 리스트에 데이터를 추가하기 위한 메모리 동적할당
USERDATA* pNew = (USERDATA*)malloc(sizeof(USERDATA));
pNew->age = age;
strcpy(pNew->name, pName);
strcpy(pNew->phone, pPhone);
pNew->pNext = NULL;
// global head pointer 체크 후 분기
if (g_pHead == NULL) {
g_pHead = pNew;
} else {
// traverse (use Queue)
USERDATA* pTail = g_pHead;
while (pTail->pNext != NULL) {
pTail = pTail->pNext;
}
pTail->pNext = pNew;
// Use Stack
// pNew->pNext = g_pHead;
// g_pHead = pNew;
}
}
이렇게 해서 연결 리스트에 데이터를 추가하는 로직이 완성되었다.
3. 연결 리스트에서 데이터 검색(Search)하기
다음으로 구현해 볼 기능은 연결 리스트에 존재하는 특정 데이터를 검색하는 것이다. 검색한다라는 것은 사용자와 같은 어떤 누군가가 입력 또는 질의(쿼리)한 값을 기준으로 일치하는지 여부를 검색하고, 일치하면 그 일치하는 데이터를 반환하고, 없다면 그다음 노드를 탐색하면 된다.
그리고 일치하는지 여부를 검색하는 것도 마찬가지로 연결 리스트의 모든 데이터 원소를 Head 노드부터 Tail 노드까지 순차적으로 순회하면 된다.
위 검색 로직을 구현하면 아래와 같다.
USERDATA* SearchElement(const char* pszName) {
USERDATA* pSearch = g_pHead;
// traverse
while (pSearch != NULL) { // pSearch->pNext로 바꾸면 Tail Node에 있는 데이터가 not found 처리됨
// check field
if (strcmp(pSearch->name, pszName) == 0) {
printf("\"%s\" Found in Linked-list Structure\n", pszName);
return pSearch;
}
// move to next node
pSearch = pSearch->pNext;
}
printf("\"%s\" Not Found in Linked-list Structure\n", pszName);
}4. 연결 리스트에서 데이터 삭제(Remove)하기
마지막으로 구현해 볼 기능은 연결 리스트에서 어떤 데이터를 삭제하는 기능이다. 데이터 삭제라는 것은 하나의 기능처럼 보이지만 그 속을 들여다보면 2가지 기능이 동시에 수행된다. 바로 "삭제할 데이터를 검색" 하는 것과 "데이터를 삭제" 하는 것. 따라서 이 삭제 기능을 코드로 구현하기 위해서 우리는 데이터를 실질적으로 삭제하는 행동을 수행하기 전에 삭제할 데이터를 검색(search)하는 것이 선행되어야 한다. 그리고 '검색'이 수행된다는 것은 3번 목차에서 알아본 것처럼 사용자가 입력 또는 질의한 어떤 값을 기준이 마련되어야 한다.
따라서 데이터를 삭제한다는 것은 아래와 같은 순서로 진행된다.
이렇게만 하면 데이터 삭제가 완성되는 걸까? 아니다. 연결 리스트에서는 삭제를 수행할 때, 한 가지 더 선행되어야 하는 것이 있다. 바로 "연결(link)의 교통정리" 이다. 이 연결의 교통정리란, 위 그림에서 까만색 화살표 즉, 노드의 next(포인터 변수)가 가리키는 부분을 정리해주어야 함을 의미한다.
만약 위 그림에서 연결의 교통정리를 수행하지 않은 채 [3. 삭제 수행]을 해버리면 어떻게 될까? 아래 그림처럼 될 것이다.
이렇게 되면 data = bar 인 노드의 next 포인터 변수가 가리키는 곳이 NULL이긴 하지만 이 NULL이 정말 연결 리스트의 끝을 가리키는 NULL을 의미하지 않는다는 것이 문제다. 즉, 연결 리스트 자료구조가 망가지는 셈이다.
이러한 문제를 예방하기 위해서 특정 노드를 삭제하기 전에 연결의 교통정리를 수행해주어야 한다. 즉, 삭제할 노드의 이전 노드(위 그림 속에서는 data = bar인 노드)의 next가 Tail 노드의 next에 담겨있는 NULL을 가리키도록 해주어야 한다.
그런데 위처럼 연결의 교통정리를 수행해 주려면 또 한가지 추가로 알아야할 것이 있다. 연결의 교통정리를 수행해주려면 코드로 구현할 때 우리는 삭제할 노드 말고도 삭제할 노드의 이전(Previous) 노드에 대해 알아야 한다. 왜 그럴까? 그래야 이전 노드의 next를 삭제할 노드의 next와 연결(위 그림 속 [3. 연결의 교통정리])을 해줄 수 있기 때문이다.
결국, 우리는 삭제할 노드뿐만 아니라 삭제할 노드의 이전(Previous) 노드에 대해서도 알아내야 한다. 그런데 잠깐만 생각해 보자. 삭제할 노드의 위치 정보는 이전 노드의 next라는 포인터 변수에 담겨있다. 이 말은 이전 노드만 알아낸다면 이전 노드의 next 값을 통해서 삭제할 노드도 알아낼 수 있다는 것이다. 돌아 돌아서, 우리는 "삭제할 노드의 이전 노드"에 대해서 알아내기만 한다면 "연결의 교통정리" 뿐만 아니라 "삭제할 노드를 삭제"하는 것까지 모두 수행해 줄 수 있게 된다.
따라서 우리는 연결 리스트에서 데이터를 삭제하는 기능을 구현하기 위해서 아래와 같은 로직을 순차적으로 구현하면 된다.
- 사용자의 입력 또는 질의로 넘어오는 삭제할 데이터의 기준 값 받아오기
- 삭제할 데이터의 기준 값을 기준으로 연결 리스트를 순회하면서 삭제할 데이터를 갖고 있는 노드(삭제할 노드)의 "이전 노드" 정보 얻기
- 이전 노드를 활용해서 연결의 교통정리 수행
- 삭제할 노드에 대해서 삭제 수행
구현한 소스코드를 알아보기 전에 마지막으로 "삭제할 노드를 삭제"할 때의 경우의 수를 따져볼 필요가 있다. 노드를 삭제할 때 이제는 삭제할 노드뿐만 아니라 삭제할 노드의 이전 노드가 무엇인지에 따라 경우의 수가 나뉜다. 경우의 수는 다음과 같다.
이제 지금까지 설명한 로직을 코드로 구현하면 다음과 같다.
void SearchToRemove(USERDATA** ppPrev, const char* pszName) {
// 초기 상태는 Head 노드 부터
USERDATA* pCurrent = g_pHead;
USERDATA* pPrev = NULL;
// traverse
while (pCurrent != NULL) {
if (strcmp(pCurrent->name, pszName) == 0) {
*ppPrev = pPrev;
return;
}
pPrev = pCurrent;
pCurrent = pCurrent->pNext;
}
}
void RemoveElement(USERDATA* pPrev) {
// pPrev is null인 경우) 1.Head 노드도 null이어서 자료구조에 노드가 아예 없는경우 2.Head 노드를 제거할 경우
if (pPrev == NULL) {
// 1번 케이스
if (g_pHead == NULL) {
printf("!!! Empty Linked-List !!!\n");
return;
}
// 2번 케이스
USERDATA* pCurrent = g_pHead;
g_pHead = pCurrent->pNext;
printf("Remove element %s\n", pCurrent->name);
free(pCurrent);
}
else {
// 삭제할 노드가 Head 노드가 아닌 경우)
USERDATA* pCurrent = pPrev->pNext;
pPrev->pNext = pCurrent->pNext;
printf("Remove element %s\n", pCurrent->name);
free(pCurrent);
}
}
void SearchAndRemove(const char* pszName) {
USERDATA* pPrev = NULL;
// search
SearchToRemove(&pPrev, pszName);
// remove
RemoveElement(pPrev);
}5. 다양한 테스트 케이스 수행
지금까지 1~4번 목차에서 소개한 내용들을 기반으로 연결 리스트에 데이터를 추가, 검색, 삭제하는 기능을 테스트해보도록 하자. 테스트하는 과정에서 잘 동작하는 체크하기 위해 중간중간 현재 연결 리스트에 들어가 있는 데이터를 출력하는 함수인 VerboseElement라는 함수도 만들었다. 그리고 테스트가 수행되면서 연결 리스트에 남은 데이터들은 어쨌건 메모리를 동적 할당받으면서 추가된 데이터이므로 테스트가 끝난 후 OS에 할당받은 메모리를 반납하도록 하는 ReleaseElements 함수도 추가했다. 로직은 어렵지 않으니 아래 코드에서 살펴보도록 하자.
코드 전문은 아래와 같다.
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
typedef struct USERDATA {
int age;
char name[32];
char phone[32];
struct USERDATA *pNext;
} USERDATA;
USERDATA* g_pHead = NULL;
void AddElement(int age, const char* pName, const char* pPhone) {
// 연결 리스트에 데이터를 추가하기 위한 메모리 동적할당
USERDATA* pNew = (USERDATA*)malloc(sizeof(USERDATA));
pNew->age = age;
strcpy(pNew->name, pName);
strcpy(pNew->phone, pPhone);
pNew->pNext = NULL;
// global head pointer 체크 후 분기
if (g_pHead == NULL) {
g_pHead = pNew;
} else {
// Queue
USERDATA* pTail = g_pHead;
while (pTail->pNext != NULL) {
pTail = pTail->pNext;
}
pTail->pNext = pNew;
// Stack
// pNew->pNext = g_pHead;
// g_pHead = pNew;
}
}
void ReleaseElements(void) {
puts("\n>>> Releasing the list of elements");
USERDATA* pTemp = g_pHead;
while (pTemp != NULL) {
USERDATA* pRemove = pTemp;
pTemp = pTemp->pNext;
printf("[Remove][%p] %d %s %s [Next:%p]\n", pRemove, pRemove->age, pRemove->name, pRemove->phone, pRemove->pNext);
free(pRemove);
}
// 초기화 안할 시, Test-case 연속으로 수행할 때 다음 테스트 케이스 수행하지 못하고 이전 테스트 케이스에서 pending 됨
g_pHead = NULL;
}
void VerboseElement(void) {
USERDATA* pTemp = g_pHead;
while (pTemp != NULL) {
printf("[%p] %d %s %s [Next:%p]\n", pTemp, pTemp->age, pTemp->name, pTemp->phone, pTemp->pNext);
pTemp = pTemp->pNext;
}
}
void InitDummyData(void) {
AddElement(10, "Hoon", "010-1111-1111");
AddElement(20, "John", "010-2222-2222");
AddElement(30, "David", "010-3333-3333");
}
USERDATA* SearchElement(const char* pszName) {
USERDATA* pSearch = g_pHead;
// traverse
while (pSearch != NULL) { // pSearch->pNext로 바꾸면 Tail Node에 있는 데이터가 not found 처리됨
// check field
if (strcmp(pSearch->name, pszName) == 0) {
printf("\"%s\" Found in Linked-list Structure\n", pszName);
return pSearch;
}
// move to next node
pSearch = pSearch->pNext;
}
printf("\"%s\" Not Found in Linked-list Structure\n", pszName);
}
void SearchToRemove(USERDATA** ppPrev, const char* pszName) {
// 초기 상태는 Head 노드 부터
USERDATA* pCurrent = g_pHead;
USERDATA* pPrev = NULL;
// traverse
while (pCurrent != NULL) {
if (strcmp(pCurrent->name, pszName) == 0) {
*ppPrev = pPrev;
return;
}
pPrev = pCurrent;
pCurrent = pCurrent->pNext;
}
}
void RemoveElement(USERDATA* pPrev) {
// pPrev is null인 경우) 1.Head 노드도 null이어서 자료구조에 노드가 아예 없는경우 2.Head 노드를 제거할 경우
if (pPrev == NULL) {
// 1번 케이스
if (g_pHead == NULL) {
printf("!!! Empty Linked-List !!!\n");
return;
}
// 2번 케이스
USERDATA* pCurrent = g_pHead;
g_pHead = pCurrent->pNext;
printf("Remove element %s\n", pCurrent->name);
free(pCurrent);
}
else {
// 삭제할 노드가 Head 노드가 아닌 경우)
USERDATA* pCurrent = pPrev->pNext;
pPrev->pNext = pCurrent->pNext;
printf("Remove element %s\n", pCurrent->name);
free(pCurrent);
}
}
void SearchAndRemove(const char* pszName) {
USERDATA* pPrev = NULL;
// search
SearchToRemove(&pPrev, pszName);
// remove
RemoveElement(pPrev);
}
void TestCase01(void) {
// 데이터 조회
puts("------------Test case 01------------");
puts(">>>>>> 데이터 조회");
VerboseElement();
// 자료구조 아무것도 없을 때 제거하려고 하는 경우
SearchAndRemove("Hoon");
// 삭제 후 데이터 재조회
puts(">>>>>> 삭제 조치 후 데이터 조회");
VerboseElement();
// Release all data
ReleaseElements();
}
void TestCase02(void) {
// 데이터 삽입
AddElement(20, "John", "010-1111-1111");
// 데이터 조회
puts("------------Test case 02------------");
puts(">>>>>> 데이터 조회");
VerboseElement();
// 자료구조 아무것도 없을 때 제거하려고 하는 경우
SearchAndRemove("John");
// 삭제 후 데이터 재조회
puts(">>>>>> 삭제 조치 후 데이터 조회");
VerboseElement();
// Release all data
ReleaseElements();
}
void TestCase03(void) {
// 데이터 삽입
AddElement(20, "John", "010-1111-1111");
AddElement(30, "Tom", "010-2222-2222");
AddElement(40, "Zedd", "010-3333-3333");
// 데이터 조회
puts("------------Test case 03------------");
puts(">>>>>> 데이터 조회");
VerboseElement();
// 자료구조 아무것도 없을 때 제거하려고 하는 경우
SearchAndRemove("John");
// 삭제 후 데이터 재조회
puts(">>>>>> 삭제 조치 후 데이터 조회");
VerboseElement();
// Release all data
ReleaseElements();
}
void TestCase04(void) {
// 데이터 삽입
AddElement(20, "John", "010-1111-1111");
AddElement(30, "Tom", "010-2222-2222");
AddElement(40, "Zedd", "010-3333-3333");
// 데이터 조회
puts("------------Test case 04------------");
puts(">>>>>> 데이터 조회");
VerboseElement();
// 자료구조 아무것도 없을 때 제거하려고 하는 경우
SearchAndRemove("Tom");
// 삭제 후 데이터 재조회
puts(">>>>>> 삭제 조치 후 데이터 조회");
VerboseElement();
// Release all data
ReleaseElements();
}
void TestCase05(void) {
// 데이터 삽입
AddElement(20, "John", "010-1111-1111");
AddElement(30, "Tom", "010-2222-2222");
AddElement(40, "Zedd", "010-3333-3333");
// 데이터 조회
puts("------------Test case 05------------");
puts(">>>>>> 데이터 조회");
VerboseElement();
// 자료구조 아무것도 없을 때 제거하려고 하는 경우
SearchAndRemove("Zedd");
// 삭제 후 데이터 재조회
puts(">>>>>> 삭제 조치 후 데이터 조회");
VerboseElement();
// Release all data
ReleaseElements();
}
int main(void) {
TestCase01();
TestCase02();
TestCase03();
TestCase04();
TestCase05();
return 0;
}