단순연결리스트

 

 

 

 

 

 

단순연결리스트 [Singly linked list] 

 

 

#include 

struct Node
{
	int          data;
	struct Node* next;
};

void PrintNodes(struct Node* root)
{
	Node* temp = root;
	printf("--------------NODES--------------\n");
	int i = -1;
	while( temp != NULL){
		if(i == -1) printf("root");
		else
		{
			printf("pos");
			printf("%d", i);
		}
		printf(": ");
		printf("%d", (int)temp);
		printf(" / data: ");
		printf("%d", temp->data);
		printf(" / next: ");
		printf("%d", (int)temp->next);
		printf("\n");
		temp = temp->next;
		i++;
	}printf("---------------------------------\n");
}

Node* CreateNode(Node* newnew)
{
	newnew = new Node;
	newnew->data = 0;
	newnew->next = NULL;
	return newnew;
}

int GetNodeCount(Node* root)
{
	int count = 0;
	Node* temp = root;
	while( temp->next != NULL )
	{
		count++;
		temp = temp->next;
	}
	return count;
}

Node* GetNode(Node* root, int pos)
{
	int count = 0;
	Node* get = root;
	while( get->next != NULL)
	{
		get = get->next;
		if( count == pos ) break;
		count++; 
	}
	return get;
}

int Insert(struct Node* root, int position)
{
	Node* NewNode = NULL;
	NewNode = CreateNode(NewNode);
	Node* prev = NULL;
	prev = GetNode(root, position-1);

	if(GetNodeCount(root) < position) return 0; //없는거 못 만든다.
	if( position == GetNodeCount(root) )
	{
		prev->next = NewNode;
		return 1;
	}
	else
	{
		Node* after = NULL;
		after = GetNode(root, position);
		if( position==0 ) root->next = NewNode;
		else    prev->next = NewNode;
		NewNode->next = after;
		return 1;
	}
	return 0;
}

int Delete(struct Node* root, int position)
{
	int a = GetNodeCount(root);
	if(GetNodeCount(root) <= position) return 0; //없는거 못 지운다.
	else
	{
		Node* deletedNode = NULL;
		deletedNode = GetNode(root, position);
		Node* afterDeletedNode = NULL;
		afterDeletedNode = GetNode(root, position+1);
		if(position == 0) 
			root->next = afterDeletedNode; //첫번째꺼 지우면 root에 나머지 연결
		else
		{
			Node* prevDeletedNode = NULL;
			prevDeletedNode = GetNode(root, position-1);
			int a = GetNodeCount(root);
			if(position == GetNodeCount(root)-1) 
				prevDeletedNode->next = NULL;
			else 
				prevDeletedNode->next = afterDeletedNode;
		}
		delete deletedNode;
		return 1;
	}
}

int SetData(struct Node* root, int position, int data)
{
	if( root->next != NULL && GetNodeCount(root) > position )
	{
		GetNode(root,position)->data = data;
		return 1;
	}
	else return 0;
}

int GetData(struct Node* root, int position, int* data)
{
	if( root->next != NULL && GetNodeCount(root) > position )
	{
		*data = GetNode(root,position)->data;
		return 1;
	}
	else return 0;
}

void main()
{
	Node* root = NULL;
	root  = CreateNode(root);
	int data = 0;

	/* position==0 created */	printf("%d ", Insert(root,0));  printf(" inserted \n");
	/* position==0 set to 7 */	printf("%d ", SetData(root,0,7)); printf(" set \n");
	/* position==1 created */	printf("%d ", Insert(root,1));  printf(" inserted \n");
	/* position==0 added */		printf("%d ", Insert(root,0));  printf(" inserted \n");
	/* --> 원래 있던 노드 밀어냄 */

	/* position==3 created */	printf("%d ", Insert(root,3));  printf(" inserted \n");
	/* position==3 deleted */	printf("%d ", Delete(root,3));  printf(" inserted \n");
	/* position==5 created */	printf("%d ", Delete(root,5));  printf(" inserted \n");
	/* --> 앞에 빈 노드 있으므로 생성 못함 */

	/* position==3 created */	printf("%d ", Insert(root,3));  printf(" inserted \n");
	/* position==2 set to 5 */	printf("%d ", SetData(root,2,5)); printf(" set \n");
	/* position==3 set to 6 */	printf("%d ", SetData(root,3,6)); printf(" set \n");
	/* position==7 get  */		GetData(root, 7, &data);  printf("%d ", data);   printf(" got \n");
	/* --> 빈 노드이므로 데이터 얻지 못함 */

	/* position==2 get  */		GetData(root, 2, &data);  printf("%d ", data);   printf(" got \n");

	PrintNodes(root);
	printf("total nodes: "); printf("%d ", GetNodeCount(root)); printf("\n\n");
	delete root;
}