Linked List 구현하기 (1)

이 글에서는 Linked List의 전체 읽기, 전체 삭제에 관해서 작성할 생각입니다. 원하는 노드를 읽는 건 다음 시간에 해보도록 하겠습니다.

#include <stdio.h>
#include <stdlib.h>

typedef struct _node {
	int data; // 데이터를 담는 바구니
	struct _node* next; // 연결의 도구
}Node;

int main(void) {
	Node* head = NULL; // 리스트의 머리
	Node* tail = NULL; // 리스트의 꼬리
	Node* cur = NULL; // 리스트의 조회에 사용되는 변수

	Node* newNode = NULL;
	int readData;

	// 데이터 입력 받는 과정
	while (1) {
		printf("자연수 입력 ");
		scanf_s("%d", &readData);
		if (readData == 0) {
			break;
		}
		newNode = (Node*)malloc(sizeof(Node)); // 필요할 때마다 바구니의 역할을 하는 구조체 변수를 하나씩 동적 할당해서 이들을 연결한다.
		newNode->data = readData; // 노드에 데이터 저장
		newNode->next = NULL; // 노드의 next를 NULL로 초기화

		if (head == NULL) // 첫 번째 노드라면
			head = newNode; // 헤드를 첫 번째 노드에 가리키게 함
		else // 그게 아니면
			tail->next = newNode; // 꼬리 다음에 노드가 들어가고 

		tail = newNode; // tail을 노드에 가르키게 함
	}
	printf("\n");

	// 입력 받은 데이터의 출력과정
	printf("입력 받은 데이터의 전체 출력! \n");

	if (head == NULL)
		printf("저장된 자연수가 존재하지 않습니다. \n");
	else
	{
		cur = head; // cur이 첫 번째 노드를 가르킴
		printf("%d ", cur->data); // 첫 번째 데이터 출력

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

	// 메모리의해제과정
	if (head == NULL) {
		return 0; // 삭제할 노드가 존재하지 않는다.
	}
	else {
		Node* delNode = head;
		Node* delNodenext = head->next; // head를 그냥 삭제하면 다음 노드를 참조할 변수가 없다.

			printf("%d을(를) 삭제합니다. \n", delNode->data);
		free(delNode); // 첫 번째 노드 삭제

		while (delNodenext != NULL) { // 두 번째 이후 노드 삭제
			delNode = delNodenext;
			delNodenext = delNodenext->next;

			printf("%d을(를) 삭제합니다. \n", delNode->data);
		}
	}
	return 0;
}

---

그렇다면 숫자를 tail 부분에 넣는 것이 아닌 head 앞에 계속 쌓아가는 것은 어떻게 할까요? 다시 말해서 우리가 3, 2, 5, 8, 7 이라는 숫자를 입력한다 했을 때, Linked List의 연결은 7, 8, 5, 2, 3이 되게 하고 싶습니다. 그러기 위해서 노드에 하나의 인자를 더 추가했습니다. 바로 next가 아닌 prev입니다. 이 전의 값을 알려주는 prev에 새로운 노드가 들어올 때 마다 넣어주면 새로운 연결을 할 수 있습니다.

#include <stdio.h>
#include <stdlib.h>

typedef struct _node {
	int data; // 데이터를 담는 바구니
	struct _node* next; // 연결의 도구
	struct _node* prev; // 연결의 도구 2
}Node;

int main(void) {
	Node* head = NULL; // 리스트의 머리
	Node* tail = NULL; // 리스트의 꼬리
	Node* cur = NULL; // 리스트의 조회에 사용되는 변수

	Node* newNode = NULL;
	int readData;

	// 데이터 입력 받는 과정
	while (1) {
		printf("자연수 입력 ");
		scanf_s("%d", &readData);
		if (readData == 0) {
			break;
		}
		newNode = (Node*)malloc(sizeof(Node)); // 필요할 때마다 바구니의 역할을 하는 구조체 변수를 하나씩 동적 할당해서 이들을 연결한다.
		newNode->data = readData; // 노드에 데이터 저장
		newNode->next = NULL; // 노드의 next를 NULL로 초기화
		newNode->prev = NULL; // 노드의 prev를 NULL로 초기화

		if (head == NULL) // 첫 번째 노드라면
			head = newNode; // 헤드를 첫 번째 노드에 가리키게 함
		else { // 그게 아니면
			head->prev = newNode; // 꼬리 다음에 노드가 들어가고 
			newNode->next = head // 뒤에 있던 친구의 next를 지정해주어야 합니다.
		}
		head = newNode; // tail을 노드에 가르키게 함
	}
	printf("\n");

	// 입력 받은 데이터의 출력과정
	printf("입력 받은 데이터의 전체 출력! \n");

	if (head == NULL)
		printf("저장된 자연수가 존재하지 않습니다. \n");
	else
	{
		cur = head; // cur이 첫 번째 노드를 가르킴
		printf("%d ", cur->data); // 첫 번째 데이터 출력

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

	// 메모리의해제과정
	if (head == NULL) {
		return 0; // 삭제할 노드가 존재하지 않는다.
	}
	else {
		Node* delNode = head;
		Node* delNodenext = head->next; // head를 그냥 삭제하면 다음 노드를 참조할 변수가 없다.

			printf("%d을(를) 삭제합니다. \n", delNode->data);
		free(delNode); // 첫 번째 노드 삭제

		while (delNodenext != NULL) { // 두 번째 이후 노드 삭제
			delNode = delNodenext;
			delNodenext = delNodenext->next;

			printf("%d을(를) 삭제합니다. \n", delNode->data);
		}
	}
	return 0;
}

---

이상 Linked List 구현하기 (1)이었습니다. ^_^