이 포스팅은 윤성우 님의 열혈 자료구조를 기반으로 합니다.

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

먼저 연결 리스트를 배우기에 앞서서 배열 기반 리스트를 살펴보면 배열은 길이의 변경이 불가능하다는 것을 알 수 있다.
따라서 이러한 문제점을 해결한 게 연결 리스트(Linked List) 이다. 먼저 다음의 구조체를 살펴보자.

이 Node 구조체를 이용하여 필요할 때마다 하나씩 동적 할당하여 데이터를 저장하고 이들을 배열처럼 연결할 수 있는
연결 리스트가 되는 것이다. 여기에서 구조체 Node 변수를 노드라 하며 이를 그림으로 그리면 다음과 같다.

먼저 ADT를 살펴보자. ADT는 다음과 같다.

배열 리스트와 비교해보면 SetSortRule함수가 추가된 것을 볼 수 있으며 이는 Head에 추가할지 Tail에 추가할지 정하는 것이다. 장단점은 각각 다음과 같다.

또한 SetSortRule 함수의 매개변수를 보면 함수 포인터가 매개변수로 존재하는 것을 알 수 있는데 반환형이 int, LData형 2개를 전달받는 함수의 주소 값을 전달하는 것이다. 예를 들면 다음의 함수의 주소 값이 매개변수로 전달될 수 있다.

먼저 다음의 형태의 기본적인 노드의 연결 상태를 보고 단점을 파악해보자.

이 경우 노드의 추가 및 삭제 또는 조회의 방법에서 첫 번째 노드와 두 번째 노드의 연결에 차이가 있다. 따라서 이를 방지하기 위해 헤드의 바로 다음에 dummy node를 넣어 어떤 위치에 있던 방법을 일관화 할 수 있다.

이제 연결 리스트를 구현해보자. 다음의 구조체를 기반으로 정의한다.

헤더 파일은 다음과 같다.

<DLinkedList.h>

이를 기준으로 초기화와 삽입을 살펴보자. 초기화는 다음과 같다.

노드를 새로 추가하기 위한 함수는 다음과 같다.

여기에서 볼 수 있는 것은 comp 즉 노드를 정렬하기 위한 기준이 마련되어있느냐에 따라 FInsert, SInsert로 나뉜다는 것이다. 그러나 이들은 내부적으로 정의된 함수이기에 사용자가 직접 호출할 수 없는 함수이다.

먼저 FInsert는 다음과 같다.

그림으로 보면 다음과 같다.

데이터 조회 역시 배열 리스트의 그것과 비슷하지만 before과 Dummy node가 존재한다는 것에서 차이가 있다.
먼저 LFirst 함수를 보자.

역시 그림으로 나타내면 다음과 같다.

LNext 역시 보면 다음과 같다.

역시 그림으로 나타내면 다음과 같다.

노드의 삭제 역시 배열 기반 리스트의 삭제와 비슷하다.

전체의 코드는 각각 다음과 같다.
<DLinkedList.h>

<DLinkedList.c>

<DLinkedListMain.c>

원형 연결 리스트 (Circular Linked List)

단순 연결 리스트에서 마지막 노드가 첫 번째 노드를 가리켜서 원의 형태로 연결이 된 리스트를 원형 연결 리스트 라고 한다. 이를 그림으로 나타내면 다음과 같다.

위의 그림에서 head나 tail에 새로운 노드 1을 추가한다고 가정하면 1 -> 2 -> 4 -> 6 -> 8 -> 1 .... 의 형태 혹은
2 -> 4 6 -> 8 -> 1 -> 2.... 즉 서로 같은 형태가 되므로 head, tail의 구분이 명확히 존재하지 않는다.
유일한 차이점은 tail이 가리키는 노드가 다르다는 것 이다. 따라서 이를 머리에 추가하는 함수, 꼬리에 추가하는 함수는 각각 다음과 같다.

void LInsert(List* plist, Data data) { // tail에 추가
	Node* newNode = (Node*)malloc(sizeof(Node));
	newNode->data = data;

	if (plist->tail == NULL) { // 비어있는 경우
		plist->tail = newNode;
		newNode->next = newNode;
	}
	else {
		newNode->next = plist->tail->next; // 새 노드와 기존에 저장된 노드 연결
		plist->tail->next = newNode; // 기존 노드의 tail이 새 노드를 가리키게 연결
		plist->tail = newNode; // tail이 새로 추가된 노드를 가르키게 함
	}
	(plist->numOfData)++;
}

