avr39ripe

cppListClass

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