C++ Linked List demo
Write a C++ program to create a double linked list. The operations associated with
the linked list are:
-Inserting item
-Deleting item
-Showing first and last items
-Showing all items
Solution
#include <iostream.h>
template <class Type> class List; // forward declaration
template <class Type>
class ListElem {
public:
ListElem (const Type elem){prev=next=0; val=elem;}
friend class List<Type>;//one-to-one friendship
protected:
Type val; // the element value
ListElem *prev; // previous element in the list
ListElem *next; // next element in the list
};
//------
template <class Type>
class List {
public:
List(void){first=last=0;}
~List(void);
void Insert (const Type&,int);
ListElem<Type> *getvalfirst();//return first item in the list
ListElem<Type> *getvallast();//return last item in the list
void Delete(int);//delete item from the list
void showfirst();//print out first item on the screen
void showlast();//print out last item on the screen
void getallval();//print out all items on the screen
int countitem();//return the number of items in the list
protected:
ListElem<Type> *first; // first element in the list
ListElem<Type> *last; // last element in the list
};
//destructor
template <class Type>
List<Type>::~List (void)
{
ListElem<Type> *item;
ListElem<Type> *next;
for(item =first; item!= 0; item= next){
next = item->next;
delete item;
}
}
//insert item
template <class Type>
void List<Type>::Insert (const Type &elem,int pos)
{
ListElem<Type> *item = new ListElem<Type>(elem);
//empty list
if(first==0 & last==0){
first=item;
last=item;
}
//insert new item at the beginning of the list
else if(pos==1)
{
ListElem<Type> *f;
f=first;
first=item;
first->next=f;
f->prev=first;
}
//insert new item between items
else if(pos>1 & pos<=countitem()){
ListElem<Type> *ta;
ta=first;
for(int t=1;t<pos;t=t+1){ta=ta->next;}
item->next=ta;
item->prev=ta->prev;
ta->prev->next=item;
ta->prev=item;
}
//insert new item at the end of the list
else if(pos==countitem()+1){
ListElem<Type> *t;
ListElem<Type> *x;
t=getvallast();
x=t;
t=item;
x->next=t;
t->prev=x;
last=t;
}
//show message if position is not valid
else cout<"Invalid position! Position must be between 1 and "<countitem()+2<"\n";
}
//Print out all items on the screen
template <class Type>
void List<Type>::getallval()
{
if(countitem()>0){
ListElem<Type> *i;
for(i=first;i!=0;i=i->next){
cout<"\n"<i->val;
}
}
else cout<"\nNo item found";
}
template <class Type>
int List<Type>::countitem()
{
ListElem<Type> *i;
int t=0;
for(i=first;i!=0;i=i->next){
t=t+1;
}
return t;
}
template <class Type>
ListElem<Type> *List<Type>::getvalfirst()
{ return first;
}
template <class Type>
void List<Type>::showfirst()
{
if(countitem()>0){
ListElem<Type> *f;
f=getvalfirst();
cout<"Lirst value:"<f->val<"\n";
}
else cout<"\n No item found\n";
}
template <class Type>
ListElem<Type> *List<Type>::getvallast()
{ListElem<Type> *i;
i=first;
for(int t=1;t<countitem();t=t+1){i=i->next;}
last=i;
return last;
}
template <class Type>
void List<Type>::showlast()
{
if(countitem()>0){
ListElem<Type> *l;
l=getvallast();
cout<"Last value:"<l->val<"\n";
}
else cout<"\n No item found\n";
}
template <class Type>
void List<Type>::Delete(int pos){
if(countitem()>0){
ListElem<Type> *temp;
if(pos==countitem()){
temp=last;
last=last->prev;
last->next=0;
delete temp;
}
else if(pos==1){
temp=first;
first=first->next;
first->prev=0;
delete temp;
}
else if(pos>1 & pos<countitem()){
temp=first;
for(int i=1;i<pos;i=i+1){temp=temp->next;}
temp->prev->next=temp->next;
temp->next=temp->prev;
delete temp;
}
else cout<"\nInvalid position!\n";
}
else cout<"\n No item found";
}
void main(){
List<int> mylist;
mylist.Insert(30,1);
mylist.Insert(20,1);
mylist.Insert(24,1);
mylist.Insert(25,2);
mylist.Insert(200,3);
mylist.Insert(205,4);
mylist.Delete(6);
mylist.Delete(3);
mylist.showfirst();cout<"\n";
mylist.showlast();cout<"\n";
cout<"\nNumber of Items:"<mylist.countitem()<"\n";
cout<"All items:\n";
mylist.getallval();
}