티스토리 뷰

Programming/뇌를 자극하는 알고리즘

뇌를 자극하는 알고리즘 1. 리스트 - Double Linked List

ProjectKMS 2010. 10. 1. 00:16

코드

DLL.h

#ifndef DLL_H
#define DLL_H

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

typedef int ElementType;

typedef struct tagNode{
	ElementType Data;
	struct tagNode *PrevNode;
	struct tagNode *NextNode;
} Node;

Node* DLL_CreateNode(ElementType NewData); // 노드 생성
void DLL_DestroyNode(Node* Node); // 노드 파괴
void DLL_AppendNode(Node** Head, Node* NewNode); // 노드를 추가하는 함수 - 링크드 리스트 젤 끝(tail)에 추가
void DLL_InsertAfter(Node* Current, Node* NewNode); // Current 노드 뒤에 NewNode를 삽입하는 함수
void DLL_InsertNewHead(Node** Head, Node* NewHead); 
				// 새로운 노드를 Head로 만드는 함수(-링크드 리스트 맨 앞에 노드를 삽입하는 함수)
void DLL_RemoveNode(Node** Head, Node* Remove);	// 노드 제거 - 제거할 노드의 메모리 해제 기능까지 자체 추가.
Node* DLL_GetNodeAt(Node* Head, int Location); // Location 번째의 노드(0번부터 시작)를 찾아 그 주소를 리턴하는 함수
			
int DLL_GetNodeCount(Node* Head);


// Vitamin Quiz 추가 함수 
void DLL_InsertBefore(Node **Head, Node* Current, Node* NewNode);// Current 노드 앞에 NewNode를 삽입하는 함수
void DLL_DestroyAllNodes(Node **List); // 모든 노드를 한번에 제거하는 함수

// Vitamin Quiz 추가 함수 
void DLL_PrintReverse(Node* Head); // 더블 링크드 리스트를 역순으로 출력하는 함수

#endif

--------------------------------------------------------------------------------------------------

DLL.cpp
 
#include "DLL.h"


// 노드 생성 함수
Node* DLL_CreateNode(ElementType NewData){

	Node* NewNode = (Node*)malloc(sizeof(Node));
	// 새로운 노드를 생성하고

	NewNode->Data = NewData; // 매개변수로 넘긴 데이터를 저장하고

	// SLL->DLL 로 변경하면서 새로 생긴 부분 //
	NewNode->PrevNode = NULL; // 이전의 노드를 가리키는 PrevNode를 NULL로 초기화
	//////////////////////////////////////////
	NewNode->NextNode = NULL; // 가리키는 다음 노드를 뜻하는 NewtNode는 NULL로

	return NewNode; // 생성한 노드의 주소를 리턴
}

// 생성한 노드를 메모리 해제시키는 함수
void DLL_DestroyNode(Node* Node){	
	free(Node);
}

// 노드를 추가하는 함수 - 링크드 리스트 젤 끝(tail)에 추가
void DLL_AppendNode(Node** Head, Node* NewNode){
	// Head의 이중 포인터 선언 
	// - Head를 싱글 포인터로 선언시 Head가 가리키는 주소값의 바꿀수 없다.
	// - 이중포인터로 선언시 Node* 타입의 헤드의 주소를 넘기므로서 Head가 가리키는 Node의 변경이 가능
		
	// Head Node가 NULL이라면 - 현재 생성된 링크드 리스트가 없다.
	// 따라서 추가할 노드가 head이자 tail이다.
	if( (*Head) == NULL){		
		*Head = NewNode;
		printf("New Node Inserted <Head Node> : NewNode's Data = %d\n", NewNode->Data);
	}
	else{ // 이미 만들어진 링크드 리스트가 있다면
		  // tail을 찾아서 tail의 NewxNode에 NewNode를 연결해야 한다.
		
		Node* Tail = (*Head); // Head가 가리키는 Node의 주소로 Tail 을 초기화
		while(Tail->NextNode !=NULL){ // Tail의 NewNode가 NULL이라면 Loop문 탈출 - 즉, Tail을 찾았다면 루프문 탈출
			Tail = Tail->NextNode;
			// Tail이 가리키는 Node를 Tail->NextNode 로 변경.
		}
		// Loop문 수행시 Tail은 링크드 리스트의 마지막 노드를 가리키게 됨
		Tail->NextNode = NewNode;
		// SLL->DLL 로 변경하면서 새로 생긴 부분 //
		NewNode->PrevNode = Tail; // 기존의 테일을 새로운 Tail이 되는 노드의 PrevNode가 가리키게 함.
		///////////////////////////////////////////
		printf("New Node Inserted             : NewNode's Data = %d \n", NewNode->Data);
		
	}
}