void LInsertFront(List* plist, Data data) { // Head에 추가
	Node* newNode = (Node*)malloc(sizeof(Node));
	newNode->data = data;

	if(plist->tail == NULL) { // 비어있는 경우
		plist->tail = newNode;
		newNode->next = newNode;
	}
	else {
		newNode->next = plist->tail->next; // 새 노드와 기존에 저장된 노드 연결
		plist->tail->next = newNode; // 기존 노드의 tail이 새 노드를 가르키게 연결
	}
	(plist->numOfData)++;
}

이번에는 조회를 살펴보자. 조회의 경우도 Fisrt, Next즉 두가지의 경우에 대한 함수가 존재한다.
LFisrt의 경우 Head가 없기 때문에 tail이 가리키는 다음 노드를 Cur로 한 뒤 이를 반환한다. 그림으로 표현하면 다음과 같다.

int LFirst(List* plist, Data* pdata) {
	if (plist->tail == NULL) { // 비어있는 경우
		return FALSE;
	}
	plist->before = plist->tail; // before가 tail을 가리키게 한다.
	plist->cur = plist->tail->next; // cur이 tail의 다음을 가리키게 한다

	*pdata = plist->cur->data; 
	return TRUE;
}

LNext의 경우도 단순히 before가 cur을 가리키게 하고 cur에 cur이 가리키는 다음 노드를 가리키게 하면 된다.
그 후 cur이 가리키는 노드를 반환하면 된다.마찬가지로 그림으로 나타내면 다음과 같다.

int LNext(List* plist, Data* pdata) {
	if (plist->tail == NULL) { // 비어있는 경우
		return FALSE;
	}
	plist->before = plist->cur; // before가 cur을 가리키게 한다
	plist->cur = plist->cur->next; // cur이 cur의 다음을 가리키게 한다.

	*pdata = plist->cur->data;
	return TRUE;
}

이 두가지 함수 모두 리스트에 원소가 없을 경우에 대해서 처리가 필요한데 단순하게 ADT를 참조하여 노드가 존재하지 않으면 False를 반환하면 된다.

이번에는 노드의 삭제에 대해서 알아보자.
노드의 삭제의 경우 두가지의 경우가 존재하는데 삭제할 노드가 tail인 경우 또는 아닌경우 삭제할 노드가 tail인 경우
노드가 하나밖에 없는 경우 역시 추가로 고려를 해주어야 한다. 다음의 코드를 살펴보자.

Data LRemove(List* plist) {
	Node* rpos = plist->cur;
	Data rdata = rpos->data;

	
	if (rpos == plist->tail) { // 삭제하려는 노드가 tail인 경우
		if (plist->tail == plist->tail->next) { // 노드가 하나인 경우
			plist->tail == NULL;
		}
		else {
			plist->tail = plist->before;
		}
	}

	plist->before->next = plist->cur->next;
	plist->cur = plist->before;
	
	free(rpos);
	(plist->numOfData)--;
	return rdata;
}

위에서 볼 수 있듯 삭제하려는 노드가 tail이 아닌 경우는 다음의 그림처럼 삭제를 진행하면 된다.

 그러나 삭제하려는 노드가 tail인 경우는 단순하게 tail을 하나 앞으로 이동시키면 된다.

단순히 plist->tail = plist->before;을 통해서 말이다.

전체의 코드는 각각 다음과 같다.
<CLinkedList.h>

<CLinkedList.c>

<CLinkedListMain.c>

양방향 연결 리스트

양방향 연결 리스트의 경우 앞서서 구현했던 단순 연결 리스트에서 좌측 혹은 우측을 연결하는 포인터 변수의 존재가 큰 차이점 이다. 그렇다면 헤더파일과 그림을 보고 양방향 연결 리스트를 구현해보자. 헤더파일은 다음과 같다.

#ifndef __DB_LINKED_LIST_H__
#define __DB_LINKED_LIST_H__

#define TRUE	1
#define FALSE	0

typedef int Data;

typedef struct _node
{
	Data data;
	struct _node * next;
	struct _node * prev;
} Node;

typedef struct _dbLinkedList
{
	Node * head;
	Node * cur;
	int numOfData;
} DBLinkedList;

typedef DBLinkedList List;

void ListInit(List * plist);
void LInsert(List * plist, Data data);

int LFirst(List * plist, Data * pdata);
int LNext(List * plist, Data * pdata);
int LPrevious(List * plist, Data * pdata);

