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

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!