JArchive 프로그래밍 일기

링크드 리스트란

링크드 리스트는 '노드(마디)를 연결해서 만드는 리스트'입니다. 

노드는 데이터를 저장하는 필드'와, 다음 노드와의 연결 고리 역할을 하는 '포인터'로 이루어져 있습니다. 

노드 구조체 

노드 하나는 다음과 같은 구조체로 나타낼 수 있습니다. 

struct 키워드 없이 인스턴스를 만들기 위해, typedef 키워드로 Node 구조체를 정의합니다. 

typedef struct Node
{
    int data; /* 데이터 필드 */
    struct Node* nextNode;  /*다음 노드를 가리키는 포인터*/
}Node;

자유 저장소에 메모리 할당하기

C언어로 작성된 프로그램은 세 가지 종류의 메모리 영역을 가집니다. 

정적 메모리(Static Memory) : 전역 변수나 정적 변수 등이 저장됩니다. 프로그램이 종료될 때 해제됩니다. 

자동 메모리(Automatic Memory) : 스택 구조로 이루어져 있어 코드블록( {와 }의 괄호) 범위 내에서 저장되었다가 제거됩니다.
블록이 끝나는 곳에서 자동으로 메모리를 해제합니다. 

자유 저장소(Free Store) : 프로그래머가  malloc()과 free()함수를 이용하여 직접 메모리를 할당하고 해제 합니다. 

자유 저장소에 메모리를 할당하려면 malloc 함수를 이용합니다. 

Node* NewNode = (Node*)malloc(sizeof(Node));

void * malloc(size_t size);

malloc() 함수의 반환형인 void*는 어느 자료형의 주소도 가리킬 수 있습니다. 

따라서 Node*형의 주소를 가리키라고 명시를 해줍니다.

(Node*)malloc(데이터의 크기)

노드 생성 

다음은 노드를 생성하는 함수 CreateNode 입니다. 

malloc으로 메모리를 할당하고, 

데이터를 저장하고, 

다음 노드에 대한 포인터를 NULL로 초기화 합니다. 

할당 받은 메모리의 주소를 리턴합니다. 

/* 노드 생성 */
Node* CreateNode(int data) {

	Node* newNode = (Node*)malloc(sizeof(Node));
	newNode->data = data;
	newNode->nextNode = NULL;

	return newNode;
}

노드를 메모리에서 해제하기 

메모리 해제 함수인 free(노드의포인터)는 DeleteNode() 함수내에서 처리합니다. 

노드 추가 

노드 추가 연산은 테일 노드 뒤에 새 노드를 만들어 연결하는 것입니다. 

(맨 뒤의 노드를 테일tail 노드, 리스트 맨 앞의 노드가 헤드head 노드 입니다.)

일단, 테일이 어디인지 계속 포인터를 따라가 봐야 합니다. 

헤드노드가 없으면(== 리스트가 비었다면), 추가한 노드가 헤드가 됩니다. 

다음은 노드를 추가하는 AppendNode 함수 입니다. 

주의 할 점! 
list 포인터의 주소를 넘겨야 하므로, (주소의 주소가 필요하므로)
노드를 추가하는 함수를 정의할 때, 헤드 노드의 매개변수는 **Node가 되어야 합니다.

/* 노드 추가. 테일 노드 찾아서 그 뒤에 새 노드를 붙인다 */
void AppendNode(Node** head, Node* newNode) {

	/* 리스트가 비었다면 헤드에 뉴 노드 */
	if (NULL == (*head)) {
		(*head) = newNode;
	}
	else { // 헤드부터 시작해서 테일을 찾아냄
		Node* tail = (*head);

		while (NULL != tail->nextNode) { // 다음노드가 NULL인 것이 테일
			tail = tail->nextNode;
		}

		tail->nextNode = newNode;
	}
}

노드를 생성하고 추가하는 코드 예시입니다. 

int main() {
	Node* list = NULL;
	Node* newNode = NULL;

	newNode = CreateNode(10);   /* 자유 저장소에 노드 생성 */
	AppendNode(&list, newNode);

	return 0;
}

왜 Node** head 일까? Node* head 가 아니라. 

