A doubly-linked list is a collection of nodes, each of which has a
pointer to the node before and after it (as opposed to a singly linked
list, where each node only has a pointer to its successor).  We may
model nodes as a simple class:

class node {
public:
  int val;
  class node *next;
  class node *prev;
};

Now, the declaration for a doubly linked list class could be:

class DoublyLinkedList {
public:
   DoublyLinkedList();                            // creates empty list
   DoublyLinkedList(const DoublyLinkedList &);    // copy constructor
   ~DoublyLinkedList();                           // destructor

   void insertAtFront(int v);
   int removeFromFront();

   void insertAtRear(int v);
   int removeFromRear();

   void insertAfter(node *n, int v);      // inserts new node after node n
   void insertBefore(node *n, int v);     // inserts new node before node n

   voide removeNode(node *n);             // removes a node

   int getLength( ) const;

   node *first;       // first item in the list
   node *last;        // last item in the list
   int   length;      // current length of the list
};

Give an implementation of each of the methods in the definition.  Each
of the basic operations (insertion, deletion and obtaining the length)
should run in an amount of time independent of the number of items in
the list.