[자료구조]03. 연결 리스트-자료구조

#include <stdio.h>

int main(void) {
	int arr[10];
	int readCount = 0;
	int readData;
	int i;
		while(1)
		{
			printf("자연수 입력");
			scanf_s("%d", &readData);
			if (readData < 1)
				break;

			arr[readCount++] = readData;

		}
	for (i = 0; i < readCount; i++)
		printf("%d", arr[i]);
	return 0;
}

배열의 단점은 길이의 변경 불가능이다. 위의 예제에서 0이하의 값을 입력하지 않고 자연수만 입력을 하면 할당된 배열의 길이을 넘어선다.

그래서 메모리의 크기를 유연하게 하기 위해 등장한 것이 ' 동적인 메모리의 구성'이다.

이것이 오늘 내가 공부한 부분이다.

이제 예시 코드 하나를 가지고 공부를 해볼 것이다.

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

정의된 구조체를 살펴보면 구조체의 멤버 next는 포인터 변수로 연결의 도구. 구조체 멤버 data는 데이터를 담을 공간이라고 생각하면 이해하기 쉽다. 

data는 데이터를 담을 공간으로 선언하였고 , next는 포인터 변수로 연결의 도구라고 하였는데

무엇을 연결할려고 선언됐을까?

바로 data들을 연결할려고 선언된 멤버이다. 즉 data라는 바구니들을 연결하기 위해 선언된 멤버이다.

next를 통해서 모든 바구니들을 연결하는 것이 가능하다. 즉 Node형 구조체 변수들을 연결하는 것이 가능하다.

 

연결리스트의 기본 원리 

 

 

 

 

 

연결리스트- 데이터 삽입

int main(void)
{// NULL 포인터 초기화
	Node* head = NULL;// 리스트의 머리를 가리키는 포인터 변수    
	Node* tail = NULL;//리스트의 꼬리를 가리키는 포인터 변수
	Node* cur = NULL;//저장된 데이터를 조회할 때 사용되는 데이터 변수 

	Node* newNode = NULL;//
	int readData;

연결리스트의 초기 상태

코드에서 보다싶이 head, tail, cur은 연결리스트에서 중요한 역할을 하는 포인터 변수들이다.

위의 그림은 포인터 변수들이 선언된 상황을 그림으로 표현한 것이다.

cur은 이후 리스트 안을 돌아다닐 때 사용된다.

 

데이터 입력 시 연결리스트의 상태- 코드분석 및 그림으로 나타내기

/**** 데이터를 입력 받는 과정 ****/
	while (1)
	{
		printf("자연수 입력: ");
		scanf("%d", &readData);
		if (readData < 1)
			break;

		/*** 노드의 추가과정 ***/
		newNode = (Node*)malloc(sizeof(Node));// 바구니를 생성한다.
		newNode->data = readData;// 바구니(노드)에 데이터를 저장한다.
		newNode->next = NULL;// 노드의 next를 null로 초기화한다.

		if (head == NULL) // 만약 첫번째 노드라면
			head = newNode; // 첫번째 노드를 head를 가리키고 있게한다.
		else 
			tail->next = newNode; // 그렇지 않다면 노드의 끝을 tail이 가리키게 한다. 

		tail = newNode;
	}
	printf("\n");

 

 

 

 

 

코드에 대한 분석은 주석으로 달아놓았다. 

 

 

 

이 그림은 데이터를 사용자로 부터 입력받았을 때의 노드 상태로 head와 tail이 null로 초기화된 상태이다.

 

 

이후 만약 첫번째 노드라면 첫번째 노드를 head를 가리키고 있게 한 상태이다.

두번째 노드를 tail이 가리키는 노드의 뒤에 연결되어야 하기 때문에 새 노드를 생성하고 초기화 한뒤에는 else 구문이 실행되어 위의 그림과 같은 상태가 된다.

"head"는 첫번째 노드를, "tail"은 마지막 노드를 가리킨다.

 

연결리스트- 데이터 조회

/**** 입력 받은 데이터의 출력과정 ****/
	printf("입력 받은 데이터의 전체출력! \n");
	if (head == NULL)
	{
		printf("저장된 자연수가 존재하지 않습니다. \n");
	}
	else
	{
		cur = head;
		printf("%d  ", cur->data);   // 첫 번째 데이터 출력

		while (cur->next != NULL)    //만약 연결된 노드가 존재한다면
		{
			cur = cur->next;// cur은 다음 노드를 가리킨다.
			printf("%d  ", cur->data);
		}
	}
	printf("\n\n");

위의 코드에서 중요한 부분은 cur->next이다.

위의 문장으로 인해 cur은 모든 노드를 가리키면서 이동하게 된다.

 

연결리스트- 데이터 삭제

삭제는 head가 가리키는 노드의 삭제를 위해서 두개의 포인터 변수를 이용하여 삭제한다.

head가 가리키는 노드를 그냥 냅다 삭제해버리면--> 그다음 노드에 접근 불가

그래서 삭제될 노드가 가리키는 다음 노드의 주소 값을 delNextNode라는 포인터 변수를 이용해 별도로 저장해둔다.

첫번째 노드를 삭제하고 난 뒤에는 delNextNode를 참조하여 추가로 삭제할 노드가 있는지 확인한 다음,

두 포인터 변수가 한칸씩 오른쪽으로 이동한다.

즉 삭제 과정을 한마디로 요약하면 

" 반복문을 사용해 delNode와 delNextNode를 한칸 씩 이동시키면서 delNode가 가리키는 대상을 소멸하는 것이다."

이 과정을 마지막 노드가 소멸될 때까지 진행하면 모든 노드를 삭제된다.