int LCount(List * plist);

#endif

리스트의 초기화는 각각의 포인터 변수를 NULL로 초기화 하면 된다. 다음과 같다.

void ListInit(List* plist) {
	plist->head = NULL;
	plist->cur = NULL;
	plist->numOfData = 0;
}

삽입의 경우 2가지의 경우가 존재하는데 각각 리스트가 비어있을때, 비어있지 않을 때 이다.
이를 코드로 작성하면 다음과 같다.

void LInsert(List* plist, Data data) {
	Node* newNode = (Node*)malloc(sizeof(Node));
	newNode->data = data;

	newNode->next = plist->head;
	newNode->prev = NULL;
	plist->head = newNode;

	(plist->numOfData)++;
}

데이터의 조회의 경우 양방향 연결 리스트의 특성으로 좌측, 우측을 모두 조회할 수 있다.
이를 함수료 표현하면 각각 LFisrt, LNext, LPrevious 이며 다음과 같다.

int LFirst(List* plist, Data* pdata) {
	if (plist->head == NULL)
		return FALSE;

	plist->cur = plist->head;
	*pdata = plist->head->data;
	return TRUE;
}

int LNext(List* plist, Data* pdata) {
	if (plist->head == NULL)
		return FALSE;

	plist->cur = plist->cur->next;
	*pdata = plist->cur->data;
	return TRUE;
}

int LPrevious(List* plist, Data* pdata) {
	if (plist->head == NULL)
		return FALSE;

	plist->cur = plist->cur->prev;
	*pdata = plist->cur->data;
	return TRUE;
}

전체의 코드는 각각 다음과 같다.
<DBLinkedList.h>

<DBLinkedList.c>

<DBLinkedListMain.c>

함수의 인자로 배열 전달

함수 호출시 전달되는 인자의 값은 매개변수에 복사가 되는 형태이다. 즉 int Func(int number); Func(num); 이라는 문장이 있다면 실제의 num값이 아닌 num에 저장된 값이 number에 복사가 되는 것이다. 그렇다면 Func 함수 내부에서 number값을 하나 증가 혹은 감소시키면 num은 어떻게 될까?

정답은 아무 상관이 없다 이다. 이유는 두 변수는 서로 다른 변수이기 때문이다. 

그렇다면 배열을 인자로 전달하려면 어떻게 해야 할까? 바로 주소값을 알려주면 되는 것이다.

int arr[3] = {1, 2, 3}; 다음의 형태로 저장된 배열이 있다면 Func(arr); 의 형태로 배열의 주소 값을 전달하면 되는 것이다. 앞에서 배열의 이름은 주소 값이라는 것을 배웠기 때문에 가능한 일이다. 다음의 예시를 통해 함수의 매개변수로 배열을 인자로 전달하는 형태를 살펴보자.

<소스코드>

Call by value와 Call by reference

함수의 호출에는 두가지 방식이 존재한다. 바로 값에 의한 호출, 참조에 의한 호출이 그것이다. 기존에 배웠던 함수들의 대부분은 Call by value 였다. 그렇다면 Call by reference는 왜 존재하는 것일까? 다음의 예시를 통해 알아보자.

<소스코드>

<실행결과>

먼저 SwapByValue 함수를 호출한 경우 main함수의 n1, n2가 그대로인 것을 확인할 수 있다. 이는 이 포스팅의 맨 처음 부분에 나왔던 number값을 증가시켜도 num값은 변화하지 않는 것과 동일한 이유 때문이다. 따라서 SwapByReference 방식을 이용한 즉 Call By Reference 방식을 이용하여 주소 값을 통해 접근하게 해야 main 함수에서도 변경이 될 수 있는 것이다. 이를 그림으로 표현하면 다음과 같다.

위의 그림에서 볼 수 있듯이 call by value와 다르게 call by reference의 경우 주소값을 통해 함수 내부에서 main영역에 있는 변수에 접근할 수 있다.

배열의 이름은 포인터 

배열의 이름은 포인터이며 값을 변경할 수 없는 상수 형태의 포인터이다. 다음 코드를 보자.

<실행결과>

위의 코드와 실행결과를 통해 배열 arr가 int형 이므로 각각 4바이트씩 주소 값의 차이가 나는 것을 볼 수 있으며 모든 배열 요소가 메모리 공간에 나란히 할당된다는 것을 알 수 있다. 또한 배열의 이름의 주소 값이 010FFB88이고 배열의 첫 번째 원소의 주소 값이 010FFB88로 동일한 것을 알 수 있다.

