C-Project16

배열리스트

장점: 요소에 인덱스를 이용해서 직접 접근 가능
단점: 리스트 삽입, 삭제시 효율이 좋지 않음, 저장공간이 제한적임

링크드 리스트

장점: 힙영역이 허용하는 범위내에서 데이터를 마음대로 저장 가능. 요소를 삽입, 삭제시 포인터를 이용해서 주소만 연결하면 되기 때문에 과부하가 없음.
단점: 데이터 순회시 리스트의 첫 노드부터 검색 시행

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

typedef struct node {
	int INFO; //각각의 노드에 저장될 데이터를 담을 멤버변수
	struct node* NEXT; //노드 타입의 다음 노드를 가리킬 포인터

}Node;

Node* FIRST = NULL;
Node* LAST = NULL;

void insert(int data);
void delete(int data);
void print(int data);
Node* search(int data);

int main(void) {

	int num1, num2, choice;
	Node* location;

	while (1) {
		printf("\n\n옵션 선택: \n");
		printf("\n1 - Insert ");
		printf("\n2 - Delete \n");
		printf("\n3 - Search \n");
		printf("\n4 - Print  \n");
		printf("\n5 - Exit \n");

		printf("\n\n메뉴 선택: ");
		scanf_s("%d", &choice); 
		switch(choice){
		case 1:
			printf("\n추가할 데이터 입력: ");
			scanf_s("%d", &num1);
			insert(num1);
			printf("\n데이터 %d 가 리스트에 성공적으로 추가되었습니다.", num1);
			getch();
			break;

		case 2:
			printf("\n리스트에서 삭제할 데이터 입력: ");
			scanf_s("%d", &num1);
			num2 = delete(num1);

			if (num2 == -9999)
				print("\n\t%d 링크드 리스트에 존재하지 않습니다.");
			else
				printf("\n\t%d가 링크드 리스트에 성공적으로 삭제되었습니다.\n\t", num1);
			getch();
			break;
		
		case 3:
			printf("\n검색할 데이터 입력: ");
			scanf_s("%d", &num1);
			location = search(num1);
			
			if (location == NULL)
				printf("\n\t%d는 링크드 리스트에 존재하지 않습니다.\n\t",num1);
			else {
				if (location == LAST)
					printf("\n\t요소 %d는 리스트의 마지막 요소입니다.", num1);
				else
					printf("\n\t요소 %d는 요소 %d의 앞에 위치해 있습니다.\n\t", num1,(location->NEXT)->INFO);
			}
			getch();
			break;

		case 4:
			print();
			getch();
			break;
		case 5:
			exit(1);
			break;
		default:
			printf("\n올바른 명령이 아닙니다. 다시 입력하세요.");
			getch();
			break;
		}
		printf("\n\n옵션 선택: \n");
	}
	return 0;
}

void insert(int data) {
	Node* ptr = malloc(sizeof(Node)); //추가할 노드가 사용할 메모리공간(힙) 할당
	ptr->INFO = data;

	if (FIRST == NULL) { //리스트가 비어있는 경우
		FIRST = LAST = ptr;
		ptr->NEXT = NULL;
	}
	else {//리스트에 기존 노드가 존재하는 경우
		LAST->NEXT = ptr;
		ptr->NEXT = NULL;
		LAST = ptr;
	}
}
void delete(int data) {
	Node* LOC, * TEMP; //LOC: 삭제 대상노드를 가리킬 포인터, TEMP: 순회과정에서 사용할 임시 포인터

	int i;
	i = data;
	LOC = search(i); //삭제할 대상 노드의 주소를 찾아서 변수 LOC에 저장

	if (LOC == NULL) //삭제할 값이 리스트에 있는지 체크
		return -9999;
	if (LOC == FIRST) { 
		if (FIRST == LAST) { //리스트에 노드가 하나만 존재하는 경우
			FIRST = LAST = NULL;
		}
		else {
			FIRST = FIRST->NEXT;
		}
		return(data);
	}
	for (TEMP = FIRST; TEMP->NEXT != LOC; TEMP = TEMP->NEXT)
		;
	TEMP->NEXT = LOC->NEXT;

	if (LOC == LAST) //삭제한 노드가 리스트의 마지막인 경우 삭제노드의 앞노드를 마지막 노드로 설정
		LAST = TEMP;
	return LOC->INFO; //삭제한 노드의 값을 호출부로 반환
}
void print(int data) {
	Node* ptr; //리스트를 앞으로부터 뒤로 순서대로 순회하는데 사용할 포인터
	
	if (FIRST == NULL) {
		printf("\n\tEmpty List!");
		return;
	}
	printf("\n링크드 리스트의 요소: \n");
	if (FIRST == LAST) {
		printf("\t%d", FIRST->INFO);
		return;
	}
	for (ptr = FIRST; ptr != LAST; ptr = ptr->NEXT)
		printf("\t%d", ptr->INFO);
	printf("\t%d", LAST->INFO);
}
Node* search(int data) {
	Node* ptr;

	if (FIRST == NULL)
		return NULL; //Node의 반환값이 포인터임으로 NULL포인터 값을 리턴해줌.
	for (ptr = FIRST; ptr != LAST; ptr = ptr->NEXT)
		if (ptr->INFO == data)
			return ptr; //찾은 경우 주소값을 반환
	if (LAST->INFO == data)
		return LAST;
	else
		return NULL;
}