연결리스트(Linked List)

연결리스트?(based C)

연결리스트(Linked List)는 데이터와 포인터로 구성된 연속적이지 않은 주소에 있는 노드들이 연결되어 있는 자료구조이다.
배열은 메모리에서 주소가 연속적이지만, 연결리스트는 노드들의 주소가 연속적이지 않다.
또한 배열은 크기가 고정되어 있지만, 연결리스트는 크기가 정해져있지 않다.
배열은 index로 데이터를 접근할 수 있지만, 연결리스트는 HEAD부터 시작하여 link를 따라가며 모든 노드를 탐색함으로써 데이터에 접근할 수 있다.
*사진출처: 생활코딩(https://opentutorials.org/module/1335/8821)

종류

연결리스트의 종류에는 단순 연결리스트, 원형연결리스트, 이중연결리스트.. 정도가 있는데, 단순 연결리스트의 동작 원리를 알고 코드를 몇번 구현해보면, 나머지는 상황에 맞게 유연하게 코드를 구현할 수 있다.

연결리스트 연산

1. 삽입 - InsertNode
2. 삭제 - DeleteNode
3. 탐색 - SearchNode
4. 동적할당 해제 - FreeNode

삽입 - InsertNode (head 바로 뒤에 삽입)

void InsertNode(int data) {			
	Node* new_node = (Node*)malloc(sizeof(Node));		//newnode포인터에 Node구조체 크기만큼의 공간이 할당. 즉, newnode에는 Node의 주소가 들어감.
	if (new_node) {			//NULL포인터 역참조 오류 해결. newnode가 메모리 할당을 받지 못했을 경우 NULL을 반환. 
		new_node->data = data;		
		new_node->link = head;
		head = new_node;			//포인터 변수에는 변수의 주소값이 들어가는데, newnode는 node를 가리키는 포인터이기 때문에 node의 주소값이 들어있음.
	}								//그러니까 head에 new_noew를 대입하면, new_node에 들어있던 node의 주소값이 head에 들어가는 것이기 때문에
	PrintList();					//head가 결국 new_node를 가리키게 되는 것.(head에 new_node의 주소값이 들어가는 것.)
}

삭제 - DeleteNode (head 바로 뒤에 노드 삭제)

void DeleteNode(int data) {			//맨 앞에 있는 노드 삭제(이게 바로 스택)
	int del_data = 0;	//삭제할 노드. 정보를 잠시 저장
	if (head) {		//head에 연결된 노드가 있다면
		del_data = head->data;		//head에는 가장 첫번째 노드의 주소가 들어있음. (*head).data와 같다.
		head = head->link;
		printf("%d을(를) 삭제합니다.\n", del_data);
	}
	else {
		printf("연결리스트가 비었습니다\n");
		return;
	}
	PrintList();
}

탐색 - SearchNode

int SearchNode(int data) {		//데이터의 위치 찾음
	int cnt = 0;
	Node* curr_ptr = head;
	while (curr_ptr) {
		cnt++;
		if (curr_ptr->data == data) {
			return cnt;		//찾은 노드의 위치(몇번째) 리턴
		}
		curr_ptr = curr_ptr->link;
	}
	return 0;		//못찾았으면 0 리턴
}

동적할당 해제 - FreeNode

void FreeNode() {				//동적할당된 노드 해제
	Node* curr_ptr = NULL;
	while (curr_ptr) {
		curr_ptr = head;
		head = head->link;
		free(curr_ptr);
	}
}

전체 코드(based C)

#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>
#include <stdlib.h>
//
typedef struct Node {
	int data;			//노드에 들어있는 데이터
	struct Node* link;	//노드를 연결하는 포인터(Node형 포인터. -> int형을 가리키면 int형 포인터, 이거는 Node구조체형을 가리키는 포인터.)
}Node;
Node* head = NULL;		//연결리스트의 시작인 head포인터
//
void PrintList() {
	Node* curr_ptr = head;		//노드 순회 포인터. 초기값으로 head값을 넣어줌(head는 연결리스트의 첫번째 노드 가리킴)
	while (curr_ptr) {
		printf("%d", curr_ptr->data);	//현재 순회중인 노드의 데이터 출력
		curr_ptr = curr_ptr->link;		//다음 노드로 이동
		if (curr_ptr != NULL) {
			printf(" -> ");
		}
	}
	printf("\n");
}
//
void InsertNode(int data) {			
	Node* new_node = (Node*)malloc(sizeof(Node));		//newnode포인터에 Node구조체 크기만큼의 공간이 할당. 즉, newnode에는 Node의 주소가 들어감.
	//
	if (new_node) {			//NULL포인터 역참조 오류 해결. newnode가 메모리 할당을 받지 못했을 경우 NULL을 반환. 
		new_node->data = data;		
		new_node->link = head;
		head = new_node;			//포인터 변수에는 변수의 주소값이 들어가는데, newnode는 node를 가리키는 포인터이기 때문에 node의 주소값이 들어있음.
	}								//그러니까 head에 new_noew를 대입하면, new_node에 들어있던 node의 주소값이 head에 들어가는 것이기 때문에
	PrintList();					//head가 결국 new_node를 가리키게 되는 것.(head에 new_node의 주소값이 들어가는 것.)
}				
//
void DeleteNode(int data) {			//맨 앞에 있는 노드 삭제(이게 바로 스택)
	int del_data = 0;	//삭제할 노드. 정보를 잠시 저장
	if (head) {		//head에 연결된 노드가 있다면
		del_data = head->data;		//head에는 가장 첫번째 노드의 주소가 들어있음. (*head).data 해보기
		head = head->link;
		printf("%d을(를) 삭제합니다.\n", del_data);
	}
	else {
		printf("연결리스트가 비었습니다\n");
		return;
	}
	PrintList();
}
//
int SearchNode(int data) {		//데이터의 위치 찾음
	int cnt = 0;
	Node* curr_ptr = head;
	while (curr_ptr) {
		cnt++;
		if (curr_ptr->data == data) {
			return cnt;		//찾은 노드의 위치(몇번째) 리턴
		}
		curr_ptr = curr_ptr->link;
	}
	return 0;		//못찾았으면 0 리턴
}
//
void FreeNode() {				//동적할당된 노드 해제
	Node* curr_ptr = NULL;
	while (curr_ptr) {
		curr_ptr = head;
		head = head->link;
		free(curr_ptr);
	}
}
//
int main() {
	int input = 0, search_data = 0, search_location = 0;
	char key = 0;		
	printf("Linked List에 삽입할 number 입력. z를 입력하면 삭제 / x를 입력하면 탐색 / y를 입력하면 종료\n");
	while (1) {
		scanf("%c", &key);
		if (key >= 48 && key <= 57) {
			InsertNode((int)key - 48);	//연결리스트 맨 앞에 삽입
		}
		if (key == 122) {		//z를 누르면
			DeleteNode(input);
		}	
		else if (key == 121) {		//y를 누르면 탈출
			printf("종료합니다.............\n");
			break;
		}
		else if (key == 120) {		//x를 누르면
			printf("찾을 데이터(숫자) 입력하시오: ");
			scanf("%d", &search_data);
			search_location = SearchNode(search_data);
			printf("찾은 데이터는 %d번째에 있습니다.\n", search_location);
		}
	}
	FreeNode();		//노드 동적할당
	//
	return 0;
}

끝

연결리스트는 데이터를 저장하는 방법중 하나일 뿐이다. 배열처럼 인덱스로 접근하지 못하고 HEAD부터 모든 데이터를 탐색하며 동작을 수행하기 때문에 속도가 느릴 수 있다. 하지만, 배열은 삽입시 나머지 원소들을 뒤로 밀고, 삭제시 나머지 원소들을 앞으로 당겨오는 과정이 필요한데, 연결리스트는 포인터로 연결만 해주면 되기 때문에 삽입과 삭제가 많고, 데이터 저장 공간이 정해져있지 않은 가변적인 상황에 쓰기에 적합하다. 연결리스트의 삽입, 삭제, 탐색의 알고리즘은 정해져있는 것이 아니라 상황에 맞게 구현하면 된다.
++배열은 컴파일 시간에 Stack영역에 static으로 메모리가 할당되고, 연결리스트는 Runtime에 Heap영역에 Dynamic하게 메모리가 할당된다.