C++의 연결된 목록에서 노드 삭제
이 기사에서는 연결된 목록 C++에서 주어진 노드를 삭제하는 함수를 구현하는 방법에 대해 설명합니다.
연결된 목록에서 주어진 노드를 삭제하는 기능 구현
이 기사에서는 STL의 컨테이너를 사용하지 않고 처음부터 단일 연결 목록을 구현합니다. 따라서 연결 목록에서 노드를 관리하는 데 필요한 몇 가지 기능을 정의해야합니다.
insertNode요소는 새 연결 목록을 작성하기 위해 호출해야하는 핵심 기능입니다. 목록의 헤드를 저장해야하므로insertNode는ListNode유형의 노드에 대한 포인터를 리턴합니다. 후자는 연결 목록 노드의 최소 표현입니다. 다음 노드와string데이터 오브젝트에 대한 포인터 만 포함합니다.
프로그램을 테스트하고 시연하는 동안 사용자 콘솔에 일부 메시지를 표시하는 유틸리티 기능을 갖는 것이 중요합니다. 이 경우printNodes요소는 주어진 목록 구조의 모든 노드를 인쇄하는 데 사용됩니다. 또한 동적 메모리에 새 노드를 할당 할 때freeNodes기능을 사용하여 프로그램 종료시 목록에있는 모든 기존 노드의 할당을 해제해야합니다.
다음 코드 스 니펫의main함수에 표시된대로 임의의 데이터로 목록을 구성했으면 노드 제거 작업을 구현하는deleteNode를 호출 할 준비가 된 것입니다. 노드를 제거하려면 여러 코너 케이스를 처리해야합니다. 즉, 주어진 노드가 목록의 헤드와 동일하고 주어진 노드가 목록에서 유일한 노드 인 다른 시나리오입니다.
후자의 시나리오에서는 노드 포인터에서delete연산자를 호출하고 함수에서 반환 할 수 있습니다. 주소에nullptr를 할당하는 것이 중요하지만 이는 주 함수의 동일한head변수에 새 요소를 추가하는 데 도움이되기 때문입니다.
반면 목록에 다른 노드가있을 때 헤드 노드를 제거하는 것은 상대적으로 까다 롭습니다. 두 번째 노드의 내용을 헤드 노드에 복사하고 이전 노드를 삭제해야합니다. 각 케이스는 성공적인 함수 호출을 나타 내기 위해EXIT_SUCCESS값을 반환합니다.
#include <iostream>
#include <string>
using std::cin;
using std::cout;
using std::endl;
using std::string;
struct ListNode {
struct ListNode *next{};
string data;
};
struct ListNode *insertNode(struct ListNode *root, string data) {
auto new_node = new ListNode;
if (root) {
while (root->next) root = root->next;
new_node->next = nullptr;
new_node->data = std::move(data);
root->next = new_node;
return root->next;
}
new_node->next = nullptr;
new_node->data = std::move(data);
return new_node;
}
int deleteNode(struct ListNode *root, struct ListNode *node) {
if (node == nullptr || root == nullptr) return EXIT_FAILURE;
if (root == node) {
if (root->next == nullptr) {
delete node;
root = nullptr;
return EXIT_SUCCESS;
}
node = root->next;
root->data = root->next->data;
root->next = root->next->next;
delete node;
return EXIT_SUCCESS;
}
auto prev = root;
while (prev->next != node && prev->next != nullptr) {
prev = prev->next;
}
prev->next = node->next;
delete node;
return EXIT_SUCCESS;
}
void freeNodes(struct ListNode *root) {
struct ListNode *tmp = nullptr;
while (root) {
tmp = root;
root = root->next;
delete tmp;
}
}
void printNodes(struct ListNode *node) {
auto count = 0;
while (node) {
cout << "node " << count << " - data: " << node->data << endl;
node = node->next;
count++;
}
}
int main() {
struct ListNode *head = nullptr;
head = insertNode(head, "Xenial");
insertNode(head, "Artful");
printNodes(head);
cout << " ----------------------------------- " << endl;
deleteNode(head, head);
printNodes(head);
freeNodes(head);
return EXIT_SUCCESS;
}
출력:
node 0 - data: Xenial
node 1 - data: Artful
-----------------------------------
node 0 - data: Artful
나머지 함수 코드는 주어진 노드가 목록 체인에서 분리 된 다음delete연산자를 사용하여 할당 해제되는 일반적인 경우를 구현합니다. 그러나이 작업을 수행하려면 이전 노드를 찾아야합니다. 이는 목록의 헤드를 제외한 모든 노드에 대한 선형 시간 작업입니다. 일반적으로 목록 끝 부분에 대한 지속적인 시간 제거를 보장하기 위해 목록 끝을 연결 목록 구조에 저장해야합니다.
다음 코드 스 니펫은 목록 중간에서 노드가 제거되는 다른main함수 시나리오를 보여줍니다.
#include <iostream>
#include <string>
using std::cin;
using std::cout;
using std::endl;
using std::string;
struct ListNode {
struct ListNode *next{};
string data;
};
struct ListNode *insertNode(struct ListNode *root, string data) {
auto new_node = new ListNode;
if (root) {
while (root->next) root = root->next;
new_node->next = nullptr;
new_node->data = std::move(data);
root->next = new_node;
return root->next;
}
new_node->next = nullptr;
new_node->data = std::move(data);
return new_node;
}
int deleteNode(struct ListNode *root, struct ListNode *node) {
if (node == nullptr || root == nullptr) return EXIT_FAILURE;
if (root == node) {
if (root->next == nullptr) {
delete node;
root = nullptr;
return EXIT_SUCCESS;
}
node = root->next;
root->data = root->next->data;
root->next = root->next->next;
delete node;
return EXIT_SUCCESS;
}
auto prev = root;
while (prev->next != node && prev->next != nullptr) {
prev = prev->next;
}
prev->next = node->next;
delete node;
return EXIT_SUCCESS;
}
void freeNodes(struct ListNode *root) {
struct ListNode *tmp = nullptr;
while (root) {
tmp = root;
root = root->next;
delete tmp;
}
}
void printNodes(struct ListNode *node) {
auto count = 0;
while (node) {
cout << "node " << count << " - data: " << node->data << endl;
node = node->next;
count++;
}
}
int main() {
struct ListNode *head = nullptr;
head = insertNode(head, "Xenial");
auto iter = insertNode(head, "Bionic");
insertNode(head, "Artful");
printNodes(head);
cout << " ----------------------------------- " << endl;
deleteNode(head, iter);
printNodes(head);
freeNodes(head);
return EXIT_SUCCESS;
}
출력:
node 0 - data: Xenial
node 1 - data: Bionic
node 2 - data: Artful
-----------------------------------
node 0 - data: Xenial
node 1 - data: Artful
Founder of DelftStack.com. Jinku has worked in the robotics and automotive industries for over 8 years. He sharpened his coding skills when he needed to do the automatic testing, data collection from remote servers and report creation from the endurance test. He is from an electrical/electronics engineering background but has expanded his interest to embedded electronics, embedded programming and front-/back-end programming.
LinkedIn Facebook