[자료구조] 연결 리스트

 

1. 자료구조
   1. 연결 리스트
   2. 이진 트리
   3. 스택
   4. 큐
   5. 해시
2. 정렬
   1. 버블 정렬
   2. 선택 정렬
   3. 삽입 정렬
   4. 퀵 정렬
   5. 힙 정렬
3. 알고리즘
   1. 재귀 함수
   2. 너비 우선탐색(BFS)
   3. 깊이 우선탐색(DFS)
   4. 다익스트라

---

연결 리스트(Linked List)

 

연결 리스트는 기차를 생각하면 이해하기 쉽다.

각 열차(Node)에 사람들(Data)가 있고 

이 열차를 1줄로 계속 연결하면 된다.

그리고 각 열차는 다음 열차의 위치를 저장한다.

 

하지만 저는 최상위/최하위 노드와 총 노드의 개수를 저장하는 구조체를 사용하여

좀더 쉽게 연결 리스트를 사용하고자 합니다.

 

 

---

 

새로운 노드 추가

 

노드가 없는 경우

 

새로운 노드를 만들고 리스트의 head에 새로운 노드의 주소를 저장한다.

Number를 1증가시킨다.

 

 

노드가 한개만 있는 경우

 

다시 새로운 노드를 만들고 리스트의 Tail에 새로운 노드의 주소를 저장한다.

Head가 가리키는 노드, 즉 최상위 노드의 Next에 새로만든 노드의 주소를 저항한다.

Number를 1증가시킨다.

 

 

노드가 여러개가 있는 경우

 

 

새로운 노드를 만들고 리스트의 Tail이 가르키는 노드의 Next에 새로운 노드의 주소를 저장한다.

리스트의 Tail에 새로운 노드의 주소를 저장한다.

Number를 1증가시킨다.

 

 

---

 

노드 삭제

 

최상위 노드를 삭제

 

리스트의 head에 삭제하는 노드의 Next가 가르키는 노드를 저장한다.

노드를 삭제한다.

Number를 1감소시킨다.

 

 

최하위 노드일 경우

 

삭제할 노드를 가르키는 노드(이전 노드)의 Next를 NULL로 초기화하고 리스트의 Tail에 주소를 저장

노드를 삭제한다.

Number를 1감소시킨다.

 

 

중간 노드일 경우

 

삭제할 노드의 Next의 주소를 삭제할 노드를 가르키는 노드(이전 노드)의 Next에 저장한다.

노드를 삭제한다.

Number를 1감소시킨다.

 

---

 

소스 코드

#define __main

#ifdef __main

#include <stdio.h>

typedef struct __node {
	struct __node* next; // 다음 노드

	// data
	char Name[20];
	int Age;
} Node;

typedef struct __list {
	Node* head;	// 최상위 노드
	Node* tail; // 최하위 노드
	int number; // 노드 수
} List;

void SetNode(Node* n, Node* next, char name[20], int age) {
	n->next = next;
	strcpy(n->Name, name);
	n->Age = age;
}

void Insert(List* list, char name[20], int age) {
	Node* ptr = malloc(sizeof(Node)); // 새로운 노드 생성

	SetNode(ptr, NULL, name, age); // 노드에 값을 입력

	if (list->number == 0) list->head = ptr; // 노드가 없는 경우
	else if (list->number == 1) list->head->next = list->tail = ptr; // 노드가 한개만 존재하는 경우
	else if (list->number > 1) list->tail = list->tail->next = ptr; // 노드가 여러개일 경우

	list->number += 1;
}


void Remove(List* list, char name[20]) {
	Node* node = list->head;
	Node* before_node = node;

	if (list->number == 0) {
		// 노드가 없는 경우
		printf("Error : no data\n");
		return 0;
	}
	else if (list->number == 1) {
		// 노드가 하나일 경우
		list->number = 0;
		free(list->head); // 최상위 노드만 삭제(최하위 노드는 NULL값임)
		list->head = NULL;
		printf("Remove %s's data\n", name);
		return 0;
	}
	else {
		// 노드가 여러개일 경우
		for (int i = 0; i < list->number; i++) {
			// 최상위 노드부터 최하위 노드까지 검색
			if (strcmp(node->Name, name) == 0) {
				// 일치하는 노드를 찾은 경우
				list->number -= 1;
				if (node == list->head) {
					// 찾은 노드가 최상위 노드일 경우
					list->head = node->next;
				}
				else if (node == list->tail) {
					// 찾은 노드가 최하위 노드일 경우
					before_node->next = NULL;
					list->tail = before_node;
				}
				else {
					before_node->next = node->next;
				}
				free(node); // 노드를 삭제
				printf("Remove %s's data\n", name);
				return 0;
			}
			before_node = node;
			node = node->next;
		}
	}
	// 노드를 찾지 못한 경우
	printf("Error : Can not find data\n");
}

void clear(List* list) {
	Node* n;

	for (int i = 0; i < list->number; i++) {
		// 최상위 노드부터 최하위 노드까지 삭제
		n = list->head->next;
		free(list->head);
		list->head = n;
	}

	list->number = 0;
}

void Print(List* list) {
	if (list->number == 0) {
		printf("\nError : no data\n");
		return 0;
	}
	Node* n = list->head;
	printf("\n");
	for (int i = 0; i < list->number; i++) {
		printf("Name : %s, Age : %d\n", n->Name, n->Age);
		n = n->next;
	}
}

int main()
{
	struct __list* list;
	int state = 0;
	int age;
	char name[10];
	char s;


	list = malloc(sizeof(List));

	list->head = NULL;
	list->tail = NULL;
	list->number = 0;

	while (1) {
		printf("\n[1] Input, [2] Remove, [3] Print\n");
		printf("Please Select Number : ");
		scanf("%d", &state);
		switch (state) {
		case 1:
			printf("Name : ");
			scanf("%s", name);
			printf("Age : ");
			scanf("%d", &age);


			Insert(list, name, age);
			break;
		case 2:
			printf("Name : ");
			scanf("%s", name);

			Remove(list, name);
			break;
		case 3:
			Print(list);
			break;
		default:
			break;
		}
	}

	clear(list);
	return 0;
}

#endif