Exercise :
Write a recursive algorithm to remove elements from a linked list.
Write a recursive algorithm to add elements into a linked list.
Try writing the same algorithms using iteration.
Do the recursive implementations or the iterative implementations feel more natural?
My question is what it actually means to add/remove elements recursively?
It means that user can just insert/remove a piece of data and only that data can be added or removed, or it means if the user inputs a x number then the list should add/remove x number of that specific data type?
My implementation as it stands works with inserting/removing a single piece of data of a specific type.
Code:
#include <iostream>
#include <iomanip>
#include <cstdlib>
template < typename T >
struct list
{
list();
void insert( T num );
void remove( T num );
void print();
private :
void print( list *l );
void insert( list *l, T num );
void remove( list *l, T num );
list *next;
list *head;
T id;
};
template < typename T >
list<T>::list() : next(), head(), id()
{ }
template < typename T >
void list<T>::insert( T num )
{
if( !head )
{
head = new list;
head->id = num;
head->next = NULL;
}
else
insert( head, num );
}
template < typename T >
void list<T>::insert( list *l, T num )
{
if( l->next )
{
insert( l->next, num );
}
else
{
l->next = new list;
l->next->id = num;
l->next->next = NULL;
}
}
template < typename T >
void list<T>::remove( T num )
{
if( !head )
return;
else
{
if( !head->next && head->id == num )
{
delete head;
head = NULL;
return;
}
remove( head, num );
}
}
template < typename T >
void list<T>::remove( list *l, T num )
{
if( !l->next && l->id != num )
{
return;
} //guard against invalid input
if( l->next->id == num )
{
list *dst = l->next;
list *nxt = dst->next;
l->next = nxt;
dst->next = NULL;
delete dst;
}
else
remove( l->next, num );
}
template < typename T >
void list<T>::print( )
{
system("cls");
std::cout<<"\n\n";
if( head )
{
std::cout<<std::setw(10)<<head->id;
if( head->next )
print( head->next );
}
else
std::cout<<std::setw(20)<<"List is empty";
std::cout<<"\n\n";
system("pause");
}
template < typename T >
void list<T>::print( list *l )
{
std::cout<<std::setw(10)<<l->id;
if( l->next )
print( l->next );
}
//methods can be called in main
int main()
{
list<short> *l = new list<short>();
/*
methods here
l->insert(1);
l->remove(1);
l->print();
*/
return 0;
}