// Current 노드 뒤에 NewNode를 삽입하는 함수
void DLL_InsertAfter(Node* Current, Node* NewNode){
	NewNode->NextNode = Current->NextNode;

	// SLL->DLL 로 변경하면서 새로 생긴 부분 //	
	NewNode->PrevNode = Current;

	if( Current->NextNode != NULL) // Current의 NextNode가 존재시 NextNode의 PrevNode의 연결상태도 변경해야함
	{
		Current->NextNode->PrevNode = NewNode;
	}
	Current->NextNode = NewNode;
	///////////////////////////////////////////

	printf("New Node Inserted             : NewNode's Data = %d \n", NewNode->Data);
}

// 새로운 노드를 Head로 만드는 함수(-링크드 리스트 맨 앞에 노드를 삽입하는 함수)
void DLL_InsertNewHead(Node** Head, Node* NewHead){
	if( (*Head) == NULL){ // Head가 존재하지 않을시 새로운 노드가 Head
		*Head = NewHead;
		printf("New Head Inserted <Head Node> : NewNode's Data = %d \n", NewHead->Data);
	}
	else{ // 기존의 Head가 존재시		
		NewHead->NextNode = (*Head);// 새로운 노드의 NextNode가 기존의 Head가 되고 

		// SLL->DLL 로 변경하면서 새로 생긴 부분 //
		(*Head)->PrevNode = NewHead;
		///////////////////////////////////////////
		(*Head) = NewHead; // 새로운 노드가 Head가 된다.	
		printf("New Head Inserted <Head Node> : NewNode's Data = %d \n", NewHead->Data);
	}
}


// 노드 제거 - 제거할 노드의 메모리 해제 기능까지 자체 추가.
void DLL_RemoveNode(Node** Head, Node* Remove){
	if( (*Head) == Remove){ // 제거할 Remove노드가 Head가 가리키는 노드와 같을시
		*Head = Remove->NextNode; // Head노드가 가리킬 새로운 Node는 기존의 Head의 NextNode

		// SLL->DLL 로 변경하면서 새로 생긴 부분 //
		if( (*Head) != NULL) // 기존의 Head를 삭제후 다른 노드가 헤드가 되었을시
			(*Head)->PrevNode = NULL; // 새로운 Head의 PrevNode는 기존의 Head를 가리키고 있으므로 NULL로 변경
		
		Remove->PrevNode = NULL; // 삭제대상의 PrevNode, NextNode를 NULL로
		Remove->NextNode = NULL; // 삭제되므로 연결고리를 끊는다.

		///////////////////////////////////////////
	}
	else{
		// SLL->DLL 로 변경하면서 새로 생긴 부분 //
		// SLL의 경우 삭제대상 Node의 바로 앞 노드까지 이동을 해서(Loop문으로) 기존 노드들의 연결상태를 바꿔야 했지만
		// DLL 삭제대상의 PrevNode, NextNode의 연결고리를 따라가면 기존 노드들의 연결상태를 쉽게 바꿀수 있다.
		Node* Temp = Remove;

		Remove->PrevNode->NextNode = Temp->NextNode;
		// 삭제대상의 바로 앞의 노드가 가리키는 NextNode를 삭제대상 뒤의 노드로 변경
		if(Remove->NextNode != NULL) // 삭제대상이 마지막 노드가 아닐 시에는
			Remove->NextNode->PrevNode = Temp->PrevNode; // 삭제대상 뒤의 노드도 링크 상태를 변경해주어야 함.
		// 삭제대상 바로 뒤의 노드의 PrevNode가 삭제대상의 PrevNode를 가리킴

		Remove->PrevNode = NULL;
		Remove->NextNode = NULL; // 연결 고리 해제
		///////////////////////////////////////////
	}
	printf("A Node Is Removed             : Removed Node's Data = %d \n", Remove->Data);
	DLL_DestroyNode(Remove); // 삭제할 노드의 메모리 해제!
}

