Linked List/영동

예전에 1학년 때 잘못된 방법으로 짠 것을 이제야 제대로(?) 고쳐서 올립니다. 창피한 역사는 빨리 지워버려야...

그냥 링크드 리스트 ¶

#include<iostream>
using namespace std;
struct Node{				//Structure 'Node' has its own data and link to next node 
	int data;				//Data of node
	Node * nextNode;		//Address value of next node
	Node(int initialData){	//Constructor with initializing data
		data=initialData;	//Assign data 
		nextNode='\0';		//Assign null value to address of next node
	}
	Node(){}				//An empty constructor to reduce warning in compile time
	
};
int enterData();			//Function which enter the data of node
void displayList(Node * argNode);	//Function which displays the elements of linked list 
Node * allocateNewNode(Node * argNode, int argData);//Function which allocate new node in memory
int main()
{	
	Node * firstAddress=new Node(enterData());//Create the first address to linked list
	Node * currentNode;//Create temporary node which indicates the last node of linked list
	currentNode=firstAddress;
	
	//Create the next node to linked list
	for(int i=0;i<7;i++)
		currentNode=allocateNewNode(currentNode, enterData());
	displayList(firstAddress);
	return 0;
}
void displayList(Node * argNode)
{
	cout<<"Address\t   Data Value\tNext Address\n";
	Node * tempNode;		//Temporary node to tour linked list
	tempNode=argNode;		
	do{
		cout<<tempNode<<"\t"<<tempNode->data<<"\t"<<tempNode->nextNode<<"\n";
		if(tempNode->nextNode=='\0')//Exit from do-while loop if value of next node is null
			break;
		else				//Go to the next node if there is next node
			tempNode=tempNode->nextNode;
	}while(1);
}
Node * allocateNewNode(Node * argNode, int argData)
{
	argNode->nextNode=new Node(argData);
	return argNode->nextNode; 
}
int enterData()
{
	int returnData;
	cout<<"Node에 들어갈 데이터 값을 입력하시오.";
	cin>>returnData;
	return returnData;
}

[edit]

자유공간리스트(?) 사용 ¶

숙제 스펙(자유공간리스트) 맞추느라 좀 지저분하네요. 조만간 필요없는 부분은 지워서...

#include<iostream>
using namespace std;
struct Node{				//Structure 'Node' has its own data and link to next node 
	int data;				//Data of node
	Node * nextNode;		//Address value of next node
	Node(int initialData){	//Constructor with initializing data
		data=initialData;	//Assign data 
		nextNode='\0';		//Assign null value to address of next node
	}
	Node(){nextNode='\0';}	//An empty constructor to reduce warning in compile time
};
#define MAX_OF_LIST 8		//Maximum number of linked list and free space list 
int enterData();	//Function which enter the data of node
void displayList(Node * argNode);	//Function which displays the elements of linked list 
Node * allocateNewNode(Node * argNode, int argData, int * argNumberOfElements);//Function which allocates new node in memory
Node * reverseList(Node * argNode);//Function which reverses the sequence of the list
void eraseLastNode(Node * argNode, Node ** argFreeNode, int * argNumberOfList, int * argNumberOfFreeSpace);//Function which deletes the last node of the list
void getNode(Node * argNode, Node ** argFreeNode, int * argNumberOfList, int * argNumberOfFreeSpace);//Function which takes the node from free space list
void returnNode(Node * argNode, Node ** argFreeNode, int * argNumberOfList, int * argNumberOfFreeSpace);//Function which return a node of linked list to free space list

