Chapter 04. 연결 리스트의 개념적인 이해

주의 사항!

• 이 글은 제가 직접 공부하는 중에 작성되고 있습니다.
• 따라서 제가 이해하는 그대로의 내용이 포함됩니다.
• 따라서 이 글은 사실과는 다른 내용이 포함될 수 있습니다.

이번 Chapter에서도 리스트에 대한 이야기를 이어갑니다. 다만 리스트의 특성을 설명하는 것이 아니라 '연결'을 기반으로 하는 다른 리스트의 구현 방법에 대해서 설명합니다.

---

다음 예제를 시작으로 '연결 리스트'에서의 '연결'이 의미하는 바의 설명을 진행하겠습니다.

//main.c 소스 파일로 저장
#include <stdio.h>

int main(void)
{
	int arr[10];
	int readCount = 0;
	int readData;
	int i;

	while (1)
	{
		printf("자연수 입력 : ");
		scanf("%d", &readData);
		if (readData < 1) break;

		arr[readCount++] = readData;
	}

	for (i = 0; i < readCount; i++)
	{
		printf("%d ", arr[i]);
	}

	return 0;
}

/*
실행결과

자연수 입력 : 1
자연수 입력 : 2
자연수 입력 : 3
자연수 입력 : 4
자연수 입력 : 0
1 2 3 4

*/

위 예제는 0이하의 값이 입력될 때까지 입력이 계속됩니다. 즉, 0이하의 값을 입력하지 않으면 끊임없이 입력을 받게 됩니다. 그런데 문제는 입력 받은 값들을 배열에 저장하는데 배열의 크기가 10개 밖에 마련되지 않았다는 것입니다. 따라서 입력되는 값이 10개를 넘어서면 허용된 배열 범위를 벗어나서 값을 저장하게 되는 불상사가 일어나게 됩니다.

 

이렇듯이 정적인 배열은 필요로 하는 메모리 크기에 유연하게 대처하지 못합니다. 그래서 등장한 것이 '동적인 메모리의 구성'입니다. 이것이 무엇인지 다음 예제를 통해서 보이겠습니다.

//main.c 소스 파일로 저장
#include <stdio.h>
#include <stdlib.h>

typedef struct Node
{
	int data;
	struct Node* next;
} Node;

int main(void)
{
	Node* head = NULL;
	Node* tail = NULL;
	Node* cur = NULL;

	Node* newNode = NULL;
	int readData;

	//데이터를 입력 받는과정
	while (1)
	{
		printf("자연수 입력 : ");
		scanf("%d", &readData);

		if (readData < 1) break;

		//노드의 추가과정
		newNode = (Node*)malloc(sizeof(Node));
		newNode->data = readData;
		newNode->next = NULL;

		if (head == NULL) head = newNode;
		else tail->next = newNode;

		tail = newNode;
	}
	printf("\n");

	//입력 받은 데이터의 출력과정
	printf("입력 받은 데이터의 전체출력!\n");
	if (head == NULL) printf("저장된 자연수가 존재하지 않습니다.\n");
	else
	{
		cur = head;
		printf("%d ", cur->data);

		while (cur->next != NULL)
		{
			cur = cur->next;
			printf("%d ", cur->data);
		}
	}
	printf("\n\n");

	//메모리의 해체 과정
	if (head == NULL) return 0;
	else
	{
		Node* delNode = head;
		Node* delNextNode = head->next;

		printf("%d을(를) 삭제합니다.\n", head->data);
		free(delNode);

		while (delNextNode != NULL)
		{
			delNode = delNextNode;
			delNextNode = delNextNode->next;

			printf("%d을(를) 삭제합니다.\n", delNode->data);
			free(delNode);
		}
	}

	return 0;
}

/*
실행결과

자연수 입력 : 1
자연수 입력 : 2
자연수 입력 : 3
자연수 입력 : 4
자연수 입력 : 5
자연수 입력 : 6
자연수 입력 : 0

입력 받은 데이터의 전체출력!
1 2 3 4 5 6

1을(를) 삭제합니다.
2을(를) 삭제합니다.
3을(를) 삭제합니다.
4을(를) 삭제합니다.
5을(를) 삭제합니다.
6을(를) 삭제합니다.

*/

위 예제를 보면 값을 입력 받을 때마다 newNode를 생성하고, 이전에 생성된 노드가 다음 노드를 가리키도록 하면서 마치 기차와 같이 리스트를 구축하고 있습니다. 새로운 값이 입력될 때마다 기차 칸을 한 칸씩 추가하는 것, 연결시키는 것과 같기 때문에 이런 형태를 보고 연결 리스트라고 부르는 것이 아닌가 생각합니다.

 

위 예제에 대해 이해가 잘 가지 않는 부분이 있다면 언제든지 댓글로 물어봐주시기 바랍니다.

---

위 예제를 통해서 연결리스트가 무엇을 의미하는지 나름의 이해를 갖추었을 것입니다. 그러나 이러한 방식의 학습은 적절하지 않다고 이 책의 저자는 말합니다. 대표적인 이유 두 가지는 다음과 같습니다.

• 연결 리스트의 추상 자료형(ADT)을 정의하지 않았습니다.
• 삽입, 삭제, 조회의 기능이 별도의 함수로 구분되어 있지 않습니다.

두 번째 이유는 어떻게 보면 첫 번째 이유에서 파생되었다고 생각합니다. 사실 추상 자료형의 정의는 어렵지 않으니 별 것 아니라고 생각할 수도 있습니다. 하지만 신경 쓰지 않으면 자료구조에 대한 잘못된 이해를 갖게 될 수도 있습니다. 자료구조를 제대로 공부하려면 가급적 다음의 세가지 순서를 지켜야 한다고 저자는 말합니다.

1. 자료구조의 추상 자료형 정의
2. 정의한 추상 자료형 구현
3. 구현이 완료된 자료구조의 활용

위의 과정을 모두 밟지 않으면, 특히 추상 자료형의 정의를 생략하면 구현도 활용도 이상한 형태로 흘러가기 쉽습니다.