List라는 포인터변수가 위치하는 메모리 주소를 넘겨야 그 List 변수 안에 newNode라는 주소를 할당할 수 있습니다. 

포인터변수의 주소는 '포인터의 포인터' 입니다. 그래서 Node** head를 넘겨야 합니다.  

포인터변수 안의 '값'을 알고 싶다면,  포인터 변수 Node* head를 넘기면 됩니다.

그러나, 포인터변수 그 자체의 '값'을 할당 하려면, 변수의 위치(==주소)를 알아야 합니다. 

( 포인터 변수의 위치 == 포인터 변수의 주소 == 포인터의 포인터 )

노드 탐색 

링크드 리스트는 인덱스를 이용하는 배열과는 다르게, 헤드 노드부터 차근차근 탐색해야만 임의의 위치의 노드를 찾을 수 있습니다. 

(이것은 리스트의 약점 중 하나)

다음은 특정 위치를 입력하여 그 위치의 노드의 주소를 반환하는 GetLocation함수 입니다. 

Node* GetLocation(Node* head, int location) {

	printf("%d번째 노드를 찾아보자. \n", location);

	Node* current = head;

	while ((NULL != current) && (--location) >= 0) {
		printf("location : %d 번째 탐색 \n", location);
		current = current->nextNode;

	}

	return current;
}

탐색 할때는 헤드만 알면 됩니다. 헤드는 첫 노드의 주소를 알고 있기 때문입니다.  

사용 예시입니다. 

노드 3개가 들어있는 리스트를 만들고, 

1번째 노드 위치를 찾습니다. 이때, 인덱스 0을 찾도록 합니다. 

int main() {
	Node* list = NULL;
	Node* targetNode = NULL;

	/* 자유 저장소에 노드를 생성하여 List에 추가  */
	AppendNode(&list, CreateNode(100));
	AppendNode(&list, CreateNode(200));
	AppendNode(&list, CreateNode(300));

	// 2번째 노드를 찾으려면, 1을 입력. 
	// 1번째 노드를 찾으려면, 0을 입력.
	targetNode = GetLocation(list, 0);
	printf("[탐색 결과] TargetNode의 Data : %d\n", targetNode->data);

	return 0;
}

탐색에서 유의할 점은 노드의 인덱스 입니다.

2번째 노드를 찾더라도, 실제로 GetLocation()함수에 넘겨줘야할 숫자는 1입니다. 

GetLocation 함수의 location는 while문 조건 내부에서 (--location) 으로 쓰입니다. 

location이 0인 0번째 노드는 head인 current 이기 때문입니다. 

이미 head가 0번째 노드 입니다. 

while문에서 조건을 비교할 순간에는, location이 1이 되어야 합니다. (그리고 location은 0 또는 0보다 커야 합니다.)

리스트 순회 

노드가 제대로 삽입됬는지 확인하기 위해, '리스트 내의 모든 노드를 순회하는 함수'를 만들었습니다. 

void PrintList(Node* head) {

	Node* tempNode = head;
	int count = 0;

	while (NULL != tempNode) {
		printf("%5d", tempNode->data);
		tempNode = tempNode->nextNode;
		count++;
	}
	printf("\n");
	printf("%5d개의 노드가 있습니다.\n", count);
}

printf() 내의 %5d는 5칸의 공백을 두고 integer를 출력하는 코드입니다. 

마지막에는 '총 노드 개수'를 출력했습니다. 

노드 삭제 

노드 삭제 연산은 특정 위치의 노드를 삭제합니다. 

특정 위치는 current 노드의 다음 노드라고 가정하고 target을 찾습니다. 

삭제할 target 노드를 찾고, 그

노드의 앞 노드(current)가 삭제할 노드의 다음 노드(target->nextNode)를 가리키도록 이어주면 됩니다. 

마지막으로 free() 함수로 타겟노드를 메모리에서 해제합니다. 

RemoveNode()는 다음과 같습니다. 

