fork download
copy 
  1. #include <iostream>
  2. #include <cstdlib>
  3. #include <ctime>
  4. #include <stack>
  5.  
  6. using namespace std;
  7.  
  8.  
  9. template<class T>
  10. class Link
  11. {
  12.       private:
  13.               T data;
  14.               Link<T> *next;
  15.               Link<T> *previous;
  16.       public:
  17.              Link(T data);
  18.              void displayLink();
  19.              T getData();
  20.              void setData(T data);
  21.              Link<T> *getNext();
  22.              void setNext(Link<T> *next);
  23.              Link<T> *getPrevious();
  24.              void setPrevious(Link<T> *previous);
  25.              template<class U> friend std::ostream& operator<< (std::ostream& print, Link<U>& obj);
  26.  
  27. };
  28.  
  29. template<class T>
  30. Link<T>::Link(T data)
  31. {
  32.      setData(data);
  33.      setNext(NULL);
  34.      setPrevious(NULL);
  35.  
  36. }
  37.  
  38. template<class T>
  39. void Link<T>::displayLink()
  40. {
  41.      std::cout<<getData()<<" ";
  42. }
  43.  
  44. template<class T>
  45. T Link<T>::getData()
  46. {
  47.      return data;
  48. }
  49.  
  50. template<class T>
  51. void Link<T>::setData(T data)
  52. {
  53.      this->data = data;
  54. }
  55.  
  56. template<class T>
  57. Link<T> *Link<T>::getNext()
  58. {
  59.       return next;
  60. }
  61.  
  62. template<class T>
  63. void Link<T>::setNext(Link<T> *next)
  64. {
  65.       this->next = next;
  66. }
  67.  
  68. template<class T>
  69. Link<T> *Link<T>::getPrevious()
  70. {
  71.       return previous;
  72. }
  73.  
  74. template<class T>
  75. void Link<T>::setPrevious(Link<T> *previous)
  76. {
  77.       this->previous = previous;
  78. }
  79.  
  80.  
  81. template <class U>
  82. std::ostream& operator<<(std::ostream& print, Link<U> & L)
  83. {
  84.         print << L.getData();
  85.         return print;
  86. }
  87.  
  88. template<class T>
  89. class DoublyLinkedList
  90. {
  91.       private:
  92.               Link<T> *first;
  93.               Link<T> *last;
  94.       public:
  95.              DoublyLinkedList();
  96.              ~DoublyLinkedList();
  97.              Link<T> *getFirst();
  98.              void setFirst(Link<T> *first);
  99.              Link<T> *getLast();
  100.              void setLast(Link<T> *first);
  101.              bool isEmpty();
  102.              Link<T> *find(T key);
  103.              void insertFirst(T dd);
  104.              void insertLast(T dd);
  105.              void deleteFirst();
  106.              void deleteLast();
  107.              bool insertAfter(T key,T dd);
  108.              void deleteKey(T key);
  109.              void displayForward();
  110.              void displayBackward();
  111.              void BSTinsert(Link<T> *&root,Link<T> *z);
  112.              void BSTtoDLL(Link<T> *root,DoublyLinkedList<T> &L);
  113.              void BSTSort();
  114. };
  115.  
  116. template<class T>
  117. DoublyLinkedList<T>::DoublyLinkedList()
  118. {
  119.     setFirst(NULL);
  120.     setLast(NULL);
  121. }
  122.  
  123. template<class T>
  124. DoublyLinkedList<T>::~DoublyLinkedList()
  125. {
  126.     while(!isEmpty())
  127.     {
  128.         deleteFirst();
  129.     }
  130. }
  131.  
  132. template<class T>
  133. Link<T> *DoublyLinkedList<T>::getFirst()
  134. {
  135.        return first;
  136. }
  137.  
  138. template<class T>
  139. void DoublyLinkedList<T>::setFirst(Link<T> *first)
  140. {
  141.      this->first = first;
  142. }
  143.  
  144. template<class T>
  145. Link<T> *DoublyLinkedList<T>::getLast()
  146. {
  147.        return last;
  148. }
  149.  
  150. template<class T>
  151. void DoublyLinkedList<T>::setLast(Link<T> *last)
  152. {
  153.      this->last = last;
  154. }
  155.  
  156. template<class T>
  157. bool DoublyLinkedList<T>::isEmpty()
  158. {
  159.      return getFirst()==NULL;
  160. }
  161.  
  162. template<class T>
  163.  Link<T> *DoublyLinkedList<T>::find(T key)
  164.  {
  165.          Link<T> *current = getFirst();
  166.          while(current != NULL && !(current->getData == key))
  167.                current = current->getNext();
  168.          return current;
  169.  }
  170.  
  171.  template<class T>
  172.  void DoublyLinkedList<T>::insertFirst(T dd)
  173.  {
  174.       Link<T> *newLink = new Link<T>(dd);
  175.       if(isEmpty())
  176.            setLast(newLink);
  177.       else
  178.           getFirst()->setPrevious(newLink);
  179.       newLink->setNext(getFirst());
  180.       setFirst(newLink);
  181.  }
  182.  
  183.  template<class T>
  184.  void DoublyLinkedList<T>::insertLast(T dd)
  185.  {
  186.       Link<T> *newLink = new Link<T>(dd);
  187.       if(isEmpty())
  188.       {
  189.           setFirst(newLink);
  190.       }
  191.       else
  192.       {
  193.           getLast()->setNext(newLink);
  194.           newLink->setPrevious(getLast());
  195.       }
  196.       setLast(newLink);
  197.  }
  198.  
  199.  template<class T>
  200.  void DoublyLinkedList<T>::deleteFirst()
  201.  {
  202.       if(isEmpty())
  203.            return;
  204.       Link<T> *temp = getFirst();
  205.       if(getFirst()->getNext() == NULL)
  206.             setLast(NULL);
  207.       else
  208.          getFirst()->getNext()->setPrevious(NULL);
  209.       setFirst(getFirst()->getNext());
  210.       delete temp;
  211.  }
  212.  
  213.  template<class T>
  214.  void DoublyLinkedList<T>::deleteLast()
  215.  {
  216.       if(isEmpty())
  217.          return;
  218.       Link<T> *temp = getLast();
  219.       if(getFirst()->getNext() == NULL)
  220.              setFirst(NULL);
  221.       else
  222.           getLast()->getPrevious()->setNext(NULL);
  223.       setLast(getLast()->getPrevious());
  224.       delete temp;
  225.  }
  226.  
  227.  template<class T>
  228.  bool DoublyLinkedList<T>::insertAfter(T key,T dd)
  229.  {
  230.       Link<T> *current = find(key);
  231.       if(current == NULL)
  232.              return false;
  233.       Link<T> *newLink = new Link<T>(dd);
  234.       if(current->getNext() == NULL)
  235.       {
  236.            newLink->setNext(NULL);
  237.            setLast(newLink);
  238.       }
  239.       else
  240.       {
  241.           newLink->setNext(current->getNext());
  242.           current->getNext()->setPrevious(newLink);
  243.       }
  244.       newLink->setPrevious(current);
  245.       current->setNext(newLink);
  246.       return true;
  247.  }
  248.  
  249.  template<class T>
  250.  void DoublyLinkedList<T>::deleteKey(T key)
  251.  {
  252.       Link<T> *current = find(key);
  253.       if(current==NULL)
  254.            return;
  255.       if(current->getPrevious() == NULL)
  256.              setFirst(current->getNext());
  257.       else
  258.              current->getPrevious()->setNext(current->getNext());
  259.       if(current->getNext() == NULL)
  260.              setLast(current->getPrevious());
  261.       else
  262.              current->getNext()->setPrevious(current->getPrevious());
  263.       delete current;
  264.  }
  265.  
  266.  template<class T>
  267.  void DoublyLinkedList<T>::displayForward()
  268.  {
  269.       std::cout<<"List (first-->last): ";
  270.       Link<T> *current = getFirst();
  271.       while(current != NULL)
  272.       {
  273.          current->displayLink();
  274.          current = current->getNext();
  275.       }
  276.       std::cout<<"\n";
  277.  }
  278.  
  279.  template<class T>
  280.  void DoublyLinkedList<T>::displayBackward()
  281.  {
  282.       std::cout<<"List (last-->first): ";
  283.       Link<T> *current = getLast();
  284.       while(current != NULL)
  285.       {
  286.          current->displayLink();
  287.          current = current->getPrevious();
  288.       }
  289.       std::cout<<"\n";
  290.  }
  291.  
  292. template<class T>
  293. void DoublyLinkedList<T>::BSTinsert(Link<T> *&root,Link<T> *z)
  294. {
  295.     Link<T> *y = NULL;
  296.     Link<T> *x = root;
  297.     while(x != NULL)
  298.     {
  299.         y = x;
  300.         if(z->getData() < x->getData())
  301.             x = x->getPrevious();
  302.         else
  303.             x = x->getNext();
  304.     }
  305.     if(y == NULL)
  306.         root = z;
  307.     else if(z->getData() < y->getData())
  308.             y->setPrevious(z);
  309.          else
  310.             y->setNext(z);
  311. }
  312.  
  313. template<class T>
  314. void DoublyLinkedList<T>::BSTtoDLL(Link<T> *root,DoublyLinkedList<T> &L)
  315. {
  316. 	std::stack<Link<T>*> s;
  317. 	Link<T>* current = root;
  318. 	while (current || !s.empty())
  319. 	{
  320. 		while (current)
  321. 		{
  322. 			s.push(current);
  323. 			current = current->getPrevious();
  324. 		}
  325. 		current = s.top();
  326. 		s.pop();
  327.  
  328.  
  329. 		if(L.isEmpty())
  330.             L.setFirst(current);
  331.         else
  332.             L.getLast()->setNext(current);
  333.         current->setPrevious(L.getLast());
  334.         L.setLast(current);
  335.  
  336. 		current = current->getNext();
  337. 	}
  338. }
  339.  
  340. template<class T>
  341. void DoublyLinkedList<T>::BSTSort()
  342. {
  343.     Link<T> *temp;
  344.     Link<T> *root = NULL;
  345.     while(!isEmpty())
  346.     {
  347.         temp = getFirst();
  348.         if(getFirst()->getNext() == NULL)
  349.             setLast(NULL);
  350.         else
  351.             getFirst()->getNext()->setPrevious(NULL);
  352.         setFirst(getFirst()->getNext());
  353.         temp->setPrevious(NULL);
  354.         temp->setNext(NULL);
  355.         BSTinsert(root,temp);
  356.     }
  357.     BSTtoDLL(root,*this);
  358. }
  359.  
  360. int main(int argc, char *argv[])
  361. {
  362.     DoublyLinkedList<int> A;
  363.     int k,n,m;
  364.     srand(time(NULL));
  365.     cin>>n>>m;
  366.     for(k = 0;k < n;k++)
  367.         A.insertLast(rand()%m);
  368.     A.displayForward();
  369.     A.displayBackward();
  370.     A.BSTSort();
  371.     A.displayForward();
  372.     A.displayBackward();
  373.         while(!A.isEmpty())
  374.             A.deleteFirst();
  375.     return EXIT_SUCCESS;
  376. }
  377.  
Success #stdin #stdout 0s 4244KB
comments (?)
stdin
copy 
30 1000
stdout
copy 
List (first-->last): 581 128 743 389 317 378 746 976 796 949 911 248 214 131 784 139 492 195 679 321 299 204 13 480 821 718 422 111 443 406 
List (last-->first): 406 443 111 422 718 821 480 13 204 299 321 679 195 492 139 784 131 214 248 911 949 796 976 746 378 317 389 743 128 581 
List (first-->last): 13 111 128 131 139 195 204 214 248 299 317 321 378 389 406 422 443 480 492 581 679 718 743 746 784 796 821 911 949 976 
List (last-->first): 976 949 911 821 796 784 746 743 718 679 581 492 480 443 422 406 389 378 321 317 299 248 214 204 195 139 131 128 111 13
https://ideone.com/PuqaKw
language:
C++ (gcc 8.3)
created:
5 years ago
visibility:
secret

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!