// Location 번째의 노드(0번부터 시작)를 찾아 그 주소를 리턴하는 함수
Node* DLL_GetNodeAt(Node* Head, int Location){
	Node* Current = Head;
	int Temp_Location = Location;

	while(Current!=NULL && (--Location) >= 0){
		// Current가 Tail에 도달 하거나
		// Location이 나타내는 수만큼 노드 이동 연산이 끝났을시 Loop 탈출
		
		// ex) 0번노드 1번노드 2번노드 존재시
		// Location = 1이고 Head는 0번노드를 가리킴
		// - 루프 첫번째
		// Location은 0이 되고 Current = Current->NextNode 수행하고 Current는 1번노드를 가리킴
		// - 루프 두번째 Location이 -1이 되어 loop 탈출 - 따라서 Current는 Location번째 노드를 가리키게 됨
		Current = Current->NextNode;
	}

	// 대충 예외처리
	if(Current!=NULL) // 옳바르게 탐색이 수행됐을시
		return Current;
	else{ // 탐색에 실패했을시
		printf("Error - %d번 노드가 존재하지 않음.\n",Temp_Location);
		return NULL;
	}
}

// 전체 노드의 개수를 얻는 함수
int DLL_GetNodeCount(Node* Head){
	int Node_Count = 0;
	Node* Current = Head;

	while(Current != NULL){
		// ex) 2개의 노드 존재시
		// - 첫번째 루프 - 조건만족 : Current가 1번노드로 이동하고 Count는 1
		// - 두번째 루프 - 조건만족 : Current가 2번노드(NULL)로 이동하고 Count는 2
		// - 세번째 루프 - 루프탈출 : Count 는 2
		Current = Current->NextNode;
		Node_Count++;
	}

	return Node_Count;
}

// Vitamin Quiz 추가 함수

// Current 노드 앞에 NewNode를 삽입하는 함수
void DLL_InsertBefore(Node **Head, Node* Current, Node* NewNode){
	if( (*Head) == Current ) // Current와 Head가 같다면 - 즉 헤드 노드 앞에 삽입하려고 할시 
		DLL_InsertNewHead(Head,NewNode); // SLL_InsertNewHead 함수 호출!
	
	else{
		Current->PrevNode->NextNode = NewNode;
		// Current의 앞노드의 NextNode를 NewNode로
		NewNode->PrevNode = Current->PrevNode;
		// NewNode의 Prev를 기존 Current의 Prev노드로
		NewNode->NextNode = Current;
		// NewNode의 Next를 Current로
		Current->PrevNode = NewNode;
		// Current의 Prev는 NewNode로
		printf("New Node Inserted             : NewNode's Data = %d \n", NewNode->Data);
	}
}

// 모든 노드를 한번에 제거하는 함수
void DLL_DestroyAllNodes(Node **List){	
	int i;
	int Count = DLL_GetNodeCount(*List); // 전체 노드의 갯수를 얻은 후
	Node* Current;

	for(i=0 ; i< Count ; i++){
		Current = DLL_GetNodeAt(*List,0);
		// 0번째 노드를 삭제하게 되면 그 다음 노드가 0번 노드가 되고.. 이런식으로 반복되기 때문에
		// 이걸 현재 노드의 개수만큼 수행하면 모든 노드가 삭제된다.
		DLL_RemoveNode(List, Current);
	}
}


// 노드의 데이터를 역순으로 출력하는 함수
void DLL_PrintReverse(Node* Head){
	Node* Tail = Head;
	int Count = DLL_GetNodeCount(Head); 
	int i;

	// 현재의 Node 개수의 -1만큼 NextNode로 이동시 가장 마지막에 있는 Tail 노드를 얻을 수 있다.
	for(i=0;i< (Count-1);i++)
		Tail = Tail->NextNode;

	// Tail노드에서 다시 Head로 이동(->PrevNode)
	printf("*** 노드의 데이터를 역순으로 출력 *** \n");
		
	while(Tail != NULL){
		printf("%d <-> ",Tail->Data);
		Tail = Tail->PrevNode;
	}
	/* 이렇게 써도 됨. 노드의 개수만큼 PrevNode만큼 이동하면 Head노드의 데이터까지 출력 가능
	for(i=0;i<Count;i++){
		printf("%d <-> ",Tail->Data);
		Tail = Tail->PrevNode;	
	}
	*/
	printf("\n");

}

----------------------------------------------------------------------------------------------------
main.cpp
 

#include "DLL.h"

void Print_State_Of_DLL(Node* List){
	int i=0;
	int Count = DLL_GetNodeCount(List);
	Node* Current = List;

	printf("-----------------------------\n");
	printf("- Current Linked List State -\n");
	printf("-----------------------------\n");
	
	if(Count){
		for(i=0;i < Count; i++){
			printf("%d <-> ", Current->Data);
			Current = Current->NextNode;
		}
		printf("\n");
	}
	else{
		printf("Doesn't Exist Current Linked List\n");
	}

}

