SHARE
TWEET

Untitled

Fazl May 16th, 2019 56 Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. #include <iostream>
  2.  
  3. using namespace std;
  4.  
  5. template <typename ItemType>
  6. class BaseList {
  7. protected:
  8.     int listSize = 0;
  9. public:
  10.     BaseList() {};
  11.     virtual ~BaseList() {};
  12.     int size() const { return listSize; }
  13.     bool isEmpty()const { return !listSize; }
  14.  
  15.     virtual BaseList<ItemType>&addInHead(const ItemType& value) = 0;
  16.     virtual BaseList<ItemType>&addInTail(const ItemType& value) = 0;
  17.     virtual BaseList<ItemType>&removeFromHead() = 0;
  18.     virtual BaseList<ItemType>&removeFromTail() = 0;
  19.  
  20.     virtual ItemType&head() = 0;
  21.     virtual const ItemType&head()const = 0;
  22.     virtual ItemType&tail() = 0;
  23.     virtual const ItemType&tail() const = 0;
  24. };
  25.  
  26. template <typename ItemType>
  27. class LinkedList : public BaseList<ItemType>
  28. {
  29.     private:
  30.         struct ListNode
  31.         {
  32.             ItemType data;
  33.             ListNode *next;
  34.             ListNode *prev;
  35.         };
  36.  
  37.         ListNode* buildNode(const ItemType& value,
  38.             ListNode *left = nullptr,
  39.             ListNode *right = nullptr)
  40.         {
  41.             ListNode *newNode = new ListNode;
  42.             newNode->next = right;
  43.             newNode->prev = left;
  44.             newNode->data = value;
  45.             if (left)
  46.             {
  47.                 left->next = newNode;
  48.             }
  49.             if (right)
  50.             {
  51.                 right->prev = newNode;
  52.             }
  53.             return newNode;
  54.         }
  55.         ListNode* addAfter(const ItemType& value, ListNode *node)
  56.         {
  57.             return buildNode(value, node, node->next);
  58.         }
  59.         ListNode* addBefore(const ItemType& value, ListNode *node)
  60.         {
  61.             return buildNode(value, node->prev, node);
  62.         }
  63.         void remove(ListNode *node)
  64.         {
  65.             if (node)
  66.             {
  67.                 if (node->next)
  68.                 {
  69.                     node->next->prev = node->prev;
  70.                 }
  71.                 if (node->prev)
  72.                 {
  73.                     node->prev->next = node->next;
  74.                 }
  75.  
  76.                 node->next = node->prev = nullptr;
  77.                 delete(node);
  78.             }
  79.         }
  80.  
  81.         ListNode* m_pHead;
  82.         ListNode* m_pTail;
  83.         int listSize = 0;
  84.        
  85.     public:
  86.         LinkedList();
  87.         virtual BaseList<ItemType>& addInHead(const ItemType& Item);
  88.         virtual BaseList<ItemType>& addInTail(const ItemType& Item);
  89.         virtual BaseList<ItemType>& removeFromHead();
  90.         virtual BaseList<ItemType>& removeFromTail();
  91.         virtual ItemType& operator[](const int index);
  92.         virtual const ItemType& operator[](const int index) const;
  93.         virtual ~LinkedList();
  94. };
  95.  
  96. template <typename ItemType>
  97. LinkedList<ItemType>::LinkedList()
  98. {
  99.     m_pHead = m_pTail = nullptr;
  100.     listSize = 0;
  101. }
  102.  
  103. template <typename ItemType>
  104. BaseList<ItemType>& LinkedList<ItemType>::addInHead(const ItemType& Item)
  105. {
  106.     if (listSize)
  107.     {
  108.         m_pHead = addBefore(Item, m_pHead);
  109.     }
  110.     else
  111.     {
  112.         m_pHead = m_pTail = buildNode(Item);
  113.     }
  114.     listSize++;
  115.  
  116.     return *this;
  117. }
  118.  
  119. template <typename ItemType>
  120. BaseList<ItemType>& LinkedList<ItemType>::addInTail(const ItemType& Item)
  121. {
  122.     if (listSize)
  123.     {
  124.         m_pTail = addAfter(Item, m_pTail);
  125.     }
  126.     else
  127.     {
  128.         m_pHead = m_pTail = buildNode(Item);
  129.     }
  130.     listSize++;
  131.  
  132.     return *this;
  133. }
  134.  
  135. template <typename ItemType>
  136. BaseList<ItemType>& LinkedList<ItemType>::removeFromHead()
  137. {
  138.     switch (listSize)
  139.     {
  140.         case 0:
  141.             return *this;
  142.         case 1:
  143.             remove(m_pHead);
  144.             m_pHead = m_pTail = nullptr;
  145.             break;
  146.         default:
  147.             ListNode* temp = m_pHead;
  148.             m_pHead = m_pHead->next;
  149.             remove(temp);
  150.     }
  151.  
  152.     listSize--;
  153.  
  154.     return *this;
  155. }
  156.  
  157. template <typename ItemType>
  158. BaseList<ItemType>& LinkedList<ItemType>::removeFromTail()
  159. {
  160.     switch (listSize)
  161.     {
  162.         case 0:
  163.             return *this;
  164.         case 1:
  165.             remove(m_pHead);
  166.             m_pHead = m_pTail = nullptr;
  167.             break;
  168.         default:
  169.             ListNode* temp = m_pTail;
  170.             m_pTail = m_pTail->prev;
  171.             remove(temp);
  172.     }
  173.  
  174.     listSize--;
  175.  
  176.     return *this;
  177. }
  178.  
  179. template <typename ItemType>
  180. ItemType& LinkedList<ItemType>::operator[](const int index)
  181. {
  182.     // Не реализована проверка на выход индекса за пределы [0, m_size - 1]
  183.  
  184.     ListNode *temp = nullptr;
  185.     int i;
  186.  
  187.     if (index < listSize / 2)
  188.     {
  189.         temp = m_pHead;
  190.         i = 0;
  191.  
  192.         while (i++ < index)
  193.         {
  194.             temp = temp->next;
  195.         }
  196.     }
  197.     else
  198.     {
  199.         temp = m_pTail;
  200.         i = listSize - 1;
  201.  
  202.         while (i-- > index)
  203.         {
  204.             temp = temp->prev;
  205.         }
  206.     }
  207.  
  208.     return temp->data;
  209. }
  210.  
  211. template <typename ItemType>
  212. const ItemType& LinkedList<ItemType>::operator[](const int index) const
  213. {
  214.     // Не реализована проверка на выход индекса за пределы [0, m_size - 1]
  215.  
  216.     ListNode *temp = nullptr;
  217.     int i;
  218.  
  219.     if (index < listSize / 2)
  220.     {
  221.         temp = m_pHead;
  222.         i = 0;
  223.  
  224.         while (i++ < index)
  225.         {
  226.             temp = temp->next;
  227.         }
  228.     }
  229.     else
  230.     {
  231.         temp = m_pTail;
  232.         i = listSize - 1;
  233.  
  234.         while (i-- > index)
  235.         {
  236.             temp = temp->prev;
  237.         }
  238.     }
  239.  
  240.     return temp->data;
  241. }
  242.  
  243. template <typename ItemType>
  244. LinkedList<ItemType>::~LinkedList()
  245. {
  246.     while (listSize)
  247.     {
  248.         remove(m_pHead);
  249.     }
  250. }
  251.  
  252.  
  253. int main() {
  254.  
  255.     return 0;
  256. }
RAW Paste Data
We use cookies for various purposes including analytics. By continuing to use Pastebin, you agree to our use of cookies as described in the Cookies Policy. OK, I Understand
 
Top