연결 자료구조[단순 연결 리스트]

등장 배경?

순차 자료구조의 문제점의 해결

1. 삽입, 삭제 연산시 순서에 맞는 물리 주소를 유지하기 위한 이동에 대한 OverHead가 발생

2. 배열을 이용한 구현시, 메모리 사용의 비효율 --> 사용하지 않는 공간도 순서를 위해서 할당 시켜야함.

--> 이러한 문제점을 해결하기 위해서 연결 자료구조가 등장

연결 자료구조

자료의 논리적인 순서와 물리적인 순서가 일치하지 않는 자료구조

각 원소에 저장되어 있는 다음 원소의 주소에 의해 순서가 연결되는 방식

--> 물리적이 주소를 맞추기 위한 OverHead가 발생하지 않음.

여러 개의 작은 공간을 연결하여 하나의 전체 자료구조 표현

--> 종합하면 필요 하지 않은 것은 할당하지 않아도 되고, 꼭 연속적일 필요도 없고

     조각 조각난 메모리로도 자료구조를 표현 할 수있다.

연결 리스트

리스트를 연결 자료구조로 표현하는 구조

--> 자료구조 공부는 이론을 기반으로 코딩하는게 가장 효율적이고 잼있는것 같다.

단순 열결 리스트[Singly Linked List]

노드가 하나의 링크 필드에 의해서 다음 노드와 연결되는 구조를 가진 연결 리스트

마지막 노드에 추가

노드 수정

마지막 노드 삭제

중간 노드 추가

중간 노드 삭제

--> 약간의 오류가 있을수도... 

삭제, 추가 할 때 tmp_Node의 순서가 중요하다?!

정도 느꼈음.

###############################################################################

#include "stdio.h"

#include "stdlib.h"

#include "string.h"



//구조체

typedef struct Node{

	char data[4];

	struct  Node* link; 

	//Node의 주소를 저장 할 변수

};



Node* Init_Node();

void Modify_Node(Node* node, char* Find_Data, char* Data);

void Insert_Node(Node* node,char* Data);

void Delete_Node(Node* node);

void Middle_Insert_Node(Node* node, char* Find_Data, char* Data);

void Middle_Delete_Node(Node* node, char* Find_Data);

void Print(Node* node);

void Delete_Last_Node(Node* node);

int main()

{

	Node* Start = Init_Node();

	strcpy_s(Start->data, "월");

	Insert_Node(Start, "화");

	Insert_Node(Start, "수");

	Insert_Node(Start, "목");

	Middle_Delete_Node(Start, "화");

	Print(Start);

	printf("\n\n");

	Modify_Node(Start, "수", "금");

	Print(Start);

	printf("\n\n");

	Insert_Node(Start, "화");

	Middle_Insert_Node(Start, "화", "하");

	

	Print(Start);

	



	printf("\n\n");

	Delete_Last_Node(Start);

	Delete_Last_Node(Start);

	Delete_Last_Node(Start);

	Print(Start);

	system("pause");

}



Node* Init_Node()

{

	Node* Init = (Node*)malloc(sizeof(Node));

	memset(Init, 0x00, sizeof(Node));

	Init->link = NULL;

	return Init;

}





void Insert_Node(Node* node, char* Data)

{

	Node* new_Node = (Node*)malloc(sizeof(Node));

	

	while (node->link != NULL)

	//마지막 노드를 만날때 까지 반복

	{

		node = node->link;

	}



	node->link = new_Node;

	strcpy_s(new_Node->data, Data);

	new_Node->link = NULL;

}



void Middle_Insert_Node(Node* node, char* Find_Data, char* Data)

{

	Node* new_Node = (Node*)malloc(sizeof(Node));

	Node* tmp_Node = NULL;

	while (node->link != NULL )

	{

		if (strcmp(node->data, Find_Data) == 0)

		{

			new_Node->link = node->link;

			tmp_Node->link = new_Node;

			break;

			

		}

		node = node->link;

		tmp_Node = node;

	}

	strcpy_s(new_Node->data, Data);

}

void Print(Node* node)

{

	while (node->link != NULL)

	{

		printf("%s\n", node->data);

		node = node->link;

	}



	printf("%s\n", node->data);



}





void Modify_Node(Node* node, char* Find_Data, char* Data)

{

	while (strcmp(node ->data,Find_Data) !=0)

	{

		node = node->link;

	}

	strcpy_s(node->data, Data);

}



void Middle_Delete_Node(Node* node, char* Find_Data)

{

	

	Node* tmp_Node = NULL;

	while (node->link != NULL)

	{

		if (strcmp(node->data, Find_Data) == 0)

		{

			tmp_Node->link = node->link;

			break;



		}

		tmp_Node = node;

		node = node->link;

		

	}

}

void Delete_Last_Node(Node* node)

{

	Node* tmp_Node = NULL;

	while (node->link != NULL)

	{

		tmp_Node = node;

		node = node->link;



	}

	tmp_Node->link = NULL;



}