fork download 
  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.     // Friend declarations for external functions
  151.     friend void Purge(List& list);
  152.     friend void Reverse(List& list);
  153. };
  154.  
  155. // Purge function outside the class
  156. void Purge(List& list) {
  157.     Position p = list.First();
  158.     while (p != NULL) {
  159.         Position q = p->next;
  160.         while (q != NULL) {
  161.             if (q->element == p->element) {
  162.                 Position temp = q;
  163.                 q = q->next;
  164.                 if (temp->prev != NULL)
  165.                     temp->prev->next = temp->next;
  166.                 if (temp->next != NULL)
  167.                     temp->next->prev = temp->prev;
  168.                 delete temp;
  169.                 list.counter--;  // Update the counter after deletion
  170.             } else {
  171.                 q = q->next;
  172.             }
  173.         }
  174.         p = p->next;
  175.     }
  176. }
  177.  
  178. // Reverse function outside the class
  179. void Reverse(List& list) {
  180.     Position current = list.First();
  181.     Position temp = NULL;
  182.  
  183.     // Reverse the list
  184.     while (current != NULL) {
  185.         temp = current->next;
  186.         current->next = current->prev;
  187.         current->prev = temp;
  188.         current = temp;
  189.     }
  190.  
  191.     // After reversal, update head and tail
  192.     temp = list.First();
  193.     list.head = list.END();
  194.     list.tail = temp;
  195. }
  196.  
  197. int main() {
  198.     List l;
  199.  
  200.     l.InsertAtStart(1);
  201.     l.InsertAtStart(2);
  202.     l.InsertAtStart(3);
  203.     l.InsertAtStart(4);
  204.     l.Insert(10, l.END());
  205.     l.Insert(-90, l.First());
  206.     l.Insert(100, l.END());
  207.     l.Insert(400, l.END());
  208.     l.Insert(-200, l.First());
  209.     l.Insert(534, NULL);
  210.     l.PrintList();
  211.  
  212.     List ll;
  213.     ll.InsertAtEnd(5);
  214.     ll.InsertAtEnd(4);
  215.     ll.InsertAtEnd(3);
  216.     ll.InsertAtEnd(2);
  217.     ll.PrintList();
  218.  
  219.     cout << "After purge: ";
  220.     Purge(l);
  221.     l.PrintList();
  222.  
  223.     cout << "After reverse: ";
  224.     Reverse(l);
  225.     l.PrintList();
  226.  
  227.     cout << "After purge: ";
  228.     Purge(ll);
  229.     ll.PrintList();
  230.  
  231.     cout << "After reverse: ";
  232.     Reverse(ll);
  233.     ll.PrintList();
  234.  
  235.     return 0;
  236. }
  237.  
Success #stdin #stdout 0s 5292KB
comments (?)
stdin 
Standard input is empty
stdout 
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/gfSygM
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!