#include <iostream>
#include <iostream>
#include <vector>
using namespace std;
struct Node {
int data;
int retrieval_cost;
Node* next;
Node* prev;
Node(int d, int c) : data(d), retrieval_cost(c), next(nullptr), prev(nullptr) {}
};
class CircularDoublyLinkedList {
private:
Node* head;
public:
CircularDoublyLinkedList() : head(nullptr) {}
~CircularDoublyLinkedList() {
Node* current = head;
if (current) {
do {
Node* temp = current;
current = current->next;
delete temp;
} while (current != head);
}
}
// Function to add a node to the end of the list
void addNode(int data, int retrieval_cost) {
Node* newNode = new Node(data, retrieval_cost);
if (!head) {
head = newNode;
head->next = head;
head->prev = head;
} else {
Node* last = head->prev;
last->next = newNode;
newNode->prev = last;
newNode->next = head;
head->prev = newNode;
}
}
// Function to display the CDL
void display() const {
if (!head) {
cout << "Empty list!" << endl;
return;
}
Node* current = head;
do {
cout << "Data: " << current->data << ", Retrieval Cost: " << current->retrieval_cost << endl;
current = current->next;
} while (current != head);
}
// Retrieval strategy function
int retrieval_strategy(int target_value) {
// Starting from the head of the list
Node* current_node = head;
int forward_cost = 0;
int backward_cost = 0;
int forward_steps = 1;
int backward_steps = 1;
// Traversing forward until we find the target value and calculating the total cost from forward direction
while (current_node->data != target_value && current_node->next != head) {
forward_cost += current_node->retrieval_cost;
forward_steps++;
current_node = current_node->next;
}
// Reseting current node to the head for backward traversal
current_node = head;
// Traversing backward until we find the target value and calculating the total cost from backward direction
while (current_node->data != target_value && current_node->prev != head) {
backward_cost += current_node->retrieval_cost;
backward_steps++;
current_node = current_node->prev;
}
// Adding retrieval cost to retrieve the target value
forward_cost+=current_node->retrieval_cost;
backward_cost+=current_node->retrieval_cost;
// Printing the direction with the minimum cost and number of steps
if (forward_cost <= backward_cost) {
cout << "Direction: forward, Move " << forward_steps << " nodes including and starting from head" << endl;
return forward_cost;
} else {
cout << "Direction: backward, Move " << backward_steps << " nodes including and starting from head" << endl;
return backward_cost;
}
}
};
int main() {
CircularDoublyLinkedList CDL;
int n;
cout << "Enter the number of nodes in the circular doubly linked list: ";
cin >> n;
cout<<endl;
cout << "Enter data and retrieval cost for each node:" << endl;
for (int i = 0; i < n; ++i) {
int data, cost;
cout << "Node " << (i + 1) << ": ";
cin >> data >> cost;
CDL.addNode(data, cost);
cout<<endl;
}
int target_value;
cout << "Enter the value of the node to retrieve: ";
cin >> target_value;
cout<<endl;
int total_cost = CDL.retrieval_strategy(target_value);
cout << "Total cost to retrieve node with value " << target_value << ": " << total_cost << endl;
cout << "Circular Doubly Linked List:" << endl;
CDL.display();
return 0;
}