void RemoveNode(Node** head, Node* target) { 

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

	// 헤드가 타겟이면
	if ((*head) == target) {
		(*head) = (*head)->nextNode;
	}
	else {
		// 현재의 다음노드가 타겟인지 검사하며 탐색  
		Node* current = (*head);

		while ((current->nextNode != target) && (NULL != current)) {
			current = current->nextNode;
		}

		// 현재의 다음이 타겟이므로. 현재와 '타겟의 다음'을 이어준다.
		current->nextNode = target->nextNode;
	}

	free(target);
}

아래는 노드 추가, 탐색, 삭제 예시입니다. 

int main() {
	Node* list = NULL;
	Node* targetNode = NULL;

	/* 자유 저장소에 노드를 생성하여 List에 추가  */
	AppendNode(&list, CreateNode(100));
	AppendNode(&list, CreateNode(200));
	AppendNode(&list, CreateNode(300));

	// 리스트 전체 출력 
	PrintList(list);

	// 2번째 노드를 찾으려면, 1을 입력. 
	// 1번째 노드를 찾으려면, 0을 입력.
	targetNode = GetLocation(list, 0);
	printf("[탐색 결과] TargetNode의 Data : %d\n", targetNode->data);

	// 1번째 노드(인덱스 0) 을 삭제 
	RemoveNode(&list, targetNode);

	// 리스트 전체 출력 
	PrintList(list);
	
	return 0;
}

모든 노드 삭제 

리스트 헤드 노드 주소를 파라미터로 넘기면, 모든 노드를 삭제하는 RemoveAll()함수입니다. 

void RemoveAll(Node** head) {
	printf("리스트 전체를 삭제 \n");

	Node* tempNode = (*head);

	while (NULL != tempNode) {
		// 헤드 갱신해두고 
		(*head) = tempNode->nextNode;
		// tempNode를 메모리 해제 
		free(tempNode);
		// 헤드 주소를 다시 tempNode에 저장 
		tempNode = (*head);
	}
}

특정 노드 뒤에 삽입

일단 새 노드를 만듭니다. 

특정 노드를 기준으로, 새 노드가 특정 노드의 다음 노드를 가리키도록 하고, 특정 노드는 새 노드를 가리키게 합니다. 

다음은 InsertAfter() 함수 입니다. 

/* 노드 삽입. 특정 위치 뒤에 삽입 */
void InsertAfter(Node* current, Node* newNode) {
	
	newNode->nextNode = current->nextNode;
	current->nextNode = newNode;
}

특정 노드 앞에 삽입

다음은 InserBefore() 함수 입니다. 

/* 노드 삽입. 특정 위치 앞에 삽입 */
void InsertBefore(Node** head, Node* current, Node* newNode) {
	printf("[InsertBefore] %d를 삽입합니다. \n", newNode->data);

	Node* tempNode = (*head);

	if (tempNode == current) {
		// 헤드 노드앞에 뉴 노드 
		newNode->nextNode = tempNode;
		(*head) = newNode;		
	}
	else {

		while (tempNode->nextNode != current) {
			tempNode = tempNode->nextNode;
		}
		//tempNode 다음이 current인 상태.
		newNode->nextNode = current;
		tempNode->nextNode = newNode;
	}
}

전체 코드입니다.

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


/* 노드 선언 */
typedef struct Node {
	int data;
	struct Node* nextNode;
}Node;

/* 노드 생성 */
Node* CreateNode(int data) {

	Node* newNode = (Node*)malloc(sizeof(Node));
	newNode->data = data;
	newNode->nextNode = NULL;

	return newNode;
}

/* 노드 추가. 테일 노드 뒤에 새 노드를 추가. */
void AppendNode(Node** head, Node* newNode) {

	printf("[AppendNode] 데이터 %2d 추가합니다. \n", newNode->data);

	/* 리스트가 비었다면 헤드에 뉴 노드 */
	if (NULL == (*head)) {
		(*head) = newNode;
	}
	else {
		Node* tail = (*head);

		while (NULL != tail->nextNode) {
			tail = tail->nextNode;
		}

		tail->nextNode = newNode;
	}
}

/* 노드 탐색 */
Node* GetLocation(Node* head, int location) {
	printf("[GetLocation]%d번째 노드를 찾아보자. \n", location);

	Node* current = head;

	while ((NULL != current) && (--location) >= 0) {
		printf("location : %d 번째 탐색 \n", location);
		current = current->nextNode;

	}

	return current;
}

