이중 연결 리스트(Doubly Linked List)

노드 추가 시 끝이 아닌 오름차순 추가가 되도록 구현.

DoublyLinkedListMain.c

#include <stdio.h>
#include <stdlib.h>
#include <Windows.h>
#include "DoublyLinkedList.h"

int main() {
	int val, select;
	char c;
	dnode* head = NULL, * tail = NULL, * temp, * ptr;
	mbool autoLookupAddNode = t, autoLookupDeleteNode = t;

	while (1) {
		printf("<Doubly Linked List>\n1. 추가\n2. 삭제\n3. 조회\n");
		printf("입력 (N = exit): ");
		scanf_s("%d", &select);
		if ((c = getchar()) == 'N') break;
		else if (Inputchk(c) > 0) ReInput();
		else if (select == 1) {		// 노드 추가
			system("cls");
			if (head != NULL) PrintNodeAscDesc(head, tail);
			while (1) {
				printf("<추가>\n(N = 이전으로 / L = Lookup\n");
				printf("C = Console Clear / A = ChangeAutoLookup(%s))\n값 입력: ", autoLookupAddNode == t ? "True" : "False");
				scanf_s("%d", &val);
				if ((c = getchar()) == 'N') {
					system("cls");
					break;
				}
				else if (c == 'L') {
					if (head == NULL) {
						system("cls");
						puts("생성된 노드가 없습니다 (조회 불가)\n");
					}
					else {
						puts("");
						PrintNodeAscDesc(head, tail);
					}
				}
				else if (c == 'C') {
					system("cls");
					if (head != NULL) PrintNodeAscDesc(head, tail);
				}
				else if (c == 'A') {
					autoLookupAddNode = autoLookupAddNode == t ? f : t;
					if (autoLookupAddNode == t) puts("\n자동조회 ON\n");
					else puts("\n자동조회 OFF\n");
				}
				else if (Inputchk(c) > 0) ReInput();
				else {
					InsertNodeASC(val, &head, &tail);
					puts("");
					if (autoLookupAddNode == t) PrintNodeAscDesc(head, tail);
				}
			}
		}
		else if (select == 2) {		// 노드 삭제
			system("cls");
			if (head == NULL) puts("생성된 노드가 없습니다 (삭제 불가)\n");
			else {
				PrintNodeAscDesc(head, tail);
				while (1) {
					printf("<삭제>\n(N = 이전으로 / L = Lookup\n");
					printf("C = Console Clear / A = ChangeAutoLookup(%s))\n값 입력: ", autoLookupDeleteNode == t ? "True" : "False");
					scanf_s("%d", &val);
					if ((c = getchar()) == 'N') {
						system("cls");
						break;
					}
					else if (c == 'L') {
						if (head == NULL) {
							system("cls");
							puts("생성된 노드가 없습니다 (메인으로)\n");
							break;
						}
						else {
							puts("");
							PrintNodeAscDesc(head, tail);
						}
					}
					else if (c == 'C') {
						system("cls");
						if (head != NULL) PrintNodeAscDesc(head, tail);
					}
					else if (c == 'A') {
						autoLookupDeleteNode = autoLookupDeleteNode == t ? f : t;
						if (autoLookupDeleteNode == t) puts("\n자동조회 ON\n");
						else puts("\n자동조회 OFF\n");
					}
					else if (Inputchk(c) > 0) ReInput();
					else {
						if (head == NULL) {
							system("cls");
							puts("생성된 노드가 없습니다 (메인으로)\n");
							break;
						}
						else DeleteNode(val, &head, &tail);
						if (head != NULL) {
							puts("");
							if (autoLookupDeleteNode == t) PrintNodeAscDesc(head, tail);
						}
						else puts("");
					}
				}
			}
		}
		else if (select == 3) {
			system("cls");
			if (head == NULL) {
				puts("생성된 노드가 없습니다 (조회 불가)\n");
			}
			else {
				printf("<조회>\n\n");
				PrintNodeAscDesc(head, tail);
			}
		}
		else ReInput();
	}

	if (head != NULL) {
		for (ptr = head; ptr;) {
			temp = ptr;
			ptr = ptr->next;
			free(temp);
		}
		printf("\n메모리 할당 해제\n");
	}
	printf("\n프로그램 종료\n");
}

