fork download
copy 
  1. #include <iostream>
  2. using namespace std;
  3.  
  4. struct node {
  5.     int data;
  6.     node* next;
  7.     node* prev;
  8.     node(int d) {
  9.         data = d;
  10.         next = NULL;
  11.         prev = NULL;
  12.     }
  13. };
  14. typedef node* position;
  15.  
  16. class DLL
  17. {
  18.     position Head;
  19.     position tail;
  20.     int counter;
  21. public:
  22.     DLL() 
  23.     {
  24.         Head = NULL;
  25.         tail = NULL;
  26.         counter = 0;
  27.     }
  28.     position first()
  29.     {
  30.         return Head;
  31.     }
  32.     position End()
  33.     {
  34.         return tail;
  35.     }
  36.     position Next(position p)
  37.     {
  38.         if (p == NULL || p == tail)
  39.             return NULL;
  40.         return p->next;
  41.     }
  42.     position previous(position p)
  43.     {
  44.         if (p == Head)
  45.             return NULL;
  46.         return p->prev;
  47.     }
  48.     void InsertAtBeginning(int x)
  49.     {
  50.         position newNode = new node(x);
  51.         newNode->next = Head;
  52.         if (Head != NULL)
  53.             Head->prev = newNode;
  54.         else tail = newNode;
  55.         Head = newNode;
  56.     }
  57.     void Insert(int x, position p)
  58.     {
  59.         position newNode = new node(x);
  60.         if (p == NULL)
  61.         {
  62.             Head = newNode;
  63.             tail = newNode;
  64.         }
  65.         else if (p == tail)
  66.         {
  67.             newNode->prev = tail;
  68.             tail->next = newNode;
  69.             tail = newNode;
  70.         }
  71.         else
  72.         {
  73.             newNode->next = p->next;
  74.             newNode->prev = p;
  75.             p->next->prev = newNode;
  76.             p->next = newNode;
  77.         }
  78.         counter++;
  79.     }
  80.     void Delete(position p)
  81.     {
  82.         if (counter == 0)
  83.         {
  84.             cout << "List is empty\n";
  85.             return;
  86.         }
  87.         if (p == Head && p == tail)
  88.         {
  89.             delete p;
  90.             Head = NULL;
  91.             tail = NULL;
  92.         }
  93.         else if (p == Head)
  94.         {
  95.             Head = p->next;
  96.             if (Head) Head->prev = NULL;
  97.             delete p;
  98.         }
  99.         else if (p == tail)
  100.         {
  101.             tail = p->prev;
  102.             if (tail) tail->next = NULL;
  103.             delete p;
  104.         }
  105.         else
  106.         {
  107.             p->prev->next = p->next;
  108.             p->next->prev = p->prev;
  109.             delete p;
  110.         }
  111.         counter--;
  112.     }
  113.  
  114.     position Locate(int x)
  115.     {
  116.         position temp = Head;
  117.         while (temp != NULL)
  118.         {
  119.             if (temp->data == x)
  120.                 return temp;
  121.             temp = temp->next;
  122.         }
  123.         return NULL;
  124.     }
  125.  
  126.     int Retrieve(position p)
  127.     {
  128.         if (p == NULL)
  129.         {
  130.             cout << "Position is invalid!\n";
  131.             return -1;
  132.         }
  133.         return p->data;
  134.     }
  135.  
  136.     int size()
  137.     {
  138.         return counter;
  139.     }
  140.  
  141.     void display()
  142.     {
  143.         if (counter == 0)
  144.         {
  145.             cout << "List is empty\n";
  146.             return;
  147.         }
  148.         position temp = Head;
  149.         while (temp != NULL)
  150.         {
  151.             cout << temp->data << "  ";
  152.             temp = temp->next;
  153.         }
  154.         cout << endl;
  155.     }
  156. };
  157. void purge(DLL& l)
  158. {
  159.     position temp1 = l.first();
  160.     while (temp1 != NULL)
  161.     {
  162.         position temp2 = l.Next(temp1);
  163.         while (temp2 != NULL)
  164.         {
  165.             position temp = l.Next(temp2);
  166.             if (l.Retrieve(temp1) == l.Retrieve(temp2))
  167.             {
  168.                 l.Delete(temp2);
  169.             }
  170.             temp2 = temp;
  171.         }
  172.         temp1 = temp1->next;
  173.     }
  174. }
  175. void reverse(DLL& l)
  176. {
  177.     position i = l.first();
  178.     position j = l.End();
  179.     while( i != j && i != l.previous(j))
  180.     {
  181.         position TOD1 = l.Next(i);
  182.         position TOD2 = l.previous(j);
  183.         int temp1 = l.Retrieve(i);
  184.         int temp2 = l.Retrieve(j);
  185.         l.Insert(temp2, i);
  186.         l.Delete(i);
  187.         l.Insert(temp1, j);
  188.         l.Delete(j);
  189.         i = TOD1;
  190.         j = TOD2;
  191.     }
  192. }
  193. int main()
  194. {
  195.     DLL list;
  196.     list.Insert(1, list.first());//1
  197.     list.Insert(2, list.first());//1 2
  198.     list.Insert(3, list.Locate(2));//1 2 3
  199.     list.Insert(5, list.End());//1 2 3 5
  200.     list.Insert(4, list.previous(list.End()));//1 2 3 4 5
  201.     list.display();
  202.  
  203.     cout << "=================Testing purge===================\n";
  204.     DLL l;
  205.     l.Insert(10, l.End());
  206.     l.Insert(20, l.End());
  207.     l.Insert(10, l.End());
  208.     l.Insert(20, l.End());
  209.     l.Insert(30, l.End());
  210.     l.Insert(30, l.End());
  211.     l.display();//10 20 10 20 30 30
  212.     purge(l);
  213.     l.display();//10 20 30
  214.     cout << "=================Testing reverse===================\n";
  215.     reverse(list);//5 4 3 2 1
  216.     list.display();
  217.     cout << "===================insert from the start===========\n";
  218.     list.InsertAtBeginning(6);
  219.     list.InsertAtBeginning(7);
  220.     list.display();//7 6 5 4 3 2 1
  221. }
Success #stdin #stdout 0.01s 5296KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
1  2  3  4  5  
=================Testing purge===================
10  20  10  20  30  30  
10  20  30  
=================Testing reverse===================
5  4  3  2  1  
===================insert from the start===========
7  6  5  4  3  2  1
https://ideone.com/AJYDHx
language:
C++ (gcc 8.3)
created:
8 days 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!