단일 연결 목록 C++에 노드 삽입
이 기사에서는 C++의 단일 연결 목록에 새 노드를 삽입하는 방법을 설명합니다.
연결된 목록의 끝에 노드를 삽입하는 함수 구현
연결된 목록은 순차적으로 서로를 가리키는 노드로 구성된 선형 데이터 구조입니다. 이 기사에서는 단일 연결 목록 구조에 더 초점을 맞추고 그에 따라 여러 삽입 작업을 구현합니다.
단일 연결 목록에는 데이터 개체와 목록의 다음 노드에 대한 포인터가 있습니다. 목록 삽입 작업을 더 잘 보여주기 위해ListNode라는 노드 구조와 두 개의 도우미 함수 (freeNodes및printNodes)를 정의했습니다. 삽입 작업 시간 복잡도는 노드를 삽입하는 위치에 따라 다릅니다. 예를 들어, 목록의 끝을 알 수없는 경우 목록 끝에 삽입하는 데 선형 시간이 걸립니다.
반면에 처음에 새 노드를 삽입하는 것은 항상 일정한 시간이 걸립니다. 다음 코드는 목록을 구성하는 핵심 함수로 취급 할 수있는insertNodeEnd함수를 보여줍니다. 목록의 헤드를 첫 번째 매개 변수로 사용하고 새 노드에 저장해야하는string데이터를 사용합니다. 이 함수는 목록의 첫 번째 요소를 만들고 그 끝에 새 요소를 추가 할 수 있습니다. 이 함수는 여유 저장 메모리에 새 노드를 할당합니다. 따라서freeNodes기능은 프로그램 종료 전에 모든 메모리를 해제하는 데 필요합니다.
#include <iostream>
#include <string>
#include <utility>
#include <vector>
using std::cin;
using std::cout;
using std::endl;
using std::string;
using std::vector;
struct ListNode {
struct ListNode *next{};
string data;
};
struct ListNode *insertNodeEnd(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;
}
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;
vector<string> data_set = {"Precise", "Quantal", "Saucy", "Raring"};
head = insertNodeEnd(head, data_set.at(0));
for (auto it = data_set.begin() + 1; it != data_set.end(); ++it) {
insertNodeEnd(head, *it);
}
printNodes(head);
cout << " ----------------------------------- " << endl;
insertNodeEnd(head, "Utopic");
printNodes(head);
freeNodes(head);
return EXIT_SUCCESS;
}
출력:
node 0 - data: Precise
node 1 - data: Quantal
node 2 - data: Saucy
node 3 - data: Raring
-----------------------------------
node 0 - data: Precise
node 1 - data: Quantal
node 2 - data: Saucy
node 3 - data: Raring
node 4 - data: Utopic
연결된 목록에서 주어진 노드 뒤에 노드를 삽입하는 함수 구현
목록 중간에 노드를 삽입하려면 일반적으로 일정한 시간과 주어진 위치를 찾는 데 사용되는 검색 알고리즘의 시간 복잡성이 필요합니다. 그러나 검색 기능이 별도로 구현되었다고 가정하고insertNodeAfter함수를 구성하여 대상 노드의 위치를 첫 번째 인수로 제공해야합니다.
insertNodeEnd함수는 새로 추가 된 노드에 대한 포인터를 반환하므로 반환 값을 사용하여insertNodeAfter의 작업을 보여줍니다. 임의의 위치 삽입을 위해 별도의 검색 기능이 필요하며 링크 된 목록에서 더 빠른 검색 작업을 구현하기 위해 외부 데이터 구조가 필요할 수도 있습니다.
#include <iostream>
#include <string>
#include <utility>
#include <vector>
using std::cin;
using std::cout;
using std::endl;
using std::string;
using std::vector;
struct ListNode {
struct ListNode *next{};
string data;
};
struct ListNode *insertNodeEnd(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;
}
struct ListNode *insertNodeAfter(struct ListNode *prev, string data) {
if (!prev) return nullptr;
auto new_node = new ListNode;
new_node->next = nullptr;
new_node->data = std::move(data);
prev->next = new_node;
return new_node;
}
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;
vector<string> data_set = {"Precise", "Quantal", "Saucy", "Raring"};
head = insertNodeEnd(head, data_set.at(0));
for (auto it = data_set.begin() + 1; it != data_set.end(); ++it) {
insertNodeEnd(head, *it);
}
printNodes(head);
cout << " ----------------------------------- " << endl;
auto iter = insertNodeEnd(head, "Utopic");
printNodes(head);
cout << " ----------------------------------- " << endl;
insertNodeAfter(iter, "Xenial");
printNodes(head);
freeNodes(head);
return EXIT_SUCCESS;
}
출력:
node 0 - data: Precise
node 1 - data: Quantal
node 2 - data: Saucy
node 3 - data: Raring
-----------------------------------
node 0 - data: Precise
node 1 - data: Quantal
node 2 - data: Saucy
node 3 - data: Raring
node 4 - data: Utopic
-----------------------------------
node 0 - data: Precise
node 1 - data: Quantal
node 2 - data: Saucy
node 3 - data: Raring
node 4 - data: Utopic
node 5 - data: Xenial
연결된 목록의 시작 부분에 노드를 삽입하는 함수 구현
단일 연결 목록에 대한 또 다른 유용한 삽입 작업은 처음에 새 노드를 추가하는 것입니다. 이 함수는 목록 자체에 액세스하기 위해 항상 목록의 헤드가 저장되므로 가장 좋은 실행 시간O(1)를 갖습니다. insertNodeFront함수는 루트 포인터와 노드에 저장해야하는string객체에 대한 참조를 가져옵니다. 이 프로세스는 새로운 연결 목록과 전면 삽입을 초기화하는 데 사용할 수 있도록 구현됩니다.
또는root인수가nullptr가 아닌 경우 새 노드를 할당하도록 함수를 다시 작성할 수 있습니다. 그렇지 않으면nullptr를 반환하여 함수가 실패했음을 나타냅니다. 이러한 함수의 인터페이스는 프로그래머의 요구와ListNode의 구조에 따라 다릅니다.
#include <iostream>
#include <string>
#include <utility>
#include <vector>
using std::cin;
using std::cout;
using std::endl;
using std::string;
using std::vector;
struct ListNode {
struct ListNode *next{};
string data;
};
struct ListNode *insertNodeEnd(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;
}
struct ListNode *insertNodeFront(struct ListNode *&root, string data) {
auto new_node = new ListNode;
if (root) {
new_node->next = root;
new_node->data = std::move(data);
root = new_node;
return root;
}
new_node->next = nullptr;
new_node->data = std::move(data);
return new_node;
}
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;
vector<string> data_set = {"Precise", "Quantal", "Saucy", "Raring"};
head = insertNodeEnd(head, data_set.at(0));
for (auto it = data_set.begin() + 1; it != data_set.end(); ++it) {
insertNodeEnd(head, *it);
}
printNodes(head);
cout << " ----------------------------------- " << endl;
insertNodeFront(head, "Bionic");
printNodes(head);
freeNodes(head);
return EXIT_SUCCESS;
}
출력:
node 0 - data: Precise
node 1 - data: Quantal
node 2 - data: Saucy
node 3 - data: Raring
-----------------------------------
node 0 - data: Bionic
node 1 - data: Precise
node 2 - data: Quantal
node 3 - data: Saucy
node 4 - data: Raring
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