또한 배열의 이름은 대입 연산자의 피연산자가 될 수 없으므로 다음과 같이 정리할 수 있다.

배열의 이름은 배열의 시작 주소 값을 의미하며, 그 형태는 값의 저장이 불가능한 상수이다.

즉 배열의 이름은 상수형태의 포인터이다. 따라서 배열의 이름을 "포인터 상수"라고 부른다.

결국 배열의 이름은 포인터 이므로 * 연산자를 사용할 수 있다.

<소스코드>

<실행결과>

*연산자를 통해 6번 라인에서 *arr을 출력하는 것을 알 수 있다. 이 경우 배열의 첫 번째 원소가 출력이 된다.

또한 7번 라인을 통해 배열의 첫 번째 원소에 접근하여 100을 더하여 101로 변경이 된 것을 확인할 수 있다.

포인터를 대상으로 하는 증가 감소 연산

먼저 다음의 예제를 먼저 살펴보자.

int* ptr1 = 0x0010;

이 경우 ptr1++;를 하게 되면 0x0011이 아니라 int형이므로 4byte가 증가하여 0x0014가 된다.

double* ptr2 = 0x0010;

이 경우 ptr2++;를 하게 되면 0x0011이 아니라 double형이므로 8byte가 증가하여 0x0018이 된다.

즉 이를 일반화하면 type형 포인터를 대상으로 n의 크기만큼 증가 혹은 감소 시 n*sizeof(type)의 크기만큼 증가 혹은 감소한다는 것을 알 수 있다.

결론

그래서 우리는 중요한 사실을 유도할 수 있는데 바로 arr[i] == *(arr + i) 라는 것이다.

arr + i 는 arr의 type만큼 주소 값이 증가하기 때문에 arr [i]라는 것이다. 이것은 매우 중요하므로 잘 기억해야 한다.

예제

길이가 5인 int형 배열 arr을 선언하고 이를 1, 2, 3, 4, 5로 초기화 한 다음 이 배열의 첫 번째 요소를 가리키는 포인터 변수 ptr을 선언한다. 그다음 포인터 변수 ptr에 저장된 값을 증가시키는 형태의 연산을 기반으로 포인터 변수 ptr에 저장된 값을 변경시키지 않고 값을 3씩 증가시키고, 정상적으로 증가가 이루어졌는지 확인하는 예제를 작성해보자. (출처 윤성우 님의 열혈 C 프로그래밍 chapter 13 p.299 문제 1)

<소스코드>

<실행결과>

상수 형태의 문자열을 가리키는 포인터

문자열을 표현하는 방식에는 2가지가 있다.

1. 배열을 기반으로 하는 문자열 - char str[] = "Hello world!";
2. 포인터를 이용하는 문자열 - char * str = "Hello world!";

이를 그림으로 표현하면 다음과 같다.

배열을 기반으로 하는 문자열은 변경이 가능하다. 그렇지만 포인터를 이용하는 문자열은 변경이 불가능하다.  사실상 배열 형태의 str, 포인터 변수 str 모두 첫 문자 H의 주소 값을 가리키긴 하지만 배열 str은 다른 것을 가리킬 수 없는 반면에 포인터 변수 str은 다른 위치를 가리킬 수 있다. 다시 말하면

char * str = "Hello world!";

str = "Bye~";

로 변경이 가능하다는 뜻 이다. 예시를 통해 살펴보자.

<실행결과>

포인터 배열

포인터 변수로 이루어져 주소 값의 저장이 가능한 배열이 포인터 배열이고 선언방식은 다음과 같다.

int * arr1[20]; // 길이가 20인 int형 포인터 배열 arr1

dounle * arr2[10]; // 길이가 10인 double형 포인터 배열 arr2

예제는 다음과 같다.

1 2 3 4 5 6 7 8 9 10 11

#include <stdio.h>   int main(void) {     int num1 = 10, num2 = 20, num3 = 30;     int* arr[3] = { &num1, &num2, &num3 };       for (int i = 0; i < 3; i++) {         printf("%d\n", *arr[i]);     }     return 0; } Colored by Color Scripter

cs

<실행결과>

 

이를 그림으로 표현하면 다음과 같다.

이는 다음의 형태로 문자열을 저장할 수도 있다. 위와 비슷하게 예시 코드를 보자.

<실행결과>

