우리는 왜 연결리스트를 사용해야 할까?

연결리스트를 이야기 하기 전에 배열에 대해 먼저 이야기해보자
우리가 배열을 사용하는 이유는 무엇일까?

• 배열을 사용하는 이유
  1선언이 쉽다
  2데이터를 저장하기위해서
  3데이터를 순차적으로 접근한기 위해서

그렇다 우리가 배열을 사용하는 이유는 데이터를 순차적으로 접근하기 위해서다
이사실을 가진상태로 배열의 동적할당에 대해 이야기해보자

배열의 동적할당은 우리가 기존의 알던 배열의 단점을 많이 상쇄시킨다
데이터의 개수에 따른 배열의 크기를 정해줄수있다는 것만으로 우리는 메모리를 더욱 효과적으로
사용할수 있게되었다 하지만 여전히 데이터가 변할때 마다 동적할당을 하며 배열의 메모리를
조절하는 것은 번거로운 작업이다

이러한 문제점을 해결하기위한 것이 연결리스트라는 자료구조이다
연결리스트에 대해 알아보자

연결리스트

앞서 말한대로 연결리스트는 2가지의 기능을 우리에게 제시해야한다
1.데이터를 순차적으로 접근해야한다
2.동적할당의 번거로움을 덜어줘야한다

그렇다면 천천히 연결리스트를 이해해 보자

우리가 메모리를 5개를 할당했다고 생각해보고 그림을 그려보자

무작위 공간의 5개의 메모리가 할당되었다
지금부터 이것들을 연결해보자
그리고 이상태에서 번호를 붙여보자

위의 그림을 보니 배열에서 중요한 순차적인 접근이 가능해진 상태임을 우리는 알수있다
그렇다면 이제 새로운 데이터가 들여오면 어떻게 할까?
새로운 메모리는 첫번쨰<헤드>마지막<테일> 쪽에 붙여주면 되는거다
이러한 연결리스틑 데이터의 순차적접근을 가능하게 하고 새로운 데이터가 추가되면 같다 붙이기만 하면 끝이다

그러면 이제 간단한 코드와 그림을 통해 이해해보자

typedef struct _node
{
	int  data;	//데이터를 담을 공간
    struct _node * next; // 연결도구

}

struct _node * next;
(이것의 역활은 다음 노드를 연결시키는 연결도구라고 그림으로생각해보자)

우리는 하나의 구조체를 정의했다 그구조체를 간단한 그림으로 그려보면

이러한 형태를 노드라고 정의해 보자
이러한 노드를 연결시켜놓으면

연결리스트의 전반적인 형태가 완성되었다
그렇다면 이제 연결리스트의 삽입에 대해 알아보자

연결리스트의 삽입

연결리스트의 삽입을 위해 3개의 포인터 변수를 선언해보자

	typedef struct _node
{
	int  data;	//데이터를 담을 공간
    struct _node * next; // 연결도구

}Node;

//포인터 변수 
Node * head =Null;
Node * tail =Null;
Node * cur =Null;

포인터들의 상황을 그림으로 봐보자
(cur변수의 역활은 나중에 살펴보자)

그렇다면 이제 연결리시트를 만들어보자

	typedef struct _node
{
	int  data;	//데이터를 담을 공간
    struct _node * next; // 연결도구

}

//포인터 변수 
Node * head =Null;
Node * tail =Null;
Node * cur =Null;


newNode = (Node*)malloc(sizeof(Node));
newNode->data = 10;
newNode->next = NULL;

if(head == Null)
	head = newNode;
else
	tail->next = newNode;

tail = newNode;

위의 코드들을 3단계로 나눠서 그림으로 살펴보자

//포인터 변수 
Node * head =Null;
Node * tail =Null;
Node * cur =Null;


newNode = (Node*)malloc(sizeof(Node));
newNode->data = 10;
newNode->next = NULL;

if(head == Null)
	head = newNode;
else
	tail->next = newNode;

tail = newNode;

이제 삽입의 과정을 쭉 나열해본 코드를 보면서 이해 해보자

while(1)
	{
		printf("자연수 입력: ");
		scanf("%d", &readData);
		if(readData < 1)
			break;

		/*** 노드의 추가과정 ***/
		newNode = (Node*)malloc(sizeof(Node));
		newNode->data = readData;
		newNode->next = NULL;

		if(head == NULL)
		{
			head = newNode;
			tail = newNode;
		}
		else
		{
			newNode->next = head;
			head = newNode;
		}
        tail = newNode;
	}