#include<iostream>
using namespace std;

typedef int ElmenetType;
struct node {
    ElmenetType element;
    node* next;
    node* prev;
};
typedef node* Position;

class List {
private:
    node* head;
    node* tail;
    int counter;
public:
    List() {
        MakeNull();
    }

    void MakeNull() {
        head = NULL;
        tail = NULL;
        counter = 0;
    }

    Position END() {
        return tail;
    }

    Position First() {
        return head;
    }

    void InsertAtEnd(ElmenetType x) {
        Position newNode = new node;
        newNode->element = x;
        newNode->prev = tail;
        newNode->next = NULL;
        if (tail != NULL)
            tail->next = newNode;
        tail = newNode;
        if (head == NULL) head = tail;
        counter++;
    }

    void InsertAtStart(ElmenetType x) {
        Position newNode = new node;
        newNode->element = x;
        newNode->prev = NULL;
        newNode->next = head;
        if (head != NULL)
            head->prev = newNode;
        head = newNode;
        if (tail == NULL) tail = head;
        counter++;
    }

    void Insert(ElmenetType x, Position p = NULL) {
        if (p == NULL) {
            InsertAtEnd(x);
        }
        else if (p == head) {
            InsertAtStart(x);
        }
        else {
            Position newNode = new node;
            newNode->element = x;
            newNode->next = p;
            newNode->prev = p->prev;

            p->prev->next = newNode;
            p->prev = newNode;

            counter++;
        }
    }

    void Delete(Position p) {
        if (p == NULL) {
            cout << "No Element to be deleted";
            return;
        }
        if (p == tail) tail = p->prev;
        Position tmp = p;
        if (p->prev != NULL)
            p->prev->next = p->next;
        if (p->next != NULL)
            p->next->prev = p->prev;
        p->next = NULL;
        p->prev = NULL;
        delete tmp;

        counter--;
    }

    Position Locate(ElmenetType x) {
        Position p = head;
        while (p != NULL) {
            if (p->element == x)
                return p;
            p = p->next;
        }
        return p;
    }

    Position LocateInRange(ElmenetType x, Position pos, Position endPos) {
        Position p = pos;
        while (p != endPos->next) {
            if (p->element == x)
                return p;
            p = p->next;
        }
        return NULL;
    }

    ElmenetType Retrieve(Position pos) {
        if (pos == NULL) {
            cout << "ERROR in retrieve";
            return -1;
        }
        return pos->element;
    }

    void PrintList() {
        cout << "List is: ";
        Position p = head;
        while (p != NULL) {
            cout << p->element << " ";
            p = p->next;
        }
        cout << endl;
    }

    Position Next(Position pos) {
        if (pos == NULL) return NULL;
        return pos->next;
    }

    Position Previous(Position pos) {
        if (pos == NULL) return NULL;
        return pos->prev;
    }

    int Size() {
        return counter;
    }

    // Friend declarations for external functions
    friend void Purge(List& list);
    friend void Reverse(List& list);
};

// Purge function outside the class
void Purge(List& list) {
    Position p = list.First();
    while (p != NULL) {
        Position q = p->next;
        while (q != NULL) {
            if (q->element == p->element) {
                Position temp = q;
                q = q->next;
                if (temp->prev != NULL)
                    temp->prev->next = temp->next;
                if (temp->next != NULL)
                    temp->next->prev = temp->prev;
                delete temp;
                list.counter--;  // Update the counter after deletion
            } else {
                q = q->next;
            }
        }
        p = p->next;
    }
}

// Reverse function outside the class
void Reverse(List& list) {
    Position current = list.First();
    Position temp = NULL;

    // Reverse the list
    while (current != NULL) {
        temp = current->next;
        current->next = current->prev;
        current->prev = temp;
        current = temp;
    }

    // After reversal, update head and tail
    temp = list.First();
    list.head = list.END();
    list.tail = temp;
}

int main() {
    List l;

    l.InsertAtStart(1);
    l.InsertAtStart(2);
    l.InsertAtStart(3);
    l.InsertAtStart(4);
    l.Insert(10, l.END());
    l.Insert(-90, l.First());
    l.Insert(100, l.END());
    l.Insert(400, l.END());
    l.Insert(-200, l.First());
    l.Insert(534, NULL);
    l.PrintList();

    List ll;
    ll.InsertAtEnd(5);
    ll.InsertAtEnd(4);
    ll.InsertAtEnd(3);
    ll.InsertAtEnd(2);
    ll.PrintList();

    cout << "After purge: ";
    Purge(l);
    l.PrintList();

    cout << "After reverse: ";
    Reverse(l);
    l.PrintList();

    cout << "After purge: ";
    Purge(ll);
    ll.PrintList();

    cout << "After reverse: ";
    Reverse(ll);
    ll.PrintList();

    return 0;
}