int main()
{	
	int elementsOfLinkedList=0;
	int elementsOfFreeSpaceList=0;
	Node * firstAddress=new Node(enterData());//Create the first address to linked list
	elementsOfLinkedList++;//Set 1 to number of node.
	Node * currentNode;//Create temporary node which indicates the last node of linked list
	Node * freeSpaceList=NULL;//Create free space list
	currentNode=firstAddress;
	
	//Create the next node to linked list
	for(int i=0;i<8;i++)
		currentNode=allocateNewNode(currentNode, enterData(), &elementsOfLinkedList);
	
	displayList(firstAddress);
	firstAddress=reverseList(firstAddress);
	displayList(firstAddress);//Display reversed list

	eraseLastNode(firstAddress, &freeSpaceList, &elementsOfLinkedList, &elementsOfFreeSpaceList);
	eraseLastNode(firstAddress, &freeSpaceList, &elementsOfLinkedList, &elementsOfFreeSpaceList);
	eraseLastNode(firstAddress, &freeSpaceList, &elementsOfLinkedList, &elementsOfFreeSpaceList);
	eraseLastNode(firstAddress, &freeSpaceList, &elementsOfLinkedList, &elementsOfFreeSpaceList);

	displayList(firstAddress);//Display the linked list with modified data
	displayList(freeSpaceList);//Display free space list with deleted data from linked list
	
	getNode(firstAddress, &freeSpaceList, &elementsOfLinkedList, &elementsOfFreeSpaceList);
	getNode(firstAddress, &freeSpaceList, &elementsOfLinkedList, &elementsOfFreeSpaceList);
	getNode(firstAddress, &freeSpaceList, &elementsOfLinkedList, &elementsOfFreeSpaceList);
	getNode(firstAddress, &freeSpaceList, &elementsOfLinkedList, &elementsOfFreeSpaceList);

	displayList(firstAddress);//Display the linked list with data which are taken from free space list
	displayList(freeSpaceList);//Display the empty free space list

	returnNode(firstAddress, &freeSpaceList, &elementsOfLinkedList, &elementsOfFreeSpaceList);
	displayList(firstAddress);
	displayList(freeSpaceList);

	return 0;
}
void displayList(Node * argNode)
{
	Node * tempNode;		//Temporary node to tour linked list
	tempNode=argNode;
	cout<<"Address\t   Data Value\tNext Address\n";
	do{
		if(tempNode==NULL)
		{
			cout<<"Sorry... There is no node to display.\n";
			break;
		}
		else
		{
			cout<<tempNode<<"\t"<<tempNode->data<<"\t"<<tempNode->nextNode<<"\n";
			if(tempNode->nextNode==NULL)//Exit from do-while loop if value of next node is null
				break;
			else				//Go to the next node if there is next node
				tempNode=tempNode->nextNode;
		}
	}while(1);
}
Node * allocateNewNode(Node * argNode, int argData, int * argNumberOfElements)
{
	if((*argNumberOfElements)>=MAX_OF_LIST)
	{
		cout<<"Out of maximum size of memory! Your input will be cancelled."<<endl;
		return NULL;
	}
	(*argNumberOfElements)++;
	argNode->nextNode=new Node(argData);
	return argNode->nextNode; 
}
int enterData()
{
	int returnData;
	cout<<"Please input the data to the node.";
	cin>>returnData;
	return returnData;
	
}
Node * reverseList(Node * argNode)
{
	Node * firstTempNode;
	Node * secondTempNode=NULL;
	Node * thirdTempNode=argNode;
	while(thirdTempNode!=NULL)
	{
		firstTempNode=secondTempNode;
		secondTempNode=thirdTempNode;
		thirdTempNode=thirdTempNode->nextNode;//Go one step to next node
		secondTempNode->nextNode=firstTempNode;
	}
	argNode=secondTempNode;//Set address of the last node at first address
	return argNode;
}
void eraseLastNode(Node * argNode, Node ** argFreeNode, int * argNumberOfList, int * argNumberOfFreeSpace)
{
	Node * tempNode=argNode;
	Node * tempPreviousNode;
	Node ** tempFreeNode=argFreeNode;
	if(tempNode==NULL)
		cout<<"You have no node to erase.\n";
	else
	{
		while(tempNode->nextNode!=NULL)
		{//Go to the last node of the linked list
			tempPreviousNode=tempNode;
			tempNode=tempNode->nextNode;
		}//Save the last node and the second node at back
		if(tempNode->nextNode==NULL)
		{//At the last node,
			if((*argNumberOfList)>0 && (*argNumberOfFreeSpace)<MAX_OF_LIST)
			{
				if(*argFreeNode==NULL)
				{//If free space list is empty
					*argFreeNode=tempPreviousNode->nextNode;
					tempPreviousNode->nextNode=NULL;
				}//Link the last node of the linked list to free space list
				else
				{//If free space list has one node at least
					tempNode->nextNode=*argFreeNode;
					*argFreeNode=tempPreviousNode->nextNode;
					(*argFreeNode)->nextNode=(*tempFreeNode)->nextNode;
					tempPreviousNode->nextNode=NULL;
				}/*Link the Free space list to the last node of linked list and
				   link the last node of the linked list to free space list*/
				(*argNumberOfList)--;
				(*argNumberOfFreeSpace)++;
			}
			else
				cout<<"An error occurs in erasing process."<<endl;
		}
	}
}
void getNode(Node * argNode, Node ** argFreeNode, int * argNumberOfList, int * argNumberOfFreeSpace)
{
	Node * tempNode=argNode;
	Node ** tempFreeNode=argFreeNode;
	if(*tempFreeNode==NULL)
		cout<<"You have no node to reuse in free space list.\n";
	else
	{
		while(tempNode->nextNode!=NULL)
		{//Go to the last node of linked list
			tempNode=tempNode->nextNode;
		}
		if((*argNumberOfList)<MAX_OF_LIST && (*argNumberOfFreeSpace)>0)
		{
			if(tempNode->nextNode==NULL)
			{//Link the first node of free space list to the last node of linked list
				tempNode->nextNode=(*tempFreeNode);
				(*tempFreeNode)=(*tempFreeNode)->nextNode;
				tempNode->nextNode->nextNode=NULL;
			}
		}
		else
			cout<<"An error occurs in getting process."<<endl;
	}
}
void returnNode(Node * argNode, Node ** argFreeNode, int * argNumberOfList, int * argNumberOfFreeSpace)
{
	Node * tempNode=argNode;
	Node ** tempFreeNode=argFreeNode;
	Node * tempPreviousNode;
	if(tempNode==NULL)
		cout<<"You have no node to return.\n";
	else
	{
		int returnData;
		cout<<"Input the data value of node that you want to return to the free space list."<<endl;
		cin>>returnData;
		//Input data which you want to return to free space list
		while(tempNode->nextNode!=NULL)
		{//Go to the last node of the linked list
			if((*argNumberOfList)>0 && (*argNumberOfFreeSpace)<MAX_OF_LIST)
			{
				if(tempNode->data==returnData)
				{//Search the data which you entered
					cout<<"You want to return node with "<<returnData<<endl;
					tempPreviousNode->nextNode=tempNode->nextNode;
					if(*argFreeNode!=NULL)
						tempNode->nextNode=(*argFreeNode)->nextNode;
					else
						tempNode->nextNode=NULL;
					*argFreeNode=tempNode;
					(*argNumberOfList)--;
					(*argNumberOfFreeSpace)++;
				}
				else
				{
					tempPreviousNode=tempNode;
					tempNode=tempNode->nextNode;
				}
			}
			else
				cout<<"An error occurs in returning process."<<endl;
		}//Save the last node and the second node at back
	}
}

----
작성자: Yggdrasil
----
LinkedList