Advertisement
karol_dziachan

Doubly Linked List c++

Nov 26th, 2020 (edited)
1,192
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 7.08 KB | None | 0 0
  1. ---------------------------------------------------------------------------------------------------------------------------------------
  2. -----------------------------------------------------------DOUBLY-LINKED-LIST-C++-----------------------------------------------------
  3. ---------------------------------------------------------------------------------------------------------------------------------------
  4.  
  5. class Node
  6. {
  7.  
  8. private:
  9.     Node* next;
  10.     Node* previous;
  11.     int iVal;
  12. public:
  13.     Node(int iElem) { iVal = iElem; }
  14.     ~Node() {  }
  15.     Node* iGetNext() { return next; }
  16.     Node* iGetPrevious() { return previous; }
  17.     int iGetVal() { return iVal; }
  18.     void vSetNext(Node* node) { next = node; }
  19.     void vSetPrevious(Node* node) { previous = node; }
  20.     void vSetIVal(int iElem) { iVal = iElem; }
  21. };
  22.  
  23. class CLinkedList
  24. {
  25.  
  26.  
  27. public:
  28.     CLinkedList();
  29.     ~CLinkedList();
  30.     void vAdd(int iELem);
  31.     void vAdd(int iElem, int iIndex);
  32.     void vAddFirst(int iElem);
  33.     void vRemoveFirst();
  34.     void vRemoveLast();
  35.     void vRemove(int iIndex);
  36.     int iGet(int iIndex);
  37.     bool bContains(int iElem);
  38.     void vToString();
  39.     void vClear();
  40.     int iSize();
  41.     bool bIsEmpty();
  42.     void vReplace(int iElem, int iIndex);
  43.    
  44. private:
  45.     Node* pcHead;
  46.     Node* pcTail;
  47.     Node* current;
  48.     void printHelper(Node* node);
  49.     //vector <Node*> vList;
  50.     int iCounter;
  51.     void vAddLikeFirst(int iELem);
  52.     void vReplaceHelper(int iElem, int iIndex, Node* tmp);
  53.     bool bContains(int iElem, Node* tmp);
  54.     void vAddHelper(int iElem, int iIndex, Node* tmp);
  55.     Node* pcGetHelper(int iIndex, Node* tmp);
  56.     void vRemoveHelper(int iIndex, Node* tmp);
  57. };
  58.  
  59.  
  60. ------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
  61.  
  62. CLinkedList::CLinkedList()
  63. {
  64.     pcHead = NULL;
  65.     pcTail = NULL;
  66.     current = NULL;
  67.     iCounter = 0;
  68. }
  69.  
  70. CLinkedList :: ~CLinkedList()
  71. {
  72.     Node* current = pcHead;
  73.     Node* next;
  74.  
  75.     for (int i = 0; i < iCounter-1; i++)
  76.     {
  77.         next = current->iGetNext();
  78.         cout << "Delete: " << current->iGetVal() << " ";
  79.         delete current;
  80.         current = next;
  81.     }
  82.     iCounter = 0;
  83.    
  84. }
  85.  
  86.  
  87.  
  88. void CLinkedList::vAdd(int iElem)
  89. {
  90.     if (bIsEmpty())
  91.         vAddLikeFirst(iElem);
  92.     else
  93.     {
  94.         Node* nElem = new Node(iElem);
  95.  
  96.         nElem->vSetPrevious(current);
  97.         current->vSetNext(nElem);
  98.         nElem->vSetNext(pcHead);
  99.         pcTail = nElem;
  100.         pcHead->vSetPrevious(nElem);
  101.         iCounter++;
  102.  
  103.         current = nElem;
  104.     }
  105. }
  106.  
  107. void CLinkedList::vAddLikeFirst(int iElem)
  108. {
  109.     Node* nElem = new Node(iElem);
  110.     pcHead = nElem;
  111.     pcTail = nElem;
  112.     current = nElem;
  113.     nElem->vSetPrevious(nElem);
  114.     nElem->vSetNext(nElem);
  115.     iCounter++;
  116. }
  117.  
  118. bool CLinkedList::bIsEmpty()
  119. {
  120.     return iCounter == 0;
  121. }
  122.  
  123. void CLinkedList :: vToString()
  124. {
  125.     printHelper(pcHead);
  126.    
  127.     cout << endl;
  128. }
  129.  
  130. void CLinkedList::printHelper(Node* node)
  131. {
  132.     cout << "value: " << node->iGetVal() << " " << "previous: " << node->iGetPrevious()->iGetVal() << " next: "<< node->iGetNext()->iGetVal() << endl;
  133.     if (node->iGetNext() != pcHead)
  134.         printHelper(node->iGetNext());
  135. }
  136.  
  137. void CLinkedList::vAdd(int iElem, int iIndex)
  138. {
  139.     if (iIndex > 0 && iIndex < iCounter)
  140.     {
  141.         vAddHelper(iElem, iIndex, pcHead);
  142.     }
  143.     else
  144.         vAddFirst(iElem);
  145. }
  146.  
  147. void CLinkedList::vAddHelper(int iElem, int iIndex, Node* tmp)
  148. {
  149.     if (iIndex != 0)
  150.         vAddHelper(iElem, iIndex - 1, tmp->iGetNext());
  151.     else
  152.     {
  153.         Node* nElem = new Node(iElem);
  154.  
  155.         nElem->vSetNext(tmp);
  156.         nElem->vSetPrevious(tmp->iGetPrevious());
  157.         tmp->iGetPrevious()->vSetNext(nElem);
  158.         tmp->vSetPrevious(nElem);
  159.    
  160.         iCounter++;
  161.     }
  162. }
  163.  
  164. void CLinkedList::vAddFirst(int iElem)
  165. {
  166.     if (bIsEmpty())
  167.         vAddLikeFirst(iElem);
  168.     else
  169.     {
  170.         Node* nElem = new Node(iElem);
  171.  
  172.         nElem->vSetPrevious(pcTail);
  173.         nElem->vSetNext(pcHead);
  174.         pcHead -> vSetPrevious(nElem);
  175.         pcHead = nElem;
  176.         pcTail->vSetNext(nElem);
  177.  
  178.         iCounter++;
  179.     }
  180. }
  181.  
  182. void CLinkedList::vRemoveFirst()
  183. {
  184.     if (!bIsEmpty())
  185.     {
  186.         Node* nElem = pcHead->iGetNext();
  187.    
  188.  
  189.         pcHead = nElem;
  190.         pcTail->vSetNext(pcHead);
  191.         pcHead->vSetPrevious(pcTail);
  192.  
  193.         iCounter--;
  194.     }
  195. }
  196.  
  197. void CLinkedList::vRemoveLast()
  198. {
  199.     if (!bIsEmpty())
  200.     {
  201.         Node* nElem = pcTail->iGetPrevious();
  202.  
  203.         pcTail = nElem;
  204.  
  205.         pcHead->vSetPrevious(pcTail);
  206.         pcTail->vSetNext(pcHead);
  207.  
  208.         iCounter--;
  209.     }
  210. }
  211.  
  212. void CLinkedList::vRemove(int iIndex)
  213. {
  214.     if (iIndex == 0)
  215.         vRemoveFirst();
  216.     if (iIndex == iCounter - 1)
  217.         vRemoveLast();
  218.  
  219.     if (!bIsEmpty() && iIndex > 0 && iIndex < iCounter)
  220.         vRemoveHelper(iIndex, pcHead);
  221.     else
  222.         cout << "UNBOUND OPERATION!!!" << endl;
  223. }
  224.  
  225. void CLinkedList::vRemoveHelper(int iIndex, Node* tmp)
  226. {
  227.     if (iIndex != 0)
  228.         vRemoveHelper(iIndex - 1, tmp->iGetNext());
  229.     else
  230.     {
  231.         tmp->iGetPrevious()->vSetNext(tmp->iGetNext());
  232.         tmp->iGetNext()->vSetPrevious(tmp->iGetPrevious());
  233.     }
  234. }
  235.  
  236. bool CLinkedList::bContains(int iElem)
  237. {
  238.     return bContains(iElem, pcHead);
  239. }
  240.  
  241. bool CLinkedList::bContains(int iElem, Node* tmp)
  242. {
  243.     if (iElem == tmp->iGetVal())
  244.         return true;
  245.     else if (tmp->iGetNext() != pcHead)
  246.         bContains(iElem, tmp->iGetNext());
  247.     else
  248.         return false;
  249. }
  250.  
  251. void CLinkedList::vClear()
  252. {
  253.     delete pcHead;
  254.     delete pcTail;
  255.  
  256.     pcHead = nullptr;
  257.     pcTail = nullptr;
  258.  
  259.     iCounter = 0;
  260.  
  261.     cout << "List is empty? " << bIsEmpty() << endl;
  262. }
  263.  
  264. int CLinkedList::iSize()
  265. {
  266.     return iCounter;
  267. }
  268.  
  269. void CLinkedList::vReplace(int iElem, int iIndex)
  270. {
  271.     vReplaceHelper(iElem, iIndex, pcHead);
  272. }
  273.  
  274. void CLinkedList::vReplaceHelper(int iElem, int iIndex, Node* tmp)
  275. {
  276.     if (iIndex != 0)
  277.         vReplaceHelper(iElem, iIndex - 1, tmp->iGetNext());
  278.     else
  279.         tmp->vSetIVal(iElem);
  280. }
  281.  
  282. int CLinkedList::iGet(int iIndex)
  283. {
  284.     if (iIndex < iCounter && iIndex > 0)
  285.         return pcGetHelper(iIndex, pcHead)->iGetVal();
  286.     else
  287.         return(-1);
  288. }
  289.  
  290. Node* CLinkedList :: pcGetHelper(int iIndex, Node* tmp)
  291. {
  292.     if (iIndex != 0)
  293.         pcGetHelper(iIndex - 1, tmp->iGetNext());
  294.     else
  295.         return tmp;
  296. }
  297.  
  298. ---------------------------------------------------------------------------------------------------------------------------------------
  299. -----------------------------------------------------------------TESTER----------------------------------------------------------------
  300. ---------------------------------------------------------------------------------------------------------------------------------------
  301. void vTest()
  302. {
  303.     CLinkedList list;
  304.  
  305.     list.vAdd(10);
  306.     list.vAdd(20);
  307.     list.vAdd(30);
  308.     list.vAdd(40);
  309.     list.vAdd(50);
  310.     list.vAdd(60);
  311.     list.vAdd(99);
  312.  
  313.     list.vToString();
  314.  
  315.     list.vAdd(2555555, 2);
  316.  
  317.     list.vToString();
  318.  
  319.     list.vAddFirst(999999);
  320.  
  321.     list.vToString();
  322.  
  323.     list.vRemoveFirst();
  324.  
  325.     list.vToString();
  326.  
  327.     list.vRemoveLast();
  328.    
  329.     list.vToString();
  330.  
  331.     list.vRemove(2);
  332.  
  333.     list.vToString();
  334.  
  335.     cout << "Do you have 10? " << list.bContains(10) << endl;
  336.     cout << "How many elems have u? " << list.iSize() << endl;
  337.  
  338.     list.vReplace(100000, 3);
  339.    
  340.     list.vToString();
  341.  
  342.  
  343.     cout << "What is in third place? " << list.iGet(2) << endl;
  344. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement