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