[단일 연결 리스트] 노드 맨 뒤 삽입

노드 맨 앞 삽입과 반대로 새로운 값이 제일 뒤에 붙는 연결 리스트이다. 

노드 맨 뒤 삽입은 N만큼의 데이터가 있으면 N만큼 순회를 하기 때문에  O(N)의 시간 복잡도를 가지게 된다. 

이를 구현하기 위해서는 일단 내가 연결하고자 하는 노드가 첫 번째 노드인지 아닌지 판별해야 하고 newNode가 NULL을 가리키기 해서 첫 번째 노드와 연결시켜준다. 그 다음 head 가 빈 값이라면 newNode 값을 넣어서 head가 첫번째 노드를 가리키게 한다.  

 

typedef struct node{
	int value;
	struct node* next;
}node;

node* head = NULL; // 초기값을 NULL로 설정

void insert_node_rear() {
	node* newNode;
	newNode = (node*)malloc(sizeof(node)); 
	scanf("%d", &newNode->value); 
	newNode->next = NULL;

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

 

이제 3,4,5 노드가 있는 상태에서 6번 노드를 추가해야 하는 상황이라고 가정해보자. 

6번 노드가 맨 뒤에 붙기 위해서는 head부터 마지막 노드까지 순회를 하고 5번 노드의 NULL 값을 찾아서 5번 노드와 6번노드를 연결해주어야 한다. 

 

노드를 순회하기 위해  curNode 를 만든 후 첫 번째 노드부터 순회해야 하니까 curNode에 head 값을 넣고 NULL 값을 안만날때까지 각 노드를 순회한다. curNode가 NULL 을 가리키게 되면 , while 반복문을 빠져나온다. 

node* curNode; 
curNode = head;
while (curNode->next != NULL) {
	curNode = newNode->next;
}

이제 새로 생성한 노드와 기존 맨 끝 노드 5번을 연결하기 위해서 curNode->next 에 newNode 의 주소를 넣어준다. 

curNode->next = newNode;