C++에서 이중 연결 목록 구현
이 기사에서는 C++에서 이중 연결 목록을 구현하는 방법에 대한 여러 방법을 보여줍니다.
struct를 사용하여 C++에서 이중 연결 목록 구현
연결된 목록은 프로그래밍에서 접할 수있는 가장 일반적인 데이터 구조 중 하나로 간주됩니다. 이러한 구조는 각 노드가 다른 노드의 주소를 포함한다는 의미에서 연결됩니다. 연결 목록에는 단일 연결 목록과 이중 연결 목록의 두 가지 유형이 있습니다. 단일 연결 목록에는 목록의 다음 노드 만 가리키는 노드가 포함됩니다. 따라서 구조의 순회를 단방향으로 만듭니다. 반면에 이중 연결 목록은 목록의 각 노드에서 양방향 액세스를 제공합니다.
이 경우struct명령을 사용하여 이중 연결 목록을 구현하여 모든 데이터 멤버를 공개하고 요소 조작 함수를 개별적으로 정의합니다. 요소 조작 루틴과 일부 기록 유지 데이터 멤버를 제공하는 멤버 함수가있는 객체 지향 버전을 선호 할 수 있습니다.
다음 예제 코드에는 기본 사용 시나리오를 테스트하는main함수의 드라이버 코드가 포함되어 있습니다. 여기서string벡터 요소가 목록에 삽입 된 다음 목록이 할당 해제됩니다. new연산자를 사용하여 각 노드를 동적으로 할당하고, 결과적으로freeNodes함수는 목록을 반복하여 각Node에서delete를 호출합니다.
사용자가 상대적으로 고성능의 링크드리스트 구조를 설계하려는 경우 각Node를 개별적으로 할당하는 방법은 비효율적 일 수 있습니다. 새 노드를 빠르게 추가하고 필요하지 않은 경우 동시에 다중 할당을 해제하기 위해 메모리 리소스를 대량 할당하는 것을 고려할 수 있습니다. 이 디자인에서는 구조의 첫 번째 노드를 나타내는 유효한 요소로 목록을 작성하기 시작합니다. 일부 구현에서는 목록의 헤드를 나타내지 만 요소 데이터를 포함하지 않는 더미 요소를 만들 수 있습니다.
#include <iostream>
#include <string>
#include <vector>
using std::cin;
using std::cout;
using std::endl;
using std::string;
using std::vector;
struct Node {
struct Node *next{};
struct Node *prev{};
string data;
};
template <typename T>
struct Node *addNewNode(struct Node *node, T &data) {
auto new_node = new Node;
if (node) node->next = new_node;
new_node->prev = node;
new_node->next = nullptr;
new_node->data = data;
return new_node;
}
void freeNodes(struct Node *node) {
struct Node *tmp = nullptr;
while (node) {
tmp = node;
node = node->next;
delete tmp;
}
}
void printNodeData(struct Node *node) {
cout << "data: " << node->data << endl;
}
int main() {
struct Node *tmp, *root = nullptr;
struct Node *end = nullptr;
vector<string> data_set = {"Rocket Lake", "Alder Lake", "Tiger Lake",
"Meteor Lake"};
root = addNewNode(root, data_set.at(0));
tmp = root;
for (auto it = data_set.begin() + 1; it != data_set.end(); ++it) {
tmp = addNewNode(tmp, *it);
if (it == data_set.end() - 1) end = tmp;
}
printNodeData(root);
printNodeData(end);
freeNodes(root);
return EXIT_SUCCESS;
}
출력:
data: Rocket Lake
data: Meteor Lake
연결 목록을 스택, 데크, 대기열 또는 순환 목록과 같은보다 전문화 된 데이터 구조의 빌딩 블록으로 활용할 수 있습니다. 후자는 본질적으로 마지막 노드가 첫 번째 요소를 다음 노드로 가리키고 그에 따라 첫 번째 요소가 이전 노드로 마지막 요소를 가리키는 이중 연결 목록이기 때문에 흥미 롭습니다. 다음 코드 조각은printNodes함수를 추가하여 구성된 목록에있는 각 노드의 내용을 표시합니다.
#include <iostream>
#include <string>
#include <vector>
using std::cin;
using std::cout;
using std::endl;
using std::string;
using std::vector;
struct Node {
struct Node *next{};
struct Node *prev{};
string data;
};
struct Node *addNewNode(struct Node *node, string &data) {
auto new_node = new Node;
if (node) node->next = new_node;
new_node->prev = node;
new_node->next = nullptr;
new_node->data = data;
return new_node;
}
void freeNodes(struct Node *node) {
struct Node *tmp = nullptr;
while (node) {
tmp = node;
node = node->next;
delete tmp;
}
}
void printNodes(struct Node *node) {
auto count = 0;
while (node) {
cout << "node " << count << " - data: " << node->data << endl;
node = node->next;
count++;
}
}
int main() {
struct Node *tmp, *root = nullptr;
struct Node *end = nullptr;
vector<string> data_set = {"Rocket Lake", "Alder Lake", "Tiger Lake",
"Meteor Lake"};
root = addNewNode(root, data_set.at(0));
tmp = root;
for (auto it = data_set.begin() + 1; it != data_set.end(); ++it) {
tmp = addNewNode(tmp, *it);
if (it == data_set.end() - 1) end = tmp;
}
printNodes(root);
freeNodes(root);
return EXIT_SUCCESS;
}
출력:
node 0 - data: Rocket Lake
node 1 - data: Alder Lake
node 2 - data: Tiger Lake
node 3 - data: Meteor Lake
std::list컨테이너를 C++에서 이중 연결 목록으로 사용
또는 일반적으로 이중 연결 목록으로 구현되고 다양한 요소 조작 기능을 제공하는 C++ STL의std::list컨테이너를 사용할 수 있습니다. 또한std::list컨테이너는 표준 라이브러리에 포함 된 매우 강력한 알고리즘을 지원하도록 구현되어있어 매우 특별한 성능 특성이 필요하지 않은 경우 사용자가 개발 시간을 절약 할 수 있습니다.
#include <iostream>
#include <list>
#include <string>
using std::cin;
using std::cout;
using std::endl;
using std::list;
using std::string;
template <typename T>
void printList(std::list<T> l) {
for (const auto &item : l) {
cout << item << "; ";
}
cout << endl;
}
int main() {
std::list<int> l = {1, 2, 3, 4};
l.push_back(5);
l.push_front(0);
printList(l);
auto it = std::find(l.begin(), l.end(), 3);
if (it != l.end()) {
l.insert(it, 99);
}
printList(l);
return EXIT_SUCCESS;
}
출력:
0; 1; 2; 3; 4; 5;
0; 1; 2; 99; 3; 4; 5;
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