int main(){
	int i =0;
	int Count = 0;

	Node*    List = NULL; // Head 노드
	Node* Current = NULL;
	Node* NewNode = NULL;

	// 노드 5개 추가
	for(i=0;i<5;i++){
		NewNode = DLL_CreateNode(i);
		// Node* DLL_CreateNode(ElementType NewData)
		DLL_AppendNode(&List,NewNode);	
		//void DLL_AppendNode(Node** Head, Node* NewNode)
	}

	// 노드 2개 추가 - 링크드 리스트 맨 앞으로 넣음
	NewNode = DLL_CreateNode(18);
	DLL_InsertNewHead(&List,NewNode);
	NewNode = DLL_CreateNode(28);
	DLL_InsertNewHead(&List,NewNode);
	// void DLL_InsertNewHead(Node** Head, Node* NewHead)


	// 추가된 노드들의 데이터 출력
	Print_State_Of_DLL(List);

	
	// 2번째 노드 뒤에 새 노드 삽입
	printf("--------------------------------\n");
	printf("- 2번 노드 뒤에 새 노드를 삽입 -\n");
	printf("--------------------------------\n");

	Current = DLL_GetNodeAt(List,2);
	// Node* DLL_GetNodeAt(Node* Head, int Location)
	NewNode = DLL_CreateNode(22);
	DLL_InsertAfter(Current, NewNode);

	NewNode = DLL_CreateNode(33);
	DLL_InsertAfter(Current, NewNode);
	//void DLL_InsertAfter(Node* Current, Node* NewNode)
	// 추가된 노드들의 데이터 출력
	Print_State_Of_DLL(List);

	// Vitamin Quiz 확인 - 특정 노드 앞에 노드 삽입
	// 2번째 노드 앞에 새 노드 삽입
	printf("******  Vitamin Quiz 확인 ******\n");
	printf("* 2번 노드 앞에 새 노드를 삽입 *\n");
	printf("********************************\n");


	NewNode = DLL_CreateNode(222222);
	Current = DLL_GetNodeAt(List,2);
	DLL_InsertBefore(&List,Current,NewNode);
	// void DLL_InsertBefore(Node **Head, Node* Current, Node* NewHead)
	Print_State_Of_DLL(List); // 추가된 노드들의 데이터 출력

	

	

	// 노드 삭제
	printf("-----------------\n");
	printf("- 0번 노드 삭제 -\n");
	printf("-----------------\n");

	Current = DLL_GetNodeAt(List,0);
	DLL_RemoveNode(&List,Current);
	// void DLL_RemoveNode(Node** Head, Node* Remove)
	Print_State_Of_DLL(List);

	printf("-----------------\n");
	printf("- 5번 노드 삭제 -\n");
	printf("-----------------\n");
	Current = DLL_GetNodeAt(List,5);
	DLL_RemoveNode(&List,Current);
	// void DLL_RemoveNode(Node** Head, Node* Remove)
	Print_State_Of_DLL(List);

	printf("- 예외 처리 확인 -\n");
	Current = DLL_GetNodeAt(List,12);
	printf("\n");

	printf("*******  Vitamin Quiz 확인 *******\n");
	printf("*******  데이터 역순 출력 ********\n");
	printf("**********************************\n");
	DLL_PrintReverse(List);
	
	printf("******  Vitamin Quiz 확인 ******\n");
	printf("*******  모든 노드 삭제 ********\n");
	printf("********************************\n");

	DLL_DestroyAllNodes(&List);
	Print_State_Of_DLL(List);
	
	printf("현재 노드의 개수 : %d\n",DLL_GetNodeCount(List));
	return 0;

}


 
실행결과

'Programming > 뇌를 자극하는 알고리즘' 카테고리의 다른 글

뇌를 자극하는 알고리즘 - 3. 큐 : 순환 큐  (0) 2010.10.05
뇌를 자극하는 알고리즘 2. 스택 - Linked List Stack  (0) 2010.10.02
뇌를 자극하는 알고리즘 2. 스택 - ArrayStack  (1) 2010.10.02
뇌를 자극하는 알고리즘 1. 리스트 - Circle Double Linked List  (2) 2010.10.01
뇌를 자극하는 알고리즘 1. 리스트 - Single Linked List  (4) 2010.09.29