[자료구조] 연결 리스트

//**************************************************************
//  연결리스트 !! 
//**************************************************************
//  데이타를 갖는 노드를 포인터를 통해 연결하여 순차적인 선형 자료구조 !! 

// 배열 --> 연접리스트

// 물리적으로 떨어져있는 데이타들을 링크( 포인터)를 통해 연결하여 논리적인
// 선형 구조를 갖게한다 !! 
//                       1024             2048
//   [  10  ]         [  20  ]          [  30  ][  40  ]
//   [ 1024]  ----> [ 2048 ]   ----> [       ]  
       
//  연결리스트 --> 메모리가 절약 --> 필요할때마다 노드르 늘려 나간다 !! 
//             --> 크기를 모는 경우에 유용하다.  
//   동적배열 VS 연결리스트 !! 
// 동적배열은 크기가 늘어나거나 줄어들때 전체를 복사 할당 재할당 해제가 필요 !! 
// 연결리스트는 필요한 만큼만 사용한다 !! 
 
// 어디서든 !!  삽입 삭제 속도가 빠르게 동작한다 !! 



#include 
#include 
//*******************************************************************
// 단일 연결리스트 구현 
//*******************************************************************
// 노드 구조체 :  리스트내의 하나의 노드를 나타내기위한 구조체 !! 데이타와 링크 !! 
struct Node
{
	int Data; // 데이타 저장소 
	Node * next;  //  다음 노드를 가르킬 포인터 
};
//*******************************************************************
// 1) 더미노드를 활용하는 방법 !!  
//   head,tail더미 노드사이에 노드들을 추가하는 방법 !! 
// 2) head 노드만 갖고 구현하는 방법 !! 
// --> tail노드 대신에 next가 null인노드를 찾는 방법으로 리스트의 끝을 판별 !! 
// 3) head * 만 갖고 구현하는 방법 !! 
//*******************************************************************
// 더미 노드 선언 !! 
//*******************************************************************
Node * head = NULL; 
Node * tail = NULL; 
//*******************************************************************
// InitList :head, tail 노드생성 
//*******************************************************************
void InitList()
{
	//head생성 
	head = (Node*)malloc(sizeof(Node)); 
	// tail노드 생성 
	tail = (Node*)malloc(sizeof(Node)); 
	// 링크 연결 
	head->next =  tail; 
	tail->next  = NULL; 
}
//-----------------------------------------------------------------
// push_back :  리스트에 맨위에 노드를 삽입하는 함수 !! 
//-----------------------------------------------------------------
void push_back( int data) 
{
	// 1) 노드생성 
	Node * NewNode =  (Node*)malloc(sizeof(Node)); 
	NewNode->Data = data; 
	NewNode->next = NULL; 
	//2) 삽입 위치 찾기 !! 
	Node * p =  head; 
	while( p->next != tail)
	{
		p = p->next; 
	}
	// 3) 링크 연결 
	NewNode->next = p->next;
	p->next = NewNode;

}
//-----------------------------------------------------------------
//  2) 맨앞에 삽입하는 경우 
//-----------------------------------------------------------------
void push_front( int data)
{// 1) 할당 
	Node * NewNode = (Node*)malloc(sizeof(Node)); 
	NewNode->Data = data;
	NewNode->next = head->next;
	head->next =  NewNode;
}
//-----------------------------------------------------------------
// 3) 중간에 삽입  :  key값 뒤에 data삽입하자 !! 
//-----------------------------------------------------------------
void Insert( int key ,  int data)
{	
	// 1)노드 생성 !! 
	Node * NewNode = (Node*)malloc(sizeof(Node)); 
	NewNode->Data = data; 
	NewNode->next = NULL; 

	Node * p = head->next; 
	while( p != tail)
	{
		if( p->Data == key) 
		{
			NewNode->next = p->next; 
			p->next =  NewNode; 
			return;
		}
		else
		{
			p = p->next;
		}
	}
	free(NewNode);
	push_back(data);
	
}
//-----------------------------------------------------------------
// 맨뒤에서 삭제 
//-----------------------------------------------------------------
void pop_back() 
{
	Node * p, *s; 
	
	if( head->next == tail) 
	{
		puts("list Empty ~ !!"); return; 
	}
	else 
	{
		p = head->next;
		s = head; 
		while( p->next != tail)
		{
			s = p;
			p = p->next;
		}
		s->next = p->next; 
		free(p);
	}
}
//-----------------------------------------------------------------
//-----------------------------------------------------------------
// 맨앞에서 삭제 
//-----------------------------------------------------------------
void pop_front()
{
	Node * p = head->next; 
	if(head->next == tail) 
	{	
		puts("list empty !! ");
	}
	else
	{
		head->next = p->next;
		free( p );
	}
}
//-----------------------------------------------------------------
//  중간에서 삭제 !! 
//-----------------------------------------------------------------
void erase( int key)
{	
	Node * p, *s; 
	if( head->next == tail) 
	{
		puts("list empty !!");
	}
	else
	{
		s = head;
		p = head->next;
		while( p != tail) 
		{
			if( p->Data == key) 
			{
				s->next = p->next;
				free(p); 
				return;
			}
			else
			{
				s = p;
				p = p->next;
			}
			
		}
	} 
}
//-----------------------------------------------------------------
//-----------------------------------------------------------------
//-----------------------------------------------------------------
// Show() : 리스트 출력 !! 
//-----------------------------------------------------------------
void Show()
{
	Node * p = head->next; 
	while( p != tail) 
	{	
		printf("%d --> " ,  p->Data );
		p = p ->next;
	}
	puts(""); //개행
}
void main()
{
	InitList();		
	// 삽입 
	//-----------------------------------------------------------------
	//  1) 맨뒤에 삽입하는 경우 
	//-----------------------------------------------------------------
	push_back( 10 );  
	push_back( 20 );  
	push_back( 30 );  
	Show();
	//-----------------------------------------------------------------	
	//  2) 맨앞에 삽입하는 경우  
	//-----------------------------------------------------------------
/*	push_front(100);
	push_front(200);
	Show();
	//-----------------------------------------------------------------
	//  3) 중간에 삽입하는 함수 
	//-----------------------------------------------------------------
	Insert( 10, 999);
	Show();
	Insert( 30, 888);
	Show();
	Insert( 888, 1888);
	Show();*/
	// 삭제 연산 
	//-----------------------------------------------------------------
	// 1) 맨뒤에서 삭제 
	//-----------------------------------------------------------------
		erase(30);
		Show();
		erase(10);
		Show();
		erase(20);
		Show();

//-----------------------------------------------------------------
// 2) 맨앞에서 삭제 
//-----------------------------------------------------------------
	// 3) 중간에서 삭제  
	//-----------------------------------------------------------------
}