C++의 순환 이중 연결 목록
이 기사에서는 C++에서 순환 이중 연결 목록을 구현하는 방법을 보여줍니다.
C++에서 처음부터 순환 이중 연결 목록 데이터 구조
이중 연결 목록은 각 노드가 다음 노드와 이전 노드 모두에 대한 포인터를 저장하는 데이터 구조입니다. 따라서 std::deque와 같은 컨테이너를 구현하는 것이 최적의 선택입니다. 마지막 노드의 next 멤버가 목록의 시작을 가리키고 첫 번째 노드도 이전 노드로 마지막 노드를 가리키도록 이중 연결 목록을 원형으로 만드는 것이 좋습니다.
먼저 목록을 구성하는 데 사용되는 ListNode라는 struct를 선언해야 합니다. 다음으로 ListNode* 유형의 데이터 멤버 2개와 멤버 함수 3개로 구성된 CircularList 클래스를 정의합니다.
string 값을 받아들이고 첫 번째 노드를 초기화하는 생성자를 하나만 포함하기로 결정했지만 이 부분은 프로그래머가 적절하다고 생각하는 대로 수정할 수 있습니다. head와 end의 두 데이터 멤버는 첫 번째 노드와 마지막 노드를 저장합니다. 또한 목록의 각 측면에 요소를 추가하는 별도의 기능이 있습니다.
#include <iostream>
#include <string>
#include <vector>
using std::cin;
using std::cout;
using std::endl;
using std::string;
using std::vector;
struct ListNode {
struct ListNode *next = nullptr;
struct ListNode *prev = nullptr;
string data;
} typedef ListNode;
class CircularList {
public:
explicit CircularList(string data) {
head = new ListNode;
head->next = head;
head->prev = head;
head->data = std::move(data);
end = head;
};
ListNode *insertNodeEnd(string data);
ListNode *insertNodeHead(string data);
void printNodes();
~CircularList();
private:
ListNode *head = nullptr;
ListNode *end = nullptr;
};
ListNode *CircularList::insertNodeEnd(string data) {
auto new_node = new ListNode;
new_node->next = head;
new_node->prev = end;
new_node->data = std::move(data);
head->prev = new_node;
end->next = new_node;
end = end->next;
return end;
}
ListNode *CircularList::insertNodeHead(string data) {
auto new_node = new ListNode;
new_node->next = head;
new_node->prev = end;
new_node->data = std::move(data);
head->prev = new_node;
end->next = new_node;
head = new_node;
return head;
}
CircularList::~CircularList() {
while (head != end) {
auto tmp = head;
head = head->next;
delete tmp;
}
delete head;
}
void CircularList::printNodes() {
auto count = 0;
auto tmp = head;
while (tmp != end) {
cout << "node " << count << " - data: " << tmp->data << endl;
tmp = tmp->next;
count++;
}
cout << "node " << count << " - data: " << tmp->data << endl;
}
int main() {
CircularList clist("Xenial");
clist.insertNodeHead("Saucy");
clist.insertNodeEnd("Quantal");
clist.printNodes();
cout << " ----------------------------------- " << endl;
clist.insertNodeHead("Bionic");
clist.printNodes();
return EXIT_SUCCESS;
}
출력:
node 0 - data: Saucy
node 1 - data: Xenial
node 2 - data: Quantal
-----------------------------------
node 0 - data: Bionic
node 1 - data: Saucy
node 2 - data: Xenial
node 3 - data: Quantal
요소 삽입을 위한 일반적인 알고리즘은 새 ListNode 개체를 할당하고 해당 노드 포인터를 해당 구성원에 할당한 다음 필요에 따라 head/end 구성원을 수정하는 작업을 수반합니다. 코드의 정확성을 검사해야 할 수도 있으므로 목록 내용을 표시하는 printNodes 기능도 포함합니다. 목록 개체가 범위를 벗어난 후에는 모든 메모리를 할당 해제하는 것을 잊지 말아야 합니다. 후자의 함수는 소멸자로 구현됩니다.
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