#include <iostream>
using namespace std;

template <class T>
class Node
{
public:
  T value;     // e.g. int
  Node* next;  // pointer to the next element in the list
  Node* prev;
};


// insert element pointed to by p as the new head of the list
template <class T>
void
push_front( Node<T>* & head, Node<T>* p )
{
  if ( p == 0 ) {
    // this should not happen -- p should already point to a Node<T>
    // ERROR.....
  } else if ( head == 0 ) {
    p->next = p->prev = 0;
    head = p;
  } else {
    head->prev = p;
    p->next = head;
    p->prev = 0;
    head = p;
  }
}


// given list L, extract the sublist specified by iterators i and e
// -- assume i comes before e in the given list
// -- be sure to handle cases in which i is the first element of L
//    or e is the last element of L
// -- return a pointer to the head of the new sublist
// -- remove extracted nodes from old list L
template <class T>
Node<T>*
extract( Node<T>* & head, Node<T>* i, Node<T>* e )
{
  // e.g.  head->1->2->3->4->5->6->7
  //                ^        ^
  //                i        e
  //
  //       head->1->6->7
  //       sublist->2->3->4->5
  //
  if ( i == head && e->next == 0 ) {  // i---e is the entire list!
    head = 0;
  } else if ( i == head ) {
    head = e->next;
    head->prev = 0;
  } else if ( e->next == 0 ) {
    i->prev->next = 0;
  } else {
    i->prev->next = e->next;
    e->next->prev = i->prev;
  }

  i->prev = 0;
  e->next = 0;

  return i;
}

int main()
{
  Node<int>* head;

  for ( int j = 1 ; j <= 12 ; j++ ) {
    Node<int>* node = new Node<int>;
    node->value = j;
    node->next = node->prev = 0;
    if ( j == 1 ) { head = node; }
    else { push_front( head, node ); }
  }

  cout << "LIST:";
  for ( Node<int>* p = head ; p != 0 ; p = p->next ) {
    cout << ' ' << p->value;
  }
  cout << '\n';

  Node<int>* i;
  Node<int>* e;
  Node<int>* p = head;
  for ( int j = 1 ; j <= 12 ; j++, p = p->next ) {
    if ( j == 4 ) { i = p; }
    if ( j == 9 ) { e = p; }
  }

  Node<int>* sublist = extract( head, i, e );

  cout << "ORIGINAL LIST:";
  for ( Node<int>* p = head ; p != 0 ; p = p->next ) {
    cout << ' ' << p->value;
  }
  cout << '\n';

  cout << "SUBLIST:";
  for ( Node<int>* p = sublist ; p != 0 ; p = p->next ) {
    cout << ' ' << p->value;
  }
  cout << '\n';
}