// File: LinkList.h
// Definitions for Linked List ADT
// The linked list contains a dummy header node that is initialized to
//	hold a value that will always come first


#ifndef LINK_LIST_H
#define LINK_LIST_H

#include <iostream>
#include <vector>

using namespace std;

template <class listEltType>
class List {

public:

 typedef vector<listEltType>::iterator listIterator;

 // Constructor...Initialize List to NULL
 // Pre:
 List();

// No destructor or copy constructor need be explicitly implemented
// There are no pointers in this implementation, so defaults are fine

 // Pre:  None
 // Post: List is empty
 void init();

 // Pre:  Argument contains element of the proper type 
 // Post: List contains at least one element (not necessarily ordered)
 void insertAtHead(const listEltType &);

 // Pre:  List is ordered
 // Post: List is ordered, containing one additional element
 void insertInOrder(const listEltType &);

 // Pre:  List contains at least one element
 // Post: List contains one less element
 void removeHead();

 // Pre:  List is ordered, item is found in list
 // Post: List is ordered, containing one additional element
 void deleteInOrder(const listEltType &);

 // Pre:  None
 // Post: Boolean value returned
 bool search(const listEltType&);

 // Retrieve a listEltType reference using an int key
 listEltType &retrieve(const int &);

 // Pre:  None
 // Post: Value returned is number of elements in list
 int countNodes();

 friend ostream &operator<<(ostream &,List);

 vector<listEltType> theList;

};

#endif