링크드 리스트(Linked List)

- 데이터값과 포인터로 구성 포인터는 다음 데이터값의 주소를 저장

#include <iostream>
#include <algorithm>
using namespace std;

struct Node
{
	int data;
	struct Node *next;	//다음 노드를 저장
};

Node* head = NULL;
Node* tail = NULL;
Node* curr = NULL;

void CreateNode(int x);
void DeleteNode(int x);
void PrintNode();

int main()
{
	ios::sync_with_stdio(false);

	int n = 0;
	int k = 1;
	while (k)
	{
		cout << "\n1. 입력  2. 출력  3. 삭제 \n";
		cin >> n;
		cout << "\n";
		switch(n)
		{
		case 1:
			cout << "입력할 수를 입력해주세요 : ";
			cin >> n;
			CreateNode(n);
			break;
		case 2:
			cout << "출력\n";
			PrintNode();
			break;
		case 3:
			cout << "삭제할 수를 입력해주세요 : ";
			cin >> n;
			DeleteNode(n);
			break;
		default:
			k = 0;
			break;
		}
	}

	return 0;
}

void CreateNode(int x)
{
	Node* newNode = new Node();	//새 노드 생성
	newNode->data = x;	//저장할 값 넣기
	newNode->next = NULL;	//다음 주소 값은 없으므로 NULL

	if (head == NULL)	//넣는 노드가 처음넣는 노드이면 head
		head = newNode;
	else
		tail->next = newNode;	//아니면 현재 꼬리의 다음에 넣는다.

	tail = newNode;	//노드의 끝을 가르키게 함
}

void PrintNode()
{
	if (head == NULL)	//아무값도 없음
		cout << "저장된 값 없음\n";
	else
	{
		curr = head;	//현재값에 첫노드를 넣는다.
		cout << curr->data << " ";	//현재값을 출력

		while (curr->next != NULL)	//끝을 만날때까지 출력
		{
			curr = curr->next;
			cout << curr->data << " ";
		}
	}
	cout << "\n";
}

void DeleteNode(int x)
{
	curr = head;
	if (curr == NULL)
		cout << "저장된 값 없음\n";
	else
	{
		if (curr->data == x)	//head가 삭제할 값일때
		{
			if (curr->next == NULL)
			{
				curr = NULL;
				head = NULL;
				tail = NULL;
				cout << "값 \'" << x << "\'" << "삭제되었습니다.\n";
			}
			else if (curr->next != NULL)
			{
				Node* next = curr->next;
				delete(curr);
				head = next;
				cout << "값 \'" << x << "\'" << "삭제되었습니다.\n";
			}
			else
			{
				cout << "값 \'" << x << "\'" << "이 없습니다.\n";
			}
		}
		else
		{
			bool count = false;
			while (curr->next != NULL)	//다음 노드가 없을때까지 반복
			{
				if (curr->next->data == x)	//다음 노드가 삭제할 값일 때
				{
					if (curr->next->next == NULL)	//다음노드의 다음노드가 없으면(꼬리)
					{
						delete(curr->next);	//다음 노드 삭제
						tail = curr;
						tail->next = NULL;	//꼬리의 다음을 가르키는 주소 NULL
						cout << "값 \'" << x << "\'" << "삭제되었습니다.\n";
						count = true;
						break;
					}
					else	//삭제하는 노드가 중간일 때
					{
						Node* nextnext = curr->next->next;	//현재 노드의 다음다음노드 저장
						delete(curr->next);	//다음 노드 삭제
						curr->next = nextnext;	//다음다음노드를 연결
						cout << "값 \'" << x << "\'" << "삭제되었습니다.\n";
						count = true;
						break;
					}
				}
				else
				{
					curr = curr->next;	//현재값이 없으면 다음값으로 넘어가기
				}
			}
			if (curr->next == NULL && count == false)
			{
				cout << "값 \'" << x << "\'" << "이 없습니다.\n";
			}
		}
	}
}