fork download
copy 
  1. #include <bits/stdc++.h>
  2. using  namespace std;
  3.  
  4. template <typename T>
  5. struct Node{
  6.     T info;
  7.     Node *link;
  8. };
  9.  
  10. template<typename T>
  11. class single_LinkedList{
  12. private:
  13.     Node<T>* head;
  14.     int list_size ;
  15. public:
  16.     single_LinkedList(){
  17.         assert(head);
  18.         head = nullptr;
  19.         list_size = 0;
  20.     }
  21.     void insertAtHead(int value){
  22.         Node<T>* newNode;
  23.         assert(newNode);
  24.         newNode = new Node<T>;
  25.         newNode->info = value;
  26.         ///
  27.         newNode->link = head;
  28.         head = newNode;
  29.         list_size++;
  30.     }
  31.     void insertAtTail(int value){
  32.         Node<T>* newNode = new Node<T>;
  33.         assert(newNode);
  34.         newNode = new Node<T>;
  35.         newNode->info = value;
  36.         newNode->link = nullptr;
  37.         /// Make head point to the newNode element
  38.         if(head == nullptr){
  39.             head= newNode;
  40.         } else{
  41.             Node<T> *current ;
  42.             current = new Node<T>;
  43.             assert(current);
  44.             current = head;
  45.             while (current->link != nullptr){
  46.                 current = current->link;
  47.             }
  48.             current->link = newNode;
  49.         }
  50.         list_size++;
  51.     }
  52.     void insertAt(T value , int index){
  53.         try {
  54.             if (index >= list_size || index < 0) {
  55.                 throw std::runtime_error("Index out of bounds\n");
  56.             }
  57.         } catch (const std::runtime_error& e) {
  58.             std::cerr << "Exception caught: " << e.what() << std::endl;
  59.         }
  60.         if(index==0){
  61.             insertAtHead(value);
  62.         } else if(index == list_size - 1){
  63.             insertAtTail(value);
  64.         } else {
  65.             Node<T> *CurrentNode = new Node<T>;
  66.             assert(CurrentNode);
  67.             Node<T>*NewNode = new Node<T>;
  68.             assert(NewNode);
  69.             Node<T> *PrevNode = new Node<T>;
  70.             assert(PrevNode);
  71.             PrevNode->link = nullptr;
  72.             NewNode->info = value;
  73.             int current_index = 0;
  74.             CurrentNode = head;
  75.             while (current_index != index){
  76.                 PrevNode = CurrentNode;
  77.                 CurrentNode = CurrentNode->link;
  78.                 current_index++;
  79.             }
  80.             PrevNode->link = NewNode;
  81.             NewNode->link = CurrentNode;
  82.         }
  83.         list_size++;
  84.     }
  85.     void removeAtTail(){
  86.         try {
  87.             if (isEmpty()) {
  88.                 throw std::runtime_error("Empty list: Can't delete an element.\n");
  89.             }
  90.         } catch (const std::runtime_error& e) {
  91.             std::cerr << "Exception caught: " << e.what() << std::endl;
  92.         }
  93.         Node<T> *to_delete ;
  94.         to_delete = new Node<T>;
  95.         assert(to_delete);
  96.         to_delete = head;
  97.         while (to_delete->link != nullptr){
  98.             to_delete = to_delete->link;
  99.         }
  100.         Node<T>* before_delete;
  101.         before_delete = new Node<T>;
  102.         assert(before_delete);
  103.         before_delete = head;
  104.         while (before_delete->link != to_delete){
  105.             before_delete = before_delete->link;
  106.         }
  107.         delete to_delete;
  108.         before_delete->link = nullptr;
  109.         list_size--;
  110.     }
  111.     void removeAtHead(){
  112.         try {
  113.             if (isEmpty()) {
  114.                 throw std::runtime_error("Empty list: Can't delete an element.\n");
  115.             }
  116.         } catch (const std::runtime_error& e) {
  117.             std::cerr << "Exception caught: " << e.what() << std::endl;
  118.         }
  119.         Node<T>*PointToHeadLink = new Node<T>;
  120.         assert(PointToHeadLink);
  121.         PointToHeadLink = head;
  122.         head = head->link;
  123.         delete PointToHeadLink;
  124.         list_size--;
  125.     }
  126.     void removeAt(int index){
  127.         try {
  128.             if (isEmpty()) {
  129.                 throw std::runtime_error("Empty list: Can't delete an element.\n");
  130.             }
  131.         } catch (const std::runtime_error& e) {
  132.             std::cerr << "Exception caught: " << e.what() << std::endl;
  133.         }
  134.         try{
  135.             if(index < 0 || index >= list_size ){
  136.                 throw std::runtime_error("Index out of bound :(.");
  137.             }
  138.         }catch (const std::runtime_error &e) {
  139.             cerr << "Exception caught " << e.what() << '\n';
  140.         }
  141.         Node<int>* current_node = head;
  142.         assert(current_node);
  143.         Node<int>* previous_current = new Node<int>;
  144.         assert(current_node);
  145.         previous_current->link = nullptr;
  146.         int current_index = -1;
  147.         while (current_index < index-1){
  148.             previous_current = current_node;
  149.             current_node = current_node->link;
  150.             current_index++;
  151.         }
  152.         if(previous_current->link == nullptr){
  153.             head = head->link;
  154.             delete current_node;
  155.         } else if(current_node->link == nullptr){
  156.             previous_current->link = nullptr;
  157.             delete current_node;
  158.  
  159.         }
  160.         else {
  161.             previous_current->link = current_node->link;
  162.             delete current_node ;
  163.         }
  164.         list_size--;
  165.     }
  166.     T retrieveAt(int index)const{
  167.         try{
  168.             if(index < 0 || index >= list_size){
  169.                 throw std::runtime_error("Index out of bound :(.");
  170.             }
  171.         }catch (const std::runtime_error &e) {
  172.             cerr << "Exception caught " << e.what() << '\n';
  173.         }
  174.         Node<int>* current_node = head;
  175.         assert(current_node);
  176.         Node<int>* previous_current = new Node<int>;
  177.         assert(previous_current);
  178.         previous_current->link = nullptr;
  179.         int current_index = -1;
  180.         while (current_index < index-1){
  181.             previous_current = current_node;
  182.             current_node = current_node->link;
  183.             current_index++;
  184.         }
  185.         if(previous_current->link == nullptr){
  186.             return head->info;
  187.         } else {
  188.             return current_node->info;
  189.         }
  190.     }
  191.     void replaceAt( T value ,  int index ){
  192.         try{
  193.             if(index < 0 || index >= list_size){
  194.                 throw std::runtime_error("Index out of bound :(.");
  195.             }
  196.         }catch (const std::runtime_error &e) {
  197.             cerr << "Exception caught " << e.what() << '\n';
  198.         }
  199.         Node<int>* current_node = head;
  200.         assert(current_node);
  201.         Node<int>* previous_current = new Node<int>;
  202.         assert(previous_current);
  203.         previous_current->link = nullptr;
  204.         int current_index = -1;
  205.         while (current_index < index-1){
  206.             previous_current = current_node;
  207.             current_node = current_node->link;
  208.             current_index++;
  209.         }
  210.         if(previous_current->link == nullptr){
  211.             head->info = value;
  212.         } else {
  213.             current_node->info = value;
  214.         }
  215.     }
  216.     bool is_itemAt_equal( T value ,  int index )const{
  217.         try{
  218.             if(index < 0 || index >= list_size){
  219.                 throw std::runtime_error("Index out of bound :(.");
  220.             }
  221.         }catch (const std::runtime_error &e) {
  222.             cerr << "Exception caught " << e.what() << '\n';
  223.         }
  224.         Node<int>* current_node = head;
  225.         assert(current_node);
  226.         Node<int>* previous_current = new Node<int>;
  227.         assert(previous_current);
  228.         previous_current->link = nullptr;
  229.         int current_index = -1;
  230.         while (current_index < index-1){
  231.             previous_current = current_node;
  232.             current_node = current_node->link;
  233.             current_index++;
  234.         }
  235.         if(previous_current->link == nullptr){
  236.             return head->info == value;
  237.         } else {
  238.             return current_node->info == value;
  239.         }
  240.     }
  241.     void swap(int first_index , int second_index){
  242.         try{
  243.             if(first_index < 0 || first_index >= list_size || second_index < 0 || second_index >= list_size){
  244.                 throw std::runtime_error("Index out of bound :(.");
  245.             }
  246.         }catch (const std::runtime_error &e) {
  247.             cerr << "Exception caught " << e.what() << '\n';
  248.         }
  249.         Node<T>*current_node = head;
  250.         assert(current_node);
  251.         int current_index = 0;
  252.         while (current_index != first_index){
  253.             current_node = current_node->link;
  254.             current_index++;
  255.         }
  256.         Node<T>*first_node = current_node;
  257.         assert(first_node);
  258.         current_node = head;
  259.  
  260.         current_index = 0;
  261.         while (current_index != second_index){
  262.             current_node = current_node->link;
  263.             current_index++;
  264.         }
  265.         Node<T>*second_node = current_node;
  266.         assert(second_node);
  267.         int temp = first_node->info;
  268.         first_node->info = second_node->info;
  269.         second_node->info = temp;
  270.     }
  271.     T size()const{
  272.         return list_size;
  273.     }
  274.     void print()const{
  275.         try {
  276.             if (isEmpty()) {
  277.                 throw std::runtime_error("Empty list: Can't delete an element.\n");
  278.             }
  279.         } catch (const std::runtime_error& e) {
  280.             std::cerr << "Exception caught: " << e.what() << std::endl;
  281.         }
  282.         Node<T>* current = head;
  283.         assert(current);
  284.         while (current->link != nullptr){
  285.             cout << current->info << ' ';
  286.             current = current->link;
  287.         }
  288.         cout << current->info  << '\n';
  289.     }
  290.     bool isEmpty()const{
  291.         return (head == nullptr);
  292.     }
  293.     void clear(){
  294.         if(head != nullptr){
  295.             Node<T> *current = new Node<T>;
  296.             assert(current);
  297.             current = head;
  298.  
  299.             while (current != nullptr) {
  300.                 Node<T> *temp = new Node<T>;
  301.                 temp = current;
  302.                 current = current->link;
  303.                 delete temp;
  304.             }
  305.         }
  306.         head = nullptr;
  307.         list_size = 0;
  308.     }
  309.     ~single_LinkedList(){
  310.         if(head != nullptr) {
  311.             Node<T> *current = new Node<T>;
  312.             assert(current);
  313.             current = head;
  314.             while (current->link != nullptr) {
  315.                 Node<T> *temp = new Node<T>;
  316.                 assert(temp);
  317.                 temp = current;
  318.                 current = current->link;
  319.                 delete temp;
  320.             }
  321.             head = nullptr;
  322.         }
  323.     }
  324. };
  325.  
  326. template<typename T>
  327. class  circular_LinkedList{
  328. private:
  329.     Node<T>*head;
  330.     int list_size = 0;
  331. public:
  332.     circular_LinkedList(){
  333.         head = new Node<T>;
  334.         assert(head);
  335.         head = nullptr;
  336.         list_size = 0;
  337.     }
  338.     void insertAtHead(int value){
  339.         Node<T>* newNode = new Node<T>;
  340.         assert(newNode);
  341.         newNode->info = value;
  342.         newNode->link = nullptr;
  343.         if(head == nullptr){
  344.             head = newNode;
  345.             head->link = head;
  346.         } else{
  347.             Node<T>*temp = new Node<T>;
  348.             temp = head;
  349.             newNode->link = head;
  350.             head = newNode;
  351.             Node<T>*current = head;
  352.             do{
  353.                 current = current->link;
  354.             } while (temp != current->link);
  355.             current->link = head;
  356.         }
  357.         list_size++;
  358.     }
  359.     void insertAtTail(int value){
  360.         Node<T>* newNode = new Node<T>;
  361.         assert(newNode);
  362.         newNode = new Node<T>;
  363.         newNode->info = value;
  364.         newNode->link = nullptr;
  365.         /// Make head point to the newNode element
  366.         if(head == nullptr){
  367.             head = newNode;
  368.         } else{
  369.             Node<T> *current ;
  370.             current = new Node<T>;
  371.             assert(current);
  372.             current = head;
  373.             while (current->link != head){
  374.                 current = current->link;
  375.             }
  376.             current->link = newNode;
  377.             newNode->link = head;
  378.         }
  379.         list_size++;
  380.     }
  381.     void insertAt(T value , int index){
  382.         try {
  383.             if (index >= list_size || index < 0) {
  384.                 throw std::runtime_error("Index out of bounds\n");
  385.             }
  386.         } catch (const std::runtime_error& e) {
  387.             std::cerr << "Exception caught: " << e.what() << std::endl;
  388.         }
  389.         if(index==0){
  390.             insertAtHead(value);
  391.         } else if(index == list_size - 1){
  392.             insertAtTail(value);
  393.         } else {
  394.             Node<T> *CurrentNode = new Node<T>;
  395.             assert(CurrentNode);
  396.             Node<T>*NewNode = new Node<T>;
  397.             assert(NewNode);
  398.             Node<T> *PrevNode = new Node<T>;
  399.             assert(PrevNode);
  400.             PrevNode->link = head;
  401.             NewNode->info = value;
  402.             int current_index = 0;
  403.             CurrentNode = head;
  404.             while (current_index != index){
  405.                 PrevNode = CurrentNode;
  406.                 CurrentNode = CurrentNode->link;
  407.                 current_index++;
  408.             }
  409.             NewNode->link = CurrentNode;
  410.             PrevNode->link = NewNode;
  411.             list_size++;
  412.         }
  413.     }
  414.     void removeAtTail(){
  415.         try {
  416.             if (isEmpty()) {
  417.                 throw std::runtime_error("Empty list: Can't delete an element.\n");
  418.             }
  419.         } catch (const std::runtime_error& e) {
  420.             std::cerr << "Exception caught: " << e.what() << std::endl;
  421.         }
  422.         Node<T> *to_delete , *previous_delete = new Node<T>;
  423.         to_delete = new Node<T>;
  424.         assert(to_delete);
  425.         previous_delete->link = head;
  426.         to_delete = head;
  427.         while (to_delete->link != head){
  428.             previous_delete = to_delete;
  429.             to_delete = to_delete->link;
  430.         }
  431.         if(to_delete == head){
  432.             head = nullptr;
  433.             delete to_delete;
  434.         } else{
  435.             previous_delete->link = head;
  436.             delete to_delete;
  437.         }
  438.         list_size--;
  439.     }
  440.     void removeAtHead(){
  441.         try {
  442.             if (isEmpty()) {
  443.                 throw std::runtime_error("Empty list: Can't delete an element.\n");
  444.             }
  445.         } catch (const std::runtime_error& e) {
  446.             std::cerr << "Exception caught: " << e.what() << std::endl;
  447.         }
  448.         Node<T>*temp = head;
  449.         if(temp->link == nullptr){
  450.             delete temp;
  451.             head = nullptr;
  452.         } else{
  453.             head = head->link;
  454.             Node<T>*current = head;
  455.             while (current->link != temp){
  456.                 current = current->link;
  457.             }
  458.             current->link = head;
  459.             delete temp;
  460.         }
  461.         list_size--;
  462.     }
  463.     void removeAt(int index){
  464.         try {
  465.             if (isEmpty()) {
  466.                 throw std::runtime_error("Empty list: Can't delete an element.\n");
  467.             }
  468.         } catch (const std::runtime_error& e) {
  469.             std::cerr << "Exception caught: " << e.what() << std::endl;
  470.         }
  471.         try{
  472.             if(index < 0 || index >= list_size ){
  473.                 throw std::runtime_error("Index out of bound :(.");
  474.             }
  475.         }catch (const std::runtime_error &e) {
  476.             cerr << "Exception caught " << e.what() << '\n';
  477.         }
  478.         Node<int>* current_node = head;
  479.         assert(current_node);
  480.         Node<int>* previous_current = new Node<int>;
  481.         assert(current_node);
  482.         previous_current->link = nullptr;
  483.         int current_index = -1;
  484.         while (current_index < index-1){
  485.             previous_current = current_node;
  486.             current_node = current_node->link;
  487.             current_index++;
  488.         }
  489.         if(previous_current->link == nullptr){
  490.             head = head->link;
  491.             delete current_node;
  492.         } else if(current_node->link == head){
  493.             previous_current->link = nullptr;
  494.             delete current_node;
  495.         }
  496.         else {
  497.             previous_current->link = current_node->link;
  498.             delete current_node ;
  499.         }
  500.         list_size--;
  501.     }
  502.     T retrieveAt(int index)const{
  503.         try{
  504.             if(index < 0 || index >= list_size){
  505.                 throw std::runtime_error("Index out of bound :(.");
  506.             }
  507.         }catch (const std::runtime_error &e) {
  508.             cerr << "Exception caught " << e.what() << '\n';
  509.         }
  510.         Node<int>* current_node = head;
  511.         assert(current_node);
  512.         Node<int>* previous_current = new Node<int>;
  513.         assert(previous_current);
  514.         previous_current->link = nullptr;
  515.         int current_index = 0;
  516.         while (current_index != index){
  517.             previous_current = current_node;
  518.             current_node = current_node->link;
  519.             current_index++;
  520.         }
  521.         if(previous_current->link == nullptr){
  522.             return head->info;
  523.         } else {
  524.             return current_node->info;
  525.         }
  526.     }
  527.     void replaceAt( T value ,  int index ){
  528.         try{
  529.             if(index < 0 || index >= list_size){
  530.                 throw std::runtime_error("Index out of bound :(.");
  531.             }
  532.         }catch (const std::runtime_error &e) {
  533.             cerr << "Exception caught " << e.what() << '\n';
  534.         }
  535.         Node<int>* current_node = head;
  536.         assert(current_node);
  537.         Node<int>* previous_current = new Node<int>;
  538.         assert(previous_current);
  539.         previous_current->link = nullptr;
  540.         int current_index = -1;
  541.         while (current_index < index-1){
  542.             previous_current = current_node;
  543.             current_node = current_node->link;
  544.             current_index++;
  545.         }
  546.         if(previous_current->link == nullptr){
  547.             head->info = value;
  548.         } else {
  549.             current_node->info = value;
  550.         }
  551.     }
  552.     bool is_itemAt_equal( T value ,  int index )const{
  553.         try{
  554.             if(index < 0 || index >= list_size){
  555.                 throw std::runtime_error("Index out of bound :(.");
  556.             }
  557.         }catch (const std::runtime_error &e) {
  558.             cerr << "Exception caught " << e.what() << '\n';
  559.         }
  560.         Node<int>* current_node = head;
  561.         assert(current_node);
  562.         Node<int>* previous_current = new Node<int>;
  563.         assert(previous_current);
  564.         previous_current->link = nullptr;
  565.         int current_index = -1;
  566.         while (current_index < index-1){
  567.             previous_current = current_node;
  568.             current_node = current_node->link;
  569.             current_index++;
  570.         }
  571.         if(previous_current->link == nullptr){
  572.             return head->info == value;
  573.         } else {
  574.             return current_node->info == value;
  575.         }
  576.     }
  577.     void swap(int first_index , int second_index){
  578.         try{
  579.             if(first_index < 0 || first_index >= list_size || second_index < 0 || second_index >= list_size){
  580.                 throw std::runtime_error("Index out of bound :(.");
  581.             }
  582.         }catch (const std::runtime_error &e) {
  583.             cerr << "Exception caught " << e.what() << '\n';
  584.         }
  585.         if(first_index == second_index)
  586.             return;
  587.         int mx = max(first_index , second_index);
  588.         int mn = min(first_index , second_index);
  589.         first_index = mn;
  590.         second_index = mx;
  591.         Node<T>*first_node = new Node<T>;
  592.         Node<T>*before_first_node = new Node<T>;
  593.         before_first_node->link = nullptr;
  594.  
  595.         Node<T>*second_node = new Node<T>;
  596.         Node<T>*before_second_node = new Node<T>;
  597.         before_second_node->link = nullptr;
  598.  
  599.         first_node = head;
  600.         int cnt = 0;
  601.         while (cnt < first_index){
  602.             before_first_node = first_node;
  603.             first_node = first_node->link;
  604.             cnt++;
  605.         }
  606.  
  607.         second_node = head;
  608.         cnt = 0;
  609.         while (cnt < second_index){
  610.             before_second_node = second_node;
  611.             second_node = second_node->link;
  612.             cnt++;
  613.         }
  614.         Node<T>*temp2 = new Node<T>;
  615.         Node<T>*temp1 = new Node<T>;
  616.  
  617.         if (first_node == head) {
  618.             temp2 = second_node->link;
  619.             temp1 = second_node;
  620.             temp1->link = first_node;
  621.             first_node->link = temp2;
  622.         } else if (second_node == head) {
  623.             // If second_node is the head of the list
  624.             temp1->link = second_node->link; // Save the link of second_node
  625.             temp1 = first_node;
  626.  
  627.             before_first_node->link = temp2;
  628.             temp2->link = first_node->link;
  629.             temp2 = first_node;
  630.  
  631.             head = temp2; // Update the head if necessary
  632.         } else {
  633.             temp2 = second_node->link;
  634.             first_node->link = temp2;
  635.             before_first_node->link = second_node;
  636.             second_node->link = first_node;
  637.         }
  638.  
  639.     }
  640.     T size()const{
  641.         return list_size;
  642.     }
  643.     void print()const{
  644.         try {
  645.             if (isEmpty()) {
  646.                 throw std::runtime_error("Empty list: Can't delete an element.\n");
  647.             }
  648.         } catch (const std::runtime_error& e) {
  649.             std::cerr << "Exception caught: " << e.what() << std::endl;
  650.         }
  651.         Node<T>*current = head;
  652.         do{
  653.             cout << current->info << ' ';
  654.             current = current->link;
  655.         } while (current != head);
  656.         cout << '\n';
  657.     }
  658.     bool isEmpty()const{
  659.         return (head == nullptr);
  660.     }
  661.     void clear(){
  662.         if(head != nullptr){
  663.             Node<T> *current = new Node<T>;
  664.             assert(current);
  665.             current = head;
  666.  
  667.             while (current != head) {
  668.                 Node<T> *temp = new Node<T>;
  669.                 temp = current;
  670.                 current = current->link;
  671.                 delete temp;
  672.             }
  673.         }
  674.         head = nullptr;
  675.         list_size = 0;
  676.     }
  677.     ~circular_LinkedList() {
  678.         if (head != nullptr) {
  679.             Node<T>* current = head;
  680.             Node<T>* next;
  681.  
  682.             do {
  683.                 next = current->link;
  684.                 delete current;
  685.                 current = next;
  686.             } while (current != head);
  687.  
  688.             head = nullptr;
  689.             list_size = 0;
  690.         }
  691.     }
  692. };
  693.  
  694. int main(){
  695.     circular_LinkedList<int>list1;
  696.     list1.insertAtHead(5);
  697.     list1.insertAtHead(6);
  698.     list1.insertAtHead(7);
  699.     list1.insertAtTail(1);
  700.     list1.insertAtTail(2);
  701.     list1.insertAtTail(3);
  702.  
  703.     list1.swap(0 , 1);
  704.     // 7 6 5 1 2 3
  705.     // 6 7 5 1 2 3
  706.  
  707.     list1.print();
  708. }
Success #stdin #stdout 0.01s 5308KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
7 5 1 2 3
https://ideone.com/COS20O
language:
C++ (gcc 8.3)
created:
9 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!