Обектно-ориентирана реализация на свързан списък

В примерната реализация се използват два шаблона на класове List и ListNode, като всеки обект на класа List е свързан списък от обекти на класа ListNode. Реализация дава възможност да се извършват следните операции над списъци:
-    добавяне на елемент в началото на списъка
-    добавяне на елемент в края на списъка
-    изключване на елемент от началото на списъка
-    изключване на елемент от края на списъка
-    завършване обработката на списъка

Файл listnode.h

  1. #ifndef LISTNODE_H
  2. #define LISTNODE_H
  3.  
  4. template <class NodeType> class List;
  5. template <class NodeType>
  6.  
  7. class ListNode
  8. {
  9.     friend class List <NodeType>;
  10. public:
  11.     ListNode (const NodeType &);
  12.     NodeType getData () const;
  13. private:
  14.     NodeType data;
  15.     ListNode <NodeType> *next;
  16. };
  17.  
  18. template <class NodeType>
  19. ListNode <NodeType>::ListNode (const NodeType &info): data(info), next(NULL)
  20. {
  21. }
  22.  
  23. template <class NodeType>
  24. NodeType ListNode <NodeType>::getData() const
  25. {
  26.     return data;
  27. }
  28. #endif

Файл list.h
  1. #ifndef LIST_H
  2. #define LIST_H
  3.  
  4. #include <iostream>
  5. #include <cassert>
  6. #include "listnode.h"
  7.  
  8. using std::cout;
  9. using std::endl;
  10.  
  11. template <class NodeType>
  12. class List
  13. {
  14. public:
  15.     List ();
  16.     ~List ();
  17.     void insertAtBeg(const NodeType &);
  18.     void insertAtEnd(const NodeType &);
  19.     bool removeFromBeg(NodeType &);
  20.     bool removeFromEnd(NodeType &);
  21.     bool isEmpty() const;
  22.     void print() const;
  23. private:
  24.     ListNode <NodeType> *first;
  25.     ListNode <NodeType> *last;
  26.     ListNode <NodeType>* getNewNode(const NodeType &);
  27. };
  28.  
  29. template <class NodeType>
  30. List <NodeType>::List() : first(NULL), last(NULL)
  31. {
  32. }
  33.  
  34. template <class NodeType>
  35. List <NodeType>::~List()
  36. {
  37.     if (!isEmpty())
  38.     {
  39.         cout << "Изключване на обекти: ";
  40.         ListNode <NodeType> *current = first, *temp;
  41.         while (current != NULL)
  42.         {
  43.             temp = current;
  44.             cout << temp -> data << \n ;
  45.             current = current -> next;
  46.             delete temp;
  47.         }
  48.     }
  49.     cout << "Всички обекти са изключени!" << endl;
  50. }
  51.  
  52. template <class NodeType>
  53. bool List<NodeType>::isEmpty() const
  54. {
  55.     return first==NULL;
  56. }
  57.  
  58. template <class NodeType>
  59. ListNode <NodeType> *List <NodeType>::getNewNode(const NodeType &value)
  60. {
  61.     ListNode <NodeType> *ptr = new ListNode<NodeType>(value);
  62.     assert (ptr != NULL);
  63.     return ptr;
  64. }
  65.  
  66. template <class NodeType>
  67. void List <NodeType>::insertAtBeg(const NodeType &value)
  68. {
  69.     ListNode <NodeType> *ptr = getNewNode(value);
  70.     if (isEmpty())
  71.     {
  72.         first = last = ptr;
  73.     }
  74.     else
  75.     {
  76.         ptr -> next = first;
  77.         first = ptr;
  78.     }
  79. }
  80.  
  81. template <class NodeType>
  82. void List <NodeType>::insertAtEnd (const NodeType &value)
  83. {
  84.     ListNode <NodeType> *ptr = getNewNode(value);
  85.     if(isEmpty())
  86.     {
  87.         first = last = ptr;
  88.     }
  89.     else
  90.     {
  91.         last -> next = ptr;
  92.         last = ptr;
  93.     }
  94. }
  95.  
  96. template <class NodeType>
  97. bool List<NodeType>::removeFromBeg(NodeType &value)
  98. {
  99.     if(isEmpty())
  100.         return false;
  101.  
  102.     ListNode <NodeType> *temp = first;
  103.     if (first == last)
  104.         first = last = NULL;
  105.     else
  106.         first = first -> next;
  107.  
  108.     value = temp -> data;
  109.     delete temp;
  110.     return true;
  111. }
  112.  
  113. template <class NodeType>
  114. bool List<NodeType>::removeFromEnd (NodeType &value)
  115. {
  116.     if (isEmpty())
  117.         return false;
  118.  
  119.     ListNode <NodeType> *temp = last;
  120.     if (first == last)
  121.     {
  122.         first = last = NULL;
  123.     }
  124.     else
  125.     {
  126.         ListNode <NodeType> *current = first;
  127.         while (current -> next != last)
  128.             current = current -> next;
  129.  
  130.         last = current;
  131.         last -> next = NULL;
  132.     }
  133.  
  134.     value = temp -> data;
  135.     delete temp;
  136.     return true;
  137. }
  138.  
  139. template <class NodeType>
  140. void List<NodeType>::print () const
  141. {
  142.     if (isEmpty())
  143.     {
  144.         cout << "Списъкът е празен!\n";
  145.         return;
  146.     }
  147.  
  148.     cout << "Списък: ";
  149.     ListNode <NodeType> *current = first;
  150.     while (current != NULL)
  151.     {
  152.         cout << current -> data << ;
  153.         current = current -> next;
  154.     }
  155.  
  156.     cout << endl;
  157. }
  158. #endif