#include <iostream>
using namespace std;
typedef int Object;

struct DNode {
    DNode(Object e) {
    	data = e;
    	next = previous = NULL;
    }
    Object data;
    DNode *next, *previous;
};

class DoubleLinkedList {
	 public:
	           DoubleLinkedList (void);
	          ~DoubleLinkedList (void);
        int    size             (void);
        bool   isEmpty          (void);
        void   addFirst         (Object e);
        void   addLast          (Object e);
        void   add              (int index, Object e);
        Object getFirst         (void);
        Object getLast          (void);
        Object remove           (Object e);
        void   print            ();
        void   clear            (void);
        void evenodd             ();
         private:
        DNode *head, *tail;
        int   count;
};
DoubleLinkedList::DoubleLinkedList() {
    head = tail = NULL;
    count = 0;
}

DoubleLinkedList::~DoubleLinkedList() {
    clear();
}

int DoubleLinkedList::size() {
	return count;
}

bool DoubleLinkedList::isEmpty() {
	return (count == 0);
}

void DoubleLinkedList::addFirst(Object e) {
	DNode *node = new DNode(e);

	if (tail == NULL)
		head = tail = node;
	else {
		node->next = head;
		head->previous = node;
		head = node;
	}
	count++;
}
void DoubleLinkedList::addLast(Object e) {
	DNode *node = new DNode(e);

	if (tail == NULL)
		head = tail = node;
	else {
		tail->next = node;
		node->previous = tail;
		tail = node;
	}
	count++;
}

void DoubleLinkedList::add(int index, Object e) {
	if (index < 0 || index > count)
		return;

	if (index == 0) {
		addFirst(e);
	} else if (index == count)
		addLast(e);
	else {
		DNode *node = new DNode(e);
		DNode *temp = head;

		for (int i = 1; i < index; i++)
			temp = temp->next;

		node->next = temp->next;
		node->previous = temp;
		temp->next = node;
		node->next->previous = node;

		count++;
	}

}

Object DoubleLinkedList::getFirst() {
	if (isEmpty())
		return 0;

	return head->data;
}

Object DoubleLinkedList::getLast() {
	if (isEmpty())
		return 0;

	return tail->data;
}




void DoubleLinkedList::evenodd()
{
    DNode *tail = head;
 
    DNode *prev = NULL;
    DNode *temp = head;
 
  
    while (tail->next != NULL)
        tail = tail->next;
 
    DNode *new_tail = tail;
 
    
    while (temp->data %2 != 0 && temp != tail)
    {
        new_tail->next = temp;
        temp = temp->next;
        new_tail->next->next = NULL;
        new_tail = new_tail->next;
    }
 
    
    if (temp->data%2 == 0)
    {
        
        head = temp;
 
        
        while (temp != tail)
        {
            if ( (temp->data)%2 == 0 )
            {
                prev = temp;
                temp = temp->next;
            }
            else
            {
                
                prev->next = temp->next;
 
                
                temp->next = NULL;
 
                
                new_tail->next = temp;
 
                
                new_tail = temp;
 
            
                temp= prev->next;
            }
        }
    }
 
    
    else prev =temp;
 
    
    if (new_tail!=tail && (tail->data)%2 != 0)
    {
        prev->next = tail->next;
        tail->next = NULL;
        new_tail->next = tail;
    }
    return;
}


void DoubleLinkedList::print() {
	cout << "Nodes : (";
	
	if (isEmpty())
		cout << ").";
    else {
	    DNode *temp = head;
	    while (temp != tail) {
	    	cout << temp->data << ", ";
	    	temp = temp->next;
	    }
	    cout << temp->data << ")." << endl;
	}
}

void DoubleLinkedList::clear() {
	DNode *temp;
	while (head != NULL) {
		temp = head;
		head = head->next;
		head->previous = NULL;
		temp->next = NULL;                    
	}
	tail = NULL;
	count = 0;
}
int main()
{
	 DoubleLinkedList list;
	 list.add(0, 2); cout << list.size() << " : "; list.print();
	
	list.add(1, 4); cout << list.size() << " : "; list.print();
	list.add(2, 7); cout << list.size() << " : "; list.print();
	list.add(3, 8); cout << list.size() << " : "; list.print();
	list.add(4, 5); cout << list.size() << " : "; list.print();
    list.evenodd();cout<<list.size() <<" : ";list.print();
}