avr39ripe

cppListFwInsertAtDeleteAt

Aug 11th, 2021 (edited)
675
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. #include <iostream>
  2.  
  3. template <typename ElemT>
  4. class ListFw
  5. {
  6.     class Node
  7.     {
  8.         ElemT data;
  9.         Node* next;
  10.     public:
  11.         Node(const ElemT& dataP, Node* nextP = nullptr) : data{ dataP }, next{ nextP }{}
  12.         friend ListFw;
  13.     };
  14.  
  15.     Node* head;
  16.     Node* tail;
  17.     size_t size;
  18.     Node* getNode(size_t idx);
  19. public:
  20.     ListFw() : head{ nullptr }, tail{ nullptr }, size{ 0 } {}
  21.     bool empty()const { return size == 0; }
  22.     size_t get_size()const { return size; }
  23.     ElemT& front() { return head->data; }
  24.     const ElemT& front()const { return head->data; }
  25.     ElemT& back() { return tail->data; }
  26.     const ElemT& back()const { return tail->data; }
  27.     void push_front(const ElemT& data);
  28.     void push_back(const ElemT& data);
  29.     bool pop_front();
  30.     bool pop_back();
  31.  
  32.     void insert_at(size_t idx, const ElemT& data);
  33.     bool delete_at(size_t idx);
  34.  
  35.     void print()
  36.     {
  37.         if (!head) { std::cout << "[empty]"; }
  38.         else
  39.         {
  40.             for (auto curr{ head }; curr; curr = curr->next)
  41.             {
  42.                 std::cout << curr->data << ' ';
  43.             }
  44.         }
  45.         std::cout << '\n';
  46.     }
  47.  
  48.     void clear();
  49.     ~ListFw();
  50. };
  51.  
  52. template <typename ElemT>
  53. void ListFw<ElemT>::push_front(const ElemT& data)
  54. {
  55.     head = new Node{ data, head };
  56.  
  57.     if (!tail) { tail = head; }
  58.     ++size;
  59. }
  60.  
  61. template <typename ElemT>
  62. void ListFw<ElemT>::push_back(const ElemT& data)
  63. {
  64.     if (!head)
  65.     {
  66.         head = new Node{ data, head };
  67.         tail = head;
  68.     }
  69.     else
  70.     {
  71.         tail->next = new Node{ data, nullptr };
  72.         tail = tail->next;
  73.     }
  74.     ++size;
  75. }
  76.  
  77. template <typename ElemT>
  78. bool ListFw<ElemT>::pop_front()
  79. {
  80.     if (head)
  81.     {
  82.         Node* oldHead{ head };
  83.         head = head->next;
  84.         delete oldHead;
  85.         --size;
  86.         if (!size) { tail = nullptr; }
  87.         return true;
  88.     }
  89.     return false;
  90. }
  91.  
  92. template <typename ElemT>
  93. bool ListFw<ElemT>::pop_back()
  94. {
  95.     if (tail)
  96.     {
  97.         if (tail == head)
  98.         {
  99.             delete tail;
  100.             head = nullptr;
  101.             tail = nullptr;
  102.             size = 0;
  103.             return true;
  104.         }
  105.  
  106.         Node* curr{ head };
  107.         for (; !(curr->next == tail); curr = curr->next);
  108.  
  109.         delete tail;
  110.         curr->next = nullptr;
  111.         tail = curr;
  112.         --size;
  113.         return true;
  114.     }
  115.     return false;
  116. }
  117.  
  118. template <typename ElemT>
  119. void ListFw<ElemT>::clear()
  120. {
  121.     while (head)
  122.     {
  123.         std::cout << "Clear for: " << front() << '\n';
  124.         pop_front();
  125.     }
  126. }
  127.  
  128. template <typename ElemT>
  129. ListFw<ElemT>::~ListFw()
  130. {
  131.     while (tail)
  132.     {
  133.         std::cout << "Destruct for: " << back() << '\n';
  134.         pop_back();
  135.     }
  136. }
  137.  
  138. template <typename ElemT>
  139. void printListState(const ListFw<ElemT>& l)
  140. {
  141.     std::cout << "Size: " << l.get_size() << '\n';
  142.     std::cout << "Front: " << l.front() << '\n';
  143.     std::cout << "Back: " << l.back() << '\n';
  144. }
  145.  
  146. template <typename ElemT>
  147. typename ListFw<ElemT>::Node* ListFw<ElemT>::getNode(size_t idx)
  148. {
  149.     Node* curr{ nullptr };
  150.     size_t currIdx;
  151.  
  152.     if (idx >= 0 and idx < size)
  153.     {
  154.         for (curr = head, currIdx = 0; currIdx < idx; curr = curr->next, ++currIdx);
  155.     }
  156.     return curr;
  157. }
  158.  
  159. template <typename ElemT>
  160. void ListFw<ElemT>::insert_at(size_t idx, const ElemT& data)
  161. {
  162.     Node* prev{ getNode(idx - 1) };
  163.     Node* curr{ prev ? prev->next : nullptr};
  164.  
  165.     if (!curr or curr == head) { push_front(data); return; }
  166.     else
  167.     {
  168.         prev->next = new Node{ data, curr };
  169.     }
  170.     ++size;
  171. }
  172.  
  173. template <typename ElemT>
  174. bool ListFw<ElemT>::delete_at(size_t idx)
  175. {
  176.     if (idx == 0) { pop_front(); return true; }
  177.     Node* prev{ getNode(idx - 1) };
  178.     Node* curr{ prev ? prev->next : nullptr };
  179.  
  180.     if (curr)
  181.     {
  182.         if (curr == head) { head = curr->next; }
  183.         else
  184.         {
  185.             if (curr->next) { prev->next = curr->next; }
  186.             else { tail = prev; prev->next = nullptr; }
  187.         }
  188.         --size;
  189.         delete curr;
  190.         return true;
  191.     }
  192.     return false;
  193. }
  194.  
  195. int main()
  196. {
  197.     ListFw<int> l;
  198.  
  199.     std::cout << "Size: " << l.get_size() << '\n';
  200.  
  201.     l.push_back(42);
  202.     l.push_back(33);
  203.  
  204.     printListState(l);
  205.  
  206.     l.pop_front();
  207.     l.pop_back();
  208.     std::cout << "Size: " << l.get_size() << '\n';
  209.  
  210.     for (int i{ 0 }; i < 5; l.push_front(i++));
  211.  
  212.     printListState(l);
  213.     l.clear();
  214.  
  215.     for (int i{ 0 }; i < 5; l.push_back(i++));
  216.     printListState(l);
  217.  
  218.     l.insert_at(3, 42);
  219.     l.print();
  220.  
  221.     l.delete_at(3);
  222.     l.print();
  223.  
  224.     l.clear();
  225.     l.print();
  226.  
  227.     l.insert_at(42, 33);
  228.     l.print();
  229.     l.delete_at(0);
  230.     l.print();
  231.  
  232.     l.insert_at(-33, 42);
  233.     l.print();
  234.     l.delete_at(0);
  235.     l.print();
  236.  
  237.     return 0;
  238. }
  239.  
RAW Paste Data