fork download 
  1. #include<iostream>
  2. using namespace std;
  3.  
  4. typedef int ElementType;
  5.  
  6. struct node {
  7.     ElementType element;
  8.     node* next;
  9.     node* prev;
  10. };
  11.  
  12. typedef node* Position;
  13.  
  14. class List {
  15.     node* head;
  16.     node* tail;
  17.     int counter;
  18.  
  19. public:
  20.     List() {
  21.         MakeNull();
  22.     }
  23.  
  24.     void MakeNull() {
  25.         head = new node;
  26.         head->next = nullptr;
  27.         head->prev = nullptr;
  28.         tail = head;
  29.         counter = 0;
  30.     }
  31.  
  32.     Position End() {
  33.         return tail;
  34.     }
  35.  
  36.     void Insert(ElementType x, Position pos) {
  37.         if (pos == nullptr) pos = tail;
  38.  
  39.         node* t = new node;
  40.         t->element = x;
  41.         t->next = pos->next;
  42.         t->prev = pos;
  43.  
  44.         if (pos->next != nullptr)
  45.             pos->next->prev = t;
  46.         else
  47.             tail = t;
  48.  
  49.         pos->next = t;
  50.         counter++;
  51.     }
  52.  
  53.     void Insertback(ElementType x) {
  54.         Insert(x, tail);
  55.     }
  56.  
  57.     void Delete(Position p) {
  58.         if (p == nullptr || p == head) {
  59.             cout << "Invalid position to delete\n";
  60.             return;
  61.         }
  62.  
  63.         if (p->next != nullptr)
  64.             p->next->prev = p->prev;
  65.         else
  66.             tail = p->prev;
  67.  
  68.         p->prev->next = p->next;
  69.  
  70.         delete p;
  71.         counter--;
  72.     }
  73.  
  74.     void PrintList() {
  75.         cout << "List is: ";
  76.         Position q = head->next;
  77.         while (q != nullptr) {
  78.             cout << q->element << " ";
  79.             q = q->next;
  80.         }
  81.         cout << endl;
  82.     }
  83.  
  84.     Position Locate(ElementType x) {
  85.         Position p = head->next;
  86.         while (p != nullptr) {
  87.             if (p->element == x)
  88.                 return p;
  89.             p = p->next;
  90.         }
  91.         return nullptr;
  92.     }
  93.  
  94.     ElementType Retrieve(Position pos) {
  95.         if (pos == nullptr || pos == head) {
  96.             cout << "ERROR in retrieve\n";
  97.             return -1;
  98.         }
  99.         return pos->element;
  100.     }
  101.  
  102.     Position First() {
  103.         return head;
  104.     }
  105.  
  106.     Position Next(Position pos) {
  107.         return (pos != nullptr) ? pos->next : nullptr;
  108.     }
  109.  
  110.     Position Previous(Position pos) {
  111.         return (pos != nullptr && pos != head) ? pos->prev : nullptr;
  112.     }
  113.  
  114.     int Size() {
  115.         return counter;
  116.     }
  117.  
  118.     friend void Reverse(List& l);
  119.     friend void Purge(List& l);
  120. };
  121.  
  122. void Purge(List& l) {
  123.     Position p = l.First()->next;
  124.     while (p != nullptr) {
  125.         Position q = p->next;
  126.         while (q != nullptr) {
  127.             Position next = q->next;
  128.             if (p->element == q->element)
  129.                 l.Delete(q);
  130.             q = next;
  131.         }
  132.         p = p->next;
  133.     }
  134. }
  135.  
  136. void Reverse(List& l) {
  137.     Position current = l.head->next;
  138.     Position prevNode = nullptr;
  139.  
  140.     // Update tail to the old first element
  141.     l.tail = current;
  142.  
  143.     while (current != nullptr) {
  144.         Position temp = current->next;
  145.         current->next = current->prev;
  146.         current->prev = temp;
  147.  
  148.         prevNode = current;
  149.         current = temp;
  150.     }
  151.  
  152.     // Update head->next to point to new front node
  153.     if (prevNode != nullptr) {
  154.         l.head->next = prevNode;
  155.         prevNode->prev = l.head;
  156.     }
  157.  
  158.     // Update tail's next to nullptr
  159.     if (l.tail != nullptr) {
  160.         l.tail->next = nullptr;
  161.     }
  162. }
  163.  
  164. int main() {
  165.     List l;
  166.     l.Insertback(10);
  167.     l.Insertback(20);
  168.     l.Insertback(30);
  169.     l.Insertback(20); // duplicate
  170.     l.Insertback(60);
  171.     l.Insertback(2);
  172.  
  173.     l.PrintList();
  174.  
  175.     cout << "Size: " << l.Size() << endl;
  176.  
  177.     Purge(l);
  178.     cout << "After Purge:\n";
  179.     l.PrintList();
  180.  
  181.     Reverse(l);
  182.     cout << "After Reverse:\n";
  183.     l.PrintList();
  184.  
  185.     return 0;
  186. }
Success #stdin #stdout 0.01s 5288KB
comments (?)
stdin 
Standard input is empty
stdout 
List is: 10 20 30 20 60 2 
Size: 6
After Purge:
List is: 10 20 30 60 2 
After Reverse:
List is: 2 60 30 20 10
https://ideone.com/hiwXHj
language:
C++ 4.3.2 (gcc-4.3.2)
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!