template <typename T>
class List;

template <typename T>
ostream &operator<<( ostream &, const List<T> & );

template <typename T>
class List {

  friend ostream &operator<< <>( ostream &, const List<T> & );

  public:
    List();
    List( const List<T> & ); /* throws bad_alloc */
    ~List();
    void add( unsigned, const T & ); /* throws bad_alloc and out_of_range */
    void addAll( const List<T> & ); /* throws bad_alloc */
    void addAll( unsigned, const List<T> & ); /* throws bad_alloc, out_of_range */
    void addFirst( const T & ); /* throws bad_alloc */
    void addLast( const T & ); /* throws bad_alloc */
    void clear();
    bool contains( const T & ) const;
    bool empty() const;
    int indexOf( const T & ) const;
    T &get( unsigned ) const; /* throws out_of_range */
    T &getFirst() const; /* throws NoSuchObject */
    T &getLast() const; /* throws NoSuchObject */
    ListIterator<T> listIterator();
    ListIterator<T> listIterator( unsigned ); /* throws out_of_range */
    T remove( unsigned ); /* throws out_of_range */
    T removeFirst(); /* throws NoSuchObject */
    T removeFirstOccurrence( const T & ); /* throws NoSuchObject */
    T removeLast(); /* throws NoSuchObject */
    T removeLastOccurrence( const T & ); /* throws NoSuchObject */
    T set( unsigned, const T & ); /* throws out_of_range */
    unsigned size() const;
    T *toArray() const; /* throws bad_alloc */
    const List<T> &operator=( const List<T> & ); /* throws bad_alloc */
    void printInternal( ostream & = cout ) const;

  private:
    Node<T> *frontPtr, *backPtr;
    unsigned sz;

    void add( Node<T> *, const T & ); /* throws bad_alloc */
    void initialize();
    Node<T> *getIthNode( unsigned ) const; /* throws out_of_range */
    T remove( Node<T> * );

}; // List class