[단일 연결 리스트 2] 노드 맨 앞 삽입(Insertion) | 스택 (stack)

단일 연결 리스트에서 노드를 맨 앞에 추가하는 방법에 대해 알아보자. 노드를 맨 앞에 삽입한다는 것은 리스트의 가장 처음 위치에 새로운 노드를 추가하는 작업을 의미한다. 이를 통해 새 노드는 기존 첫 번째 노드가 되고, 이전 첫 번쨰 노드는 새 노드 뒤로 밀리게 된다. 노드 맨 앞 삽입은   한쪽 방향으로 데이터의 삽입(push)과 삭제(pop)가 이루어지는 스택(stack) 을 구현할 때 사용하고 스택은 LIFO(Last In, First Out) 구조를 따른다. 

 

 

 

1. 노드 구조체 선언 

연결리스트의 각 노드는 값을 저장할 공간과 포인터를 저장할 공간이 한 세트로 필요하기 때문에 구조체를 할당해준다. 

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

 

2. 헤드 포인터 선언 및 초기화

연결 리스트는 노드가 비연속적으로 할당이 되어 있기 떄문에 첫번쨰 값이 뭔지를 별도로 표시해주어야 한다. 이를 위해서는 head 를 선언하고 그 안에 첫 번쨰 노드의 주소값을 할당해서 첫 번쨰 노드가 어디있는지 알려준다.

 

그런데 처음에는 노드가 없으니까 'NULL' 로 초기화한다. 

node* head = NULL;

 

3. 노드 생성

이제 malloc 으로 각 노드의 메모리 공간을 동적 할당하기 위해 1번에서 만들었던 node 구조체 크기 만큼의 메모리 공간을 만들어준다. 이 생성된 메모리는 주소를 리턴하니까 반드시 포인터로 저장을 해주어야 한다. 

(64bit 시스템에서) 8byte 짜리 포인터 newNode는 포인터이고 포인터니까 새로 생성된 노드의 주소를 가리키는 상태가 되는 상태로 만들어주면 된다. malloc 으로 할당된 메모리 주소는 node 타입의 주소니까 형 변환은 node type 의 포인터로 할당해주면 된다. 

 

이제 head는 NULL로 잡히고 malloc 으로 노드를 생성한걸 newNode라는 포인터 변수가 가리키는 상태까지 완성했다.

 

 

 

4. 데이터 입력 및 노드 연결 

첫 번째 노드에 데이터가 입력되는 과정이다. 맨 처음 scanf 를 사용해서 노드의 데이터를 입력받는다.

scanf("%d", &newNode->value);

 

아직 노드가 1개이고 그 다음에 가리킬 노드가 없으니까 넥스트 포인터에는 NULL 값을 준다. 

newNode->next = NULL; //다음 값이 아직은 없으니까 NULL을 줌

 

head 는아무것도 안가리키는 상태이기 떄문에 주소값을 저장하고 있는 변수 newNode 값을 저장해서

첫 번쨰 노드의 주소값을 가리키게 해준다. 그 다음 더 할게 없으니까 return 값으로 함수를 종료한다. 

if (head == NULL) {  //처음 생성된 노드의 값을 head 에 입력
	head = newNode;
	return; // 함수 종료 
}

 

 5. 새로운 노드를 맨 앞에 추가 

두 번의 스텝이 필요하다. 

 head 를 그 다음 노드를 가리키도록 만들어서 생성된 역순으로 노드를 추가해준다. 예를 들어서 3,4,5 순으로 노드를 생성했다고 하면 새로운 노드가 뒤가 아니라 맨 앞에 계속해서 붙으니까 5,4,3 순으로 연결이 된다.  

 

head 의 값을 새로운 노드의 포인터에 이전 노드의 값에 연결한다. 

 

 

 head가 그 다음 노드를 가리키도록 만들어서 생성된 역순으로 노드가 추가될 수 있게 설정한다. 

 

	//생성된 역순으로 노드를 추가
	newNode->next = head; 
	head = newNode;
}

 

<전체 코드>

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

#pragma warning (disable : 4996)

typedef struct node
{
	int value; // 값 
	node* next; //다음 노드의 주소를 저장하는 포인터(8byte_
}node;

node* head = NULL; // 첫 노드를 저장하는 포인터(8byte); // 전역변수 

int main() {
	int choice;

	while (1)
	{
		system("cls");
		printf("\n\n*** 단일 연결 리스트(Singly Linked List) ***\n\n");
		printf("1. 노드 삽입(맨 앞) \n");
		printf("10. 단일 연결 리스트 출력 \n");
		printf("0. 프로그램 종료");

		printf("\n 메뉴 선택");
		scanf("%d", &choice);
		while (getchar() != '\n');

		switch (choice)
		{
		case 1:
			break;
		case 10:
			break;
		case 0:
			exit(0);
		}
		printf("\n\n\t\t");
		system("pause");
	}
	return 0;
}

	void insert_node_front(int data){
		node* new_node;
		new_node = (node*)malloc(sizeof(node));
		new_node->value = data;
		new_node->next = NULL;

		if (head == NULL) {
			head = new_node;
			return;
		}

		new_node->next = head;
		head = new_node;
}