C에서 어려운 포인터입니다. C는 low-level 언어라고 하는데 바로 이 포인터를 이용해 메모리에 직접 접근이 가능하기 때문에 low-level 언어라고 불립니다. 그렇다면 이 포인터는 과연 어떤 것일까요?

int num = 10; 즉 변수 num의 경우 int형이므로 4바이트가 메모리에 저장이 된다. 이 메모리의 주소 값을 임의로 0x123456부터 시작한다고 가정해보자. 이때 이 0x123456이라는 번지를 주소 값이라고 한다. 이 주소 값 역시 저장할 수 있는 값이며 포인터 변수는 메모리의 주소 값을 저장하기 위한 변수이다.

포인터 변수의 선언

이 포인터 변수의 선언은 매우 간단하다. 다음을 보자

int * pnum; // int 형 변수를 가리키는 포인터 변수 pnum

double * pnum2; // double 형 변수를 가르키는 포인터 변수 pnum2

float * pnum3; // float 형 변수를 가르키는 포인터 변수 pnum3

즉 저장하고자 하는 변수의 형에 따라 포인터 변수의 형 역시 정해진다.

& 연산자

& 연산자는 피연산자의 주소 값을 반환하는 연산자이다. 이를 다음의 예시를 통해 살펴보면 다음과 같다.

이때 변수의 형과 포인터 변수의 형은 일치해야 한다. 즉 다음의 경우는 오류가 발생할 수 있다.

* 연산자

* 연산자는 포인터가 가리키는 메모리 공간에 접근할 때 사용하는 연산자이다. 다음을 보자. 주석이 그 의미이다.

*pnum = 20; // 포인터 변수 pnum이 가리키는 메모리 공간인 변수 num에 int 값 20을 저장하라

printf("%d", *pnum); // 포인터 변수 pnum이 가리키는 메모리 공간인 변수 num에 저장된 값을 출력하라

예시를 통해 살펴보자

<소스코드>

<실행결과>

위의 결과를 그림으로 그려보면 다음과 같다.

예제

int형 변수 num1, num2를 선언과 동시에 각각 30, 20으로 초기화하고 int형 포인터 변수 ptr1, ptr2를 선언하여 각각 num1, num2를 가리키게 하자. 그 후 ptr1과 ptr2를 이용하여 num1의 값을 10 증가시키고, num2의 값을 10 감소시키자. 이제 두 포인터 변수 ptr1과 ptr2가 가리키는 대상을 서로 바꾸고 ptr1과 ptr2가 가리키는 변수에 저장된 값을 출력하라

<실행결과>

배열이란?

배열이란 둘 이상의 변수를 모아 놓은 것이다. 배열의 선언 방식은 다음과 같다.

위에서 볼 수 있듯이 int arr[10]; 이면 자료형이 int, 배열의 이름이 arr, 배열의 길이가 10이라는 것을 말하는 것이다.

위에서 볼 수 있듯이 int arr[10]; 이면 자료형이 int, 배열의 이름이 arr, 배열의 길이가 10이라는 것을 말하는 것이다.

또한 특징이 있는데 배열의 시작은 0부터 시작한다는 것이다. 따라서 위의 길이가 10인 배열의 경우 0번째 원소부터 9번째 원소까지 존재한다.

배열의 가장 큰 장점이 존재하는데 바로 반복문을 이용하여 순차적으로 접근이 가능하다는 점이다. 이것을 예시를 통해 알아보자.

배열의 선언과 동시에 초기화

배열의 초기화의 방법은 총 3가지가 존재한다. 다음을 통해 알아보자.

1. int arr[5] = {1, 2, 3, 4, 5}; // 차례차례 초기화
2. int arr1[ ] = {1, 2, 3, 4, 5}; // 컴파일러에 의해서 자동으로 길이 5가 채워진다
3. int arr3[5] = {1, 2};  // 3, 4, 5 번째 요소는 자동으로 0으로 채워진다.

배열의 길이를 구하는 sizeof() 함수

배열의 길이를 따로 명시하지 않더라도 sizeof 함수를 통해 알 수 있다. 먼저 일반적인 배열 int arr[5] = {1, 2, 3, 4, 5};를 생각해보면 int형이므로 한 요소당 4byte씩 총 20byte이다. 따라서 sizeof(arr);는 20byte이다. 이를 int의 크기 4byte로 나누면 5 즉 배열의 길이를 구할 수 있다. 따라서 배열의 길이는 int len = sizeof(arr) / sizeof(int);로 구할 수 있다. 예시를 보면 다음과 같다.

<소스코드>