[자료구조] 이중 연결 리스트

//*******************************************************
// 이중 연결 리스트 
//*******************************************************
//  -  head , tail 
#include 
#include 
//*******************************************************
struct Node
{
	int data; 
	Node * prev; // 앞의 노드를 가르키는 포인터 
	Node * next; // 뒤의 노드를 가리키는 포인터 
};
//*******************************************************
Node * head = NULL;
Node * tail  = NULL; 
//*******************************************************

Node * Begin(){ return head->next;}
Node * End(){   return tail->prev; }
//*******************************************************
// Utility 함수 !! 
//*******************************************************
Node * CreateNode( int data) 
{
	Node * NewNode =  (Node*)malloc(sizeof(Node)); 
	NewNode->data = data;
	NewNode->prev = NULL;
	NewNode->next = NULL; 
	return NewNode;
}
//*******************************************************
//  InitList : head, tail 노드 초기화 !! 
//*******************************************************
void InitList() 
{
	head = CreateNode(0); 
	tail = CreateNode(0); 
	head->next = tail;
	head->prev = head; 
	tail->next = tail; 
	tail->prev = head;
}

//*******************************************************
//  Insert( Node * first ,  Node * last ,  int data) 
//  : first포인터와 ㅣlast포인터 사이에 data를 넣어라 !! 
//*******************************************************
void Insert( Node * first ,  Node * last , int data ) 
{	
	// 노드 생성 
	Node * NewNode =  CreateNode(data); 
	//링크 연결 !! 
	NewNode->next = last; 
	NewNode->prev = first; 
	first->next = NewNode;
	last->prev = NewNode; 
}
//*******************************************************

void push_back(int data)
{
	Insert( End(), tail , data);
}
//*******************************************************
void push_front( int data )
{
	Insert( head, Begin(), data);
}
//*******************************************************
//*******************************************************
Node * find( int data) 
{
	Node * p = head->next; 
	while( p != tail)
	{
		if( p->data == data)
		{
			return p;
		}
		else 
		{
			p  = p->next;
		}
	}
	return NULL;
}
//*******************************************************

void show()
{
	Node * p = head->next; 
	while( p != tail)
	{
		printf("%d--", p->data);
		p = p->next;
	}
	puts("");
}
//*******************************************************
// erase( Node * where); 해당 노드를 삭제한다 !! 
//*******************************************************
void erase( Node * Where )
{	
	Where->prev->next = Where->next; 
	Where->next->prev = Where->prev; 
	free(Where);
}
void erase( int data )
{	
	erase( find(data)) ;
}
void pop_back()
{
	erase( End()); 
}
void pop_front()
{
	erase( Begin()); 
}