[C언어] 연결리스트 - 개념과 기본 동작들(2)

이번 포스팅에서는 연결 리스트에서 특정 노드 뒤에 새로운 노드를 삽입하는 방법과, 연결 리스트에서 노드를 삭제하는 방법에 대해 알아보겠습니다.

---

연결 리스트의 처음이 아닌, 어떤 노드의 뒤에 새로운 노드를 삽입하기 위해선

1. 새롭게 생성할 노드의 next 주소를 prev 노드의 next주소로 변경한 후

2. prev노드의 next 필드를 새롭게 생성한 노드의 주소로 변경하는 것입니다.

Node* add_after(Node* prev, char* name)
{
	if (prev == NULL)
		return 0;
	
	Node* temp = (Node*)malloc(sizeof(Node));
	temp->name = name;
	temp->next = prev->next;
	return temp;
}

위의 코드 블록과 같이 main에서의 prev 주소를 받아온 다음, 동적 할당을 통해 만든 temp에 데이터를 저장하고 연결 리스트를 변경합니다.

---

다음으로는 연결 리스트에서 노드를 삭제하는 방법입니다.

우선 연결 리스트의 첫 번째 노드를 삭제하는 방법은 간단합니다.

Node* remove_first()
{
	if (head == NULL)	// 전역변수 head
		return NULL;	// 예외처리 문장
	else
	{
		Node* temp = head;	// 현재의 head
		head = head->next;	// 여기서 삭제가 발생
		return temp;		// Node는 동적 할당을 받았기 때문에 더 이상 사용하지 않으면 free를 해줘야 함
	}
}

첫 번째 노드의 주소를 가리키는 head의 주소를, 첫 번째 노드의 다음 노드인 head->next로 변경해주기만 하면 됩니다.

remove_fist 함수에서의 temp는 삭제된 노드를 리턴해주는데 이는 혹시 삭제한 노드를 사용할 경우의 함수이고,

삭제한 노드를 더 이상 사용하지 않는다면 동적 할당을 받은 노드를 꼭 free로 메모리 garbage 생성을 막아야 합니다.

---

첫 번째 노드가 아닌, 연결 리스트의 중간에 있는 노드를 삭제하기 위해선, 삭제하려는 노드 이전의 노드 주소가 필요합니다. 삭제할 노드의 주소만으로는 삭제할 노드의 이전 노드와 삭제할 노드의 이후 노드를 연결시킬 수 없기 때문입니다. 때문에 단순 연결 리스트에서 어떤 노드를 삭제할 때는 삭제할 노드의 바로 앞 노드의 주소가 필요합니다.

Node* remove_after(Node* prev)
{
	Node* tmp = prev->next;	// 삭제할 다음 노드
	if (tmp == NULL)
		return NULL;
	else
	{
		prev->next = tmp->next; // prev->next->next
		return tmp;	// 삭제된 노드 리턴
        // 만약 사용하지 않는다면 free를 통해 메모리 반환
	}
}

위의 코드 블록과 같이 삭제할 노드 이전의 노드인 prev 노드를 매개변수로 받아서,

tmp에 삭제할 노드의 주소를 저장한 다음 if문을 통해 prev노드의 next를 삭제될 노드의 next로 변경하여 연결 리스트를 이어줍니다. 그 이후는 remove_first와 동일합니다.