fork(1) download
copy 
  1. #include <iostream>
  2.  
  3. #include <iostream>
  4. #include <vector>
  5.  
  6. using namespace std;
  7.  
  8. struct Node {
  9.     int data;
  10.     int retrieval_cost;
  11.     Node* next;
  12.     Node* prev;
  13.     Node(int d, int c) : data(d), retrieval_cost(c), next(nullptr), prev(nullptr) {}
  14. };
  15.  
  16. class CircularDoublyLinkedList {
  17. private:
  18.     Node* head;
  19.  
  20. public:
  21.     CircularDoublyLinkedList() : head(nullptr) {}
  22.  
  23.     ~CircularDoublyLinkedList() {
  24.         Node* current = head;
  25.         if (current) {
  26.             do {
  27.                 Node* temp = current;
  28.                 current = current->next;
  29.                 delete temp;
  30.             } while (current != head);
  31.         }
  32.     }
  33.  
  34.     // Function to add a node to the end of the list
  35.     void addNode(int data, int retrieval_cost) {
  36.         Node* newNode = new Node(data, retrieval_cost);
  37.         if (!head) {
  38.             head = newNode;
  39.             head->next = head;
  40.             head->prev = head;
  41.         } else {
  42.             Node* last = head->prev;
  43.             last->next = newNode;
  44.             newNode->prev = last;
  45.             newNode->next = head;
  46.             head->prev = newNode;
  47.         }
  48.     }
  49.  
  50.     // Function to display the CDL
  51.     void display() const {
  52.         if (!head) {
  53.             cout << "Empty list!" << endl;
  54.             return;
  55.         }
  56.  
  57.         Node* current = head;
  58.         do {
  59.             cout << "Data: " << current->data << ", Retrieval Cost: " << current->retrieval_cost << endl;
  60.             current = current->next;
  61.         } while (current != head);
  62.     }
  63.  
  64.     // Retrieval strategy function
  65.     int retrieval_strategy(int target_value) {
  66.         // Starting from the head of the list
  67.         Node* current_node = head; 
  68.         int forward_cost = 0;
  69.         int backward_cost = 0;
  70.         int forward_steps = 1;
  71.         int backward_steps = 1;
  72.  
  73.         // Traversing forward until we find the target value and calculating the total cost from forward direction
  74.         while (current_node->data != target_value && current_node->next != head) {
  75.             forward_cost += current_node->retrieval_cost;
  76.             forward_steps++;
  77.             current_node = current_node->next;
  78.         }
  79.  
  80.         // Reseting current node to the head for backward traversal
  81.         current_node = head;
  82.  
  83.         // Traversing backward until we find the target value and calculating the total cost from backward direction
  84.         while (current_node->data != target_value && current_node->prev != head) {
  85.             backward_cost += current_node->retrieval_cost;
  86.             backward_steps++;
  87.             current_node = current_node->prev;
  88.         }
  89.  
  90.          // Adding retrieval cost to retrieve the target value
  91.         forward_cost+=current_node->retrieval_cost;
  92.         backward_cost+=current_node->retrieval_cost;
  93.  
  94.         // Printing the direction with the minimum cost and number of steps
  95.         if (forward_cost <= backward_cost) {
  96.             cout << "Direction: forward, Move " << forward_steps << " nodes including and starting from head" << endl;
  97.             return forward_cost;
  98.         } else {
  99.             cout << "Direction: backward, Move " << backward_steps << " nodes including and starting from head" << endl;
  100.             return backward_cost;
  101.         }
  102.     }
  103. };
  104.  
  105. int main() {
  106.     CircularDoublyLinkedList CDL;
  107.  
  108.     int n;
  109.     cout << "Enter the number of nodes in the circular doubly linked list: ";
  110.     cin >> n;
  111.  
  112.     cout << "Enter data and retrieval cost for each node:" << endl;
  113.     for (int i = 0; i < n; ++i) {
  114.         int data, cost;
  115.         cout << "Node " << (i + 1) << ": ";
  116.         cin >> data >> cost;
  117.         CDL.addNode(data, cost);
  118.     }
  119.  
  120.     int target_value;
  121.     cout << "Enter the value of the node to retrieve: ";
  122.     cin >> target_value;
  123.  
  124.     int total_cost = CDL.retrieval_strategy(target_value);
  125.     cout << "Total cost to retrieve node with value " << target_value << ": " << total_cost << endl;
  126.  
  127.     cout << "Circular Doubly Linked List:" << endl;
  128.     CDL.display();
  129.  
  130.     return 0;
  131. }
  132.  
Success #stdin #stdout 0.01s 5300KB
comments (?)
stdin
copy 
5
10 5
20 2
30 4
40 8
50 1
30
stdout
copy 
Enter the number of nodes in the circular doubly linked list: Enter data and retrieval cost for each node:
Node 1: Node 2: Node 3: Node 4: Node 5: Enter the value of the node to retrieve: Direction: forward, Move 3 nodes including and starting from head
Total cost to retrieve node with value 30: 11
Circular Doubly Linked List:
Data: 10, Retrieval Cost: 5
Data: 20, Retrieval Cost: 2
Data: 30, Retrieval Cost: 4
Data: 40, Retrieval Cost: 8
Data: 50, Retrieval Cost: 1
https://ideone.com/NSP6D6
language:
C++ 4.3.2 (gcc-4.3.2)
created:
29 days ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!