[자료구조] 연결리스트 노드 삭제

단순 연결리스트의 노드 삭제

1. pre가 NULL인 경우: 선행 노드가 없는 경우
2. pre가 NULL아 아닌 경우: 선행 노드가 있는 경우

 

1. pre가 NULL인 경우: 선행 노드가 없는 경우

• 연결 리스트의 첫 번째 노드를 삭제하고 헤드 포인터 변경 

// head : 헤드 포인터
// x: 삭제될 노드가 가진 데이터
void remove_node(Node *head, int x) 
{
	Node *list = head;

	if( head == NULL )  return; 	// 삭제할 것이 없음
	else if( head->data == x ) 	// 찾는 노드(삭제 노드)가 첫 노드인 경우 
	{      // delete list; free(list);
	        head = head->link;
	        return;
	}
	else 			// 나머지 경우
	{        while(list->link != NULL)
	          {     	if( list->link->data == x ) 
		{	list->link = list->link->link;
			//delete list; free(list->link);
			return;
		}
		list = list->link;
	           }
	}
}

 

2. pre가 NULL이 아닌 경우: 선행 노드가 있는 경우

• 해당 노드(중간 노드)를 삭제하고 pre의 링크가 다음 노드를 가리키도록 변경

// head : 헤드 포인터
// pre: 삭제될 노드의 선행 노드
// removed: 삭제될 노드 
void remove_node(Node *head, Node *pre, Node *removed) 
{
	if( head == NULL) return;		// 빈 리스트의 경우
	else if( pre == NULL ) head = head->link; 	// 삭제할 노드가 첫 노드인 경우
	else pre->link = removed->link; 		// 나머지 경우
	delete removed; //free(removed);	// 삭제된 노드를 반환		
}

 

예제) 연결 리스트 노드 삭제

- 60을 가진 노드를 찾아, 연결 리스트에서 삭제하시오.
- 삭제가 제대로 잘 되었는지, 전체 리스트를 출력해 보시오.

#include <iostream>
using namespace std;

class Node {
public:
	int score; //점수
	Node *link; //다음 노드 주소
};
Node *Head = NULL;

//리스트 마지막에 노드 삽입 방법
void insert_at_rear(Node *new_node) {
	if (Head == NULL) {
		Head = new_node;
	}
	else {
		//마지막 노드를 찾고, 그 노드 뒤에 new_node 연결
		Node *list = Head; //list는 포인터이며 초기값은 head
		while (list->link != NULL) //list의 link값이 null일 경우 끝남 
			list = list->link;
		list->link = new_node;
	}
}

//리스트 처음에 노드 삽입 방법
void insert_node_at_front(Node *new_node)
{
	new_node->link = Head;
	Head = new_node;
}

Node *MakeNewNode(int score) { //노드를 하나 동적 할당, 값 초기화
	Node *ptr;
	ptr = new Node();
	ptr->score = score;
	ptr->link = NULL;
	return ptr;
}

void printNodes() {
	for (Node *list = Head; list != NULL; list = list->link)
		//list != NULL 뜻: 리스트가 뭔가를 가리키고 있으면. list == NULL 뜻: 리스트가 가리키는 방이없다는 뜻
		cout << list->score << endl;
}

void findNode(int score) {
	for (Node *list = Head; list; list = list->link)
		//C언어에서는 0만을 거짓으로 본다. 따라서 list != NULL을 그냥 list로 쓰는 경우도 있다.
		if (list->score == score)
			cout << "I found it : " << list->score << endl;
}

//노드 삭제 (key값을 가진 노드를 찾아서 지우는 방법)
void delete_node(int key) {
	Node *list = Head;
	if (Head == NULL)
		return;
	else if (Head->score == key) { //첫 노드를 지우려는 경우
		Head = Head->link;
		return;
	}
	else { //일반적인 경우
		while (list->link != NULL) //다음 노드가 있는 동안
		{
			if (list->link->score == key) { //다음 노드가 우리가 찾는 노드면
				list->link = list->link->link;
				return;
			}
			list = list->link;
		}
	}
}

//노드 카운트
void NodeCount() {
	int cnt = 0; //카운트 초기화

	for (Node *list = Head; list != NULL; list = list->link)
		cnt++;
	cout << "Node Cnt = " << cnt << endl;
}

void main() {
	Node *new_node;
	int std_num; //학생수

	cout << "Student Number : ";
	cin >> std_num; //학생수 입력

	for (int i = 0; i < std_num; i++)
	{
		int score;
		cout << "Student #" << i + 1 << " : ";
		cin >> score;

		//노트 생성, 연결리스트에 추가
		new_node = MakeNewNode(score);
		insert_at_rear(new_node);

	}
	printNodes();
	NodeCount();

	cout << "AFTER DELETION" << endl;

	//노드 삭제 테스트
	delete_node(60);
	printNodes();
	NodeCount();
}