fork download
copy 
  1. #include <iostream>
  2. using namespace std;
  3.  
  4. class Node {
  5. public:
  6.     int data;
  7.     Node* left;
  8.     Node* right;
  9.  
  10.     Node(int val) : data(val), left(nullptr), right(nullptr) {}
  11. };
  12.  
  13. class CircularDoublyLinkedList {
  14. private:
  15.     Node* head;
  16.  
  17. public:
  18.     CircularDoublyLinkedList() : head(nullptr) {}
  19.  
  20.     // Function to insert a node at the end of the list
  21.     void insert(Node* newNode) {
  22.         if (head == nullptr) {
  23.             head = newNode;
  24.             head->left = head;
  25.             head->left = head;
  26.         } else {
  27.             Node* last = head->left;
  28.             last->right = newNode;
  29.             newNode->left = last;
  30.             newNode->right = head;
  31.             head->left = newNode;
  32.         }
  33.     }
  34.  
  35.     // Function to insert a node into a sorted circular doubly linked list
  36.     CircularDoublyLinkedList I(CircularDoublyLinkedList SCDL, Node* x) {
  37.         // If list is empty, x becomes the head
  38.         if (SCDL.head == nullptr) {
  39.             x->left = x;
  40.             x->right = x;
  41.             head = x;
  42.             SCDL.head = head;
  43.             return SCDL;
  44.         }
  45.  
  46.         Node* current = SCDL.head;
  47.  
  48.         // Finding position to insert x
  49.         while (true) {
  50.             if (current->data >= x->data) {
  51.                 break;
  52.             }
  53.             if (current->right == head) {
  54.                 break;
  55.             }
  56.             current = current->right;
  57.         }
  58.  
  59.         // Inserting x before the current node
  60.         if (x->data < current->data) {
  61.             x->left = current->left;
  62.             x->right = current;
  63.             current->left->right = x;
  64.             current->left = x;
  65.             // Updating head if x is smallest
  66.             if (x->data < head->data) {
  67.                 head = x;
  68.                 SCDL.head = head;
  69.             }
  70.         } else { // Inserting after the current node
  71.             x->left = current;
  72.             x->right = current->right;
  73.             current->right->left = x;
  74.             current->right = x;
  75.         }
  76.  
  77.         return SCDL;
  78.     }
  79.  
  80.     // Utility function to print circular doubly linked list
  81.     void printList() {
  82.         if (head == nullptr) {
  83.             std::cout << "List is empty" << std::endl;
  84.             return;
  85.         }
  86.         Node* temp = head;
  87.         do {
  88.             std::cout << temp->data << " ";
  89.             temp = temp->right;
  90.         } while (temp != head);
  91.         std::cout << std::endl;
  92.     }
  93. };
  94.  
  95. int main() {
  96.     CircularDoublyLinkedList SCDL;
  97.  
  98.     Node* node1 = new Node(10);
  99.     Node* node2 = new Node(20);
  100.     Node* node3 = new Node(30);
  101.  
  102.     SCDL.insert(node1);
  103.     SCDL.insert(node2);
  104.     SCDL.insert(node3);
  105.     cout<<"Original SCDL: ";
  106.     SCDL.printList();
  107.  
  108.     Node* node4 = new Node(15);
  109.     Node* node5 = new Node(5);
  110.  
  111.     SCDL.I(SCDL,node4);
  112.     SCDL.I(SCDL,node5);
  113.  
  114.     cout<<"Inserting 15 and 5.."<<endl;
  115.     cout<<"SCDL after insertion: ";
  116.     SCDL.printList();
  117.  
  118.     // Freeing dynamically allocated memory
  119.     delete node1;
  120.     delete node2;
  121.     delete node3;
  122.     delete node4;
  123.     delete node5;
  124.  
  125.     return 0;
  126. }
  127.  
Success #stdin #stdout 0.01s 5276KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Original SCDL: 10 20 30 
Inserting 15 and 5..
SCDL after insertion: 5 10 15 20 30
https://ideone.com/Hk6YRM
language:
C++ 4.3.2 (gcc-4.3.2)
created:
34 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!