단순연결리스트

#pragma once
#include "Windows.h"
#include "stdio.h"
#include <iostream>
 
using namespace std;
 
struct Node
{
	Node* _Next;
	int value;
};
 
class Linked
{
public:
	Node* _Head;
	Node* _Tail;
 
public:
	// n번째 노드 다음에 삽입
	Node* Insert_After(int k, Node* _node)
	{
		Node *s = new Node();// 새로운 노드 공간 확보
		s->value = k;// 새로운 노드에 갑 대입
		s->_Next = _node->_Next;// 새로운 노드의 다음 노드는 n번째 노드의 다음 노드
		_node->_Next = s;// n번째 노드의 다음 노드는 새로운 노드
		return s;
	}
 
	// n번째 노드의 다음 노드를 삭제
	int Delete_Next(Node *t)
	{
		Node *s;
		if (t->_Next == _Tail)
			return 0;  // n번째의 다음 노드가 꼬리면 리턴
		s = t->_Next;// n번째의 다음 노드를 s가 물어둠
		t->_Next = t->_Next->_Next;// n번째의 다음 노드를 삭제 하면 빈공간은 n번째의 다음 다음 노드로 채운다
		delete s;// n번째의 다음 노드 삭제
		return 1;
	}
 
	// k값을 가지는 노드 찾기
	Node* Find_Node(int k)
	{
		Node *s;
		s = _Head->_Next;
		while (s->value != k && s != _Tail)
			s = s->_Next;
		return s;
	}
 
	// k값을 가지는 노드 삭제
	int delete_node(int k)
	{
		Node *s;// 검색할 노드
		Node *p;// s가 가리키는 노드이 앞 노드
		p = _Head;
		s = p->_Next;
		while (s->value != k && s != _Tail)// 값을 찾든지 꼬리에 도달하면 끝
		{
			p = p->_Next; // p = s			다음 노드로 
			s = p->_Next; // s = s.next	다음 다음 노드로
		}
 
		if (s != _Tail)  /* if find */
		{
			p->_Next = s->_Next; // k값을 가지는 노드를 삭제시 빈공간을 k값노드의 다음 노드를 이전 노드의 다음 노드로 묵는다
			delete s; // k값을 가지는 노드 삭제
			return 1;
		}
		else
			return 0;
	}
 
	// k값을 같는 노드 앞에 t값 같는 새로운 노드 삽입
	Node *Insert_Node(int t, int k)
	{
		Node *s;// 값 검색을 따라가는 노드
		Node *p;// s의 앞노드
		p = _Head;
		s = p->_Next;
		while (s->value != k && s != _Tail)// 값을 찾든지 꼬리에 도달하면 끝
		{
			p = p->_Next; // p = s			다음 노드로 
			s = p->_Next; // s = s.next	다음 다음 노드로
		}
 
		if (s != _Tail)  /* if find */
		{
			Node *r = new Node();// 삽입하기위한 새로운 노드
			r->value = t; // 새로운 노드에 값 대입
			p->_Next = r; // k값노드의 앞 노드에 새로운 노드 대입 		p와 s 사이에 r을 삽입
			r->_Next = s; // 새로운 노드의 다음 노드에 k값노드의 대입	p와 s 사이에 r을 삽입
		}
		return p->_Next;
	}
 
	// 오르차순으로 정령 되있다고 가정하에 정령 순서를 깨지 않고 삽입하기
	Node *Ordered_Insert(int k)
	{
		Node *s;// 값 검색을 따라가는 노드
		Node *p;// s의 앞노드
		p = _Head;
		s = p->_Next;
		while (s->value <= k && s != _Tail)// 값을 찾든지 꼬리에 도달하면 끝
		{
			p = p->_Next; // p = s			다음 노드로 
			s = p->_Next; // s = s.next	다음 다음 노드로
		}
		Node* r = new Node();// 삽입하기위한 새로운 노드
		r->value = k; // 새로운 노드에 값 대입
		p->_Next = r; // k값노드의 앞 노드에 새로운 노드 대입		p와 s 사이에 r을 삽입
		r->_Next = s; // 새로운 노드의 다음 노드에 k값노드의 대입   p와 s 사이에 r을 삽입
		return r;
	}
 
	void Print_List(Node* t)
	{
		printf("\n");
		while (t != _Tail)
		{
			printf("%-8d", t->value);
			t = t->_Next;
		}
	}
 
	Node *delete_all(void)
	{
		Node *s;// 현제 노드
		Node *t;// 이전 노드
		t = _Head->_Next;// 머리 다음이 첫번째 노드, 첫번째 노드부터 삭제
		while (t != _Tail)
		{
			s = t;			// 현제 노드
			t = t->_Next;	// 현제 노드의 다음 노드
			delete s;		// 현제 노드 삭제
		}
		_Head->_Next = _Tail;
		return _Head;
	}
 
	// 노드 역순으로 재배열 해라
	Node* reverse(Node* head)
	{
		Node* p, *c, *n;
		p = head;// 첫번째 원소를 가리킨다
		n = _Tail;// NULL 아니면 꼬리를 가리킨다
		c = _Tail;// NULL 아니면 꼬리를 가리킨다
		while (p != _Tail)
		{
			n = c;			// p의 이전 이전 노드
			c = p;			// p의 이전 노드
			p = p->_Next;	// p의 노드를 한칸 이동
			c->_Next = n;	// p를 한칸 이동 시킨후에 n을 묵음
		}
		return c;
	}
 
public:
	Linked::Linked() {
		_Head = new Node();// 머리 공간 확보
		_Tail = new Node();// 꼬리 공간 확보
		_Head->_Next = _Tail;// 초기에 머리에 다음은 꼬리
		_Tail->_Next = _Tail;// 초기에 꼬리에 다음은 꼬리
	}
	virtual Linked::~Linked() {}
};
 
void main()
{
	Linked _Linked;
 
	Node* A = new Node();
	A->value = 1;
 
	_Linked.Insert_After(4, _Linked._Head);
	_Linked.Insert_After(3, _Linked._Head);
	_Linked.Insert_After(2, _Linked._Head);
	_Linked.Insert_After(1, _Linked._Head);
	_Linked.Print_List(_Linked._Head);
 
	_Linked._Head->_Next = _Linked.reverse(_Linked._Head->_Next);
	_Linked.Print_List(_Linked._Head);
 
	int x = 0;
	cin >> x;
	cout << x << endl;
}