template <class T>
struct ListNode{
T item;
ListNode * next;
};
template <class T>
class LinkedList: public List<T> {
private:
ListNode<T>* head;
int count;
public:
LinkedList();
~LinkedList();
virtualbool isEmpty ();
virtualint getLength ();
virtualvoid insert (int pos,T item);
virtual T remove (int pos);
virtual T retrieve (int pos);
};
//constructor
template <class T>
LinkedList<T>::LinkedList(){
head= NULL;
count =0;
}
// isempty
template <class T>
bool LinkedList<T>::isEmpty (){
if (head == NULL){
returnfalse;
}
returntrue;
}
template<class T>
int LinkedList<T>::getLength(){
return count;
}
template <class T>
T LinkedList<T>::retrieve(int pos){
ListNode<T>* temp;
if (isEmpty()){
throw -1;
}
if (pos > count){
throw -1;
}
for (int i=0; i<pos ; i++) {
temp= temp->next;
}
return temp->item;
}
//Removes a node from the position
//probably should do an exception what if the pos was not random but given by user
// if given by user or random probably best to do exception
template <class T>
T LinkedList<T>::remove (int pos){
ListNode<T>* temp;
if (isEmpty()){
throw -1;
}
if (pos>count){
throw -1;
}
for (int i=0; i<pos ; i++) {
temp= temp->next;
}
ListNode<T>* holder= temp->next;
temp->next = holder->next;
count--;
return holder-> item;
}
//inserts a T item into the random pos
template <class T>
void LinkedList<T>::insert(int pos,T item){
ListNode<T> * temp=head;
for (int i=1; i<pos ; i++) {
temp= temp->next;
}
ListNode<T> * temp2= new ListNode<T>;
temp2->item=item;
temp2= temp-> next;
temp-> next=temp2;
count++;
}
template <class T>
LinkedList<T>::~LinkedList(){
ListNode<T>* temp= head;
ListNode<T>* a;
while (isEmpty()==false){
a=temp;
temp = temp->next;
delete temp;
}
}