메인 프로그램

 

LinkedListFunction.c

#include <stdio.h>
#include "DoublyLinkedList.h"

int Inputchk(char c)
{
	if (c == '\n') return 0;
	int i = 1;
	while (getchar() != '\n') i++;
	return i;
}

void ReInput(void) {
	system("cls");
	puts("재입력\n");
}

void PrintNodeASC(dnode* head) {
	dnode* ptr;
	printf("오름차순 \n");
	for (ptr = head; ptr; ptr = ptr->next) {
		printf("%d ", ptr->data);
	}
}

void PrintNodeDESC(dnode* tail) {
	dnode* ptr;
	printf("내림차순 \n");
	for (ptr = tail; ptr; ptr = ptr->prev) {
		printf("%d ", ptr->data);
	}
}

void PrintNodeAscDesc(dnode* head, dnode* tail) {
	PrintNodeASC(head);
	puts("");
	PrintNodeDESC(tail);
	printf("\n\n");
}

void DeleteNode(int val, dnode** head, dnode** tail) {
	dnode* ptr;
	mbool chk = f;
	for (ptr = *head; ptr; ptr = ptr->next) {
		if (ptr == *head && ptr->data == val) {
			if (ptr->next != NULL) {
				*head = ptr->next;
				ptr->next->prev = NULL;
			}
			else {
				*head = NULL;
				*tail = NULL;
			}
			free(ptr);
			chk = t;
			break;
		}
		else if (ptr == *tail && ptr->data == val) {
			if (ptr->prev != NULL) {
				*tail = ptr->prev;
				ptr->prev->next = NULL;
			}
			else {
				*head = NULL;
				*tail = NULL;
			}
			free(ptr);
			chk = t;
			break;
		}
		else if (ptr->data == val) {
			ptr->prev->next = ptr->next;
			ptr->next->prev = ptr->prev;
			free(ptr);
			chk = t;
			break;
		}
		//else if (ptr->data > val) break;	// 노드 추가 오름차순일 경우
	}
	if (chk == f) puts("\n| 삭제 데이터를 찾지 못했습니다 |");
	else puts("\n| 삭제 완료 |");
}

void InsertNodeASC(int val, dnode** head, dnode** tail) {	// 오름차순 추가
	dnode* temp, * ptr;

	if (*head == NULL) {
		*head = (dnode*)malloc(sizeof(dnode));
		(*head)->data = val;
		(*head)->next = NULL;
		(*head)->prev = NULL;
		*tail = *head;
	}
	else {
		temp = (dnode*)malloc(sizeof(dnode));
		temp->data = val;
		temp->next = NULL;
		temp->prev = NULL;

		for (ptr = *head; ptr; ptr = ptr->next) {
			if (ptr == *head && ptr->data > temp->data) {
				temp->next = ptr;
				ptr->prev = temp;
				*head = temp;
				break;
			}
			else if (ptr->next != NULL && ptr->data <= temp->data && ptr->next->data >= temp->data) {
				temp->next = ptr->next;
				temp->prev = ptr;
				ptr->next->prev = temp;
				ptr->next = temp;
				break;
			}
			else if (ptr->next == NULL) {
				temp->prev = ptr;
				ptr->next = temp;
				*tail = temp;
				break;
			}
		}
	}
	puts("\n| 추가 완료 |");
}

사용 함수 구현부

 

DoublyLinkedList.h

#ifndef __LINKED_LIST_HEADER__
#define __LINKED_LIST_HEADER__

typedef enum mbool { f, t }mbool;

struct dnode {
	int data;
	struct dnode* prev;
	struct dnode* next;
};
typedef struct dnode dnode;

int Inputchk(char);
void ReInput(void);
void PrintNodeASC(dnode*);
void PrintNodeDESC(dnode*);
void PrintNodeAscDesc(dnode*, dnode*);
void DeleteNode(int, dnode**, dnode**);
void InsertNodeASC(int, dnode**, dnode**);

#endif

헤더

 

콘솔 실행 화면

실행 첫 화면

노드 추가 (오름차순)

조회

삭제

삭제 시 현재 데이터 먼저 출력

 

메모리 할당 해제 후 종료