HOWTO · C++
C++의 순환 이중 연결 목록
이 문서에서는 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 기능도 포함합니다. 목록 개체가 범위를 벗어난 후에는 모든 메모리를 할당 해제하는 것을 잊지 말아야 합니다. 후자의 함수는 소멸자로 구현됩니다.