/* 노드 삭제 */
void RemoveNode(Node** head, Node* target) { 

	printf("[RemoveNode] %2d를 삭제합니다.\n", target->data);

	// 헤드가 타겟이면
	if ((*head) == target) {
		(*head) = (*head)->nextNode;
	}
	else {
		// 현재의 다음노드가 타겟인지 검사하며 탐색  
		Node* current = (*head);

		while ((current->nextNode != target) && (NULL != current)) {
			current = current->nextNode;
		}

		// 현재의 다음이 타겟이므로. 현재와 '타겟의 다음'을 이어준다.
		current->nextNode = target->nextNode;
	}

	free(target);
}

/* 리스트 출력 */
void PrintList(Node* head) {
	printf("[PrintList] 리스트 전체를 출력합니다. \n");

	Node* tempNode = head;
	int count = 0;

	while (NULL != tempNode) {
		printf("%5d", tempNode->data);
		tempNode = tempNode->nextNode;
		count++;
	}
	printf("\n");
	printf("%5d개의 노드가 있습니다.\n", count);
}


/* 모든 노드 삭제  */
void RemoveAll(Node** head) {
	printf("[RemoveAll] 리스트 전체를 삭제합니다. \n");

	Node* tempNode = (*head);

	while (NULL != tempNode) {
		// 헤드 갱신해두고 
		(*head) = tempNode->nextNode;
		// tempNode를 메모리 해제 
		free(tempNode);
		// 헤드 주소를 다시 tempNode에 저장 
		tempNode = (*head);
	}
}


/* 노드 삽입. 특정 위치 뒤에 삽입 */
void InsertAfter(Node* current, Node* newNode) {
	printf("[InsertAfter] %d를 삽입합니다. \n", newNode->data);

	newNode->nextNode = current->nextNode;
	current->nextNode = newNode;
}


/* 노드 삽입. 특정 위치 앞에 삽입 */
void InsertBefore(Node** head, Node* current, Node* newNode) {
	printf("[InsertBefore] %d를 삽입합니다. \n", newNode->data);

	Node* tempNode = (*head);

	if (tempNode == current) {
		// 헤드 노드앞에 뉴 노드 
		newNode->nextNode = tempNode;
		(*head) = newNode;		
	}
	else {

		while (tempNode->nextNode != current) {
			tempNode = tempNode->nextNode;
		}
		//tempNode 다음이 current인 상태.
		newNode->nextNode = current;
		tempNode->nextNode = newNode;
	}
}


int main() {
	Node* list = NULL;
	Node* targetNode = NULL;

	/* 자유 저장소에 노드를 생성하여 List에 추가  */
	AppendNode(&list, CreateNode(100));
	AppendNode(&list, CreateNode(200));
	AppendNode(&list, CreateNode(300));

	// 리스트 전체 출력 
	PrintList(list);

	// 2번째 노드를 찾으려면, 1을 입력. 
	// 1번째 노드를 찾으려면, 0을 입력.
	targetNode = GetLocation(list, 0);
	printf("[탐색 결과] TargetNode의 Data : %d\n", targetNode->data);

	// 1번째 노드(인덱스 0) 을 삭제 
	RemoveNode(&list, targetNode);

	// 리스트 전체 출력 
	PrintList(list);
	
	targetNode = GetLocation(list, 0);
	// 헤드 앞에 2개 삽입 
	InsertBefore(&list, targetNode, CreateNode(50));

	targetNode = GetLocation(list, 0);
	InsertBefore(&list, targetNode, CreateNode(60));

	// 리스트 전체 출력 
	PrintList(list);

	targetNode = GetLocation(list, 0);
	// 헤드 뒤에 삽입 
	InsertAfter(targetNode, CreateNode(70));

	// 리스트 전체 출력 
	PrintList(list);

	// 모든 노드 삭제 
	RemoveAll(&list);
	// 리스트 전체 출력 
	PrintList(list);

	return 0;
}

다음 포스팅은 '더블 링크드 리스트'입니다.