#ifndef LLIST_H
#define LLIST_H
/**
* Node structure for linked list
*/
template <class T>
struct node
{
T info;
node<T> *next;
};
/**
* Linked list class
*/
template <class T>
class LList
{
private:
// Pointer to first node
node<T> *first;
int length;
public:
//Constructor
LList();
// Destructor
~LList();
//Copy constructor
LList ( const LList<T> & other);
//Overload the assignment operator
const LList<T> & operator= (const LList<T> & other);
//Returns current length of list
int getLength();
// Returns true if list is empty, false otherwise
bool isEmpty();
// Inserts parameter item
void insertItem(T item);
//If list is not empty and parameter item is in the list,
//removes item from the list and decrements length.
//If list is empty or item is not in the list, prints error
void deleteItem(T item);
//Returns true if parameter item is in the list, false otherwise
bool searchItem(T item);
//Print all items in the list. Print message if list is empty.
void printList();
// function to copy a list
void copy (const LList<T> & other);
// Destroy list function
void destroy();
};
#endif
LList.cpp
#include "LList.h"
#include <iostream>
using namespace std;
/**
* Constructor
*/
template <class T>
LList<T> :: LList()
{
length = 0;
first = NULL;
}
/**
* Destructor
*/
template <class T>
LList<T> :: ~LList()
{
destroy();
}
/**
* Copy constructor
*/
template <class T>
LList<T> :: LList ( const LList<T> & other)
{
copy (other);
}
/**
* Overload the assignment operator
* @tparam T
* @param other
* @return LList<T>
*/
template <class T>
const LList<T> & LList<T> :: operator= (const LList<T> & other)
{
if ( this != &other )
{
destroy ();
copy (other);
}
return *this;
}
/**
* Returns true if list is empty, false otherwise
*/
template <class T>
bool LList<T> :: isEmpty()
{
return first == NULL;
}
/**
* Inserts parameter item into the list in ascending order
*/
template <class T>
void LList<T> :: insertItem(T item)
{
length++;
node<T> * p = new node<T>;
p->info = item;
if ( first == NULL || item < first-> info )
{
p->next = first;
first = p;
}
else
{
node<T> *r = NULL;
node<T> *q = first;
while ( q!= NULL && item > q->info )
{
r = q;
q = q->next;
}
p->next = q;
r->next = p;
}
}
/**
* If list is not empty and parameter item is in the list,
* removes item from the list and decrements length.
* If list is empty or item is not in the list, prints error
*/
template <class T>
void LList<T> :: deleteItem(T item)
{
if ( first == NULL || item < first->info )
cout<<"\nLIST EMPTY OR ITEM NOT IN THE LIST\n";
else
{
node<T> *p = first;
// item is contained in the first node
if ( item == first->info )
{
first = first->next;
delete p;
length--;
}
// item is contained in some other node
else
{
node<T> *q = p;
p = p->next;
while ( p != NULL && item > p->info )
{
q = p;
p = p->next;
}
if ( p == NULL || item < p->info )
cout<<"\nITEM NOT IN THE LIST\n";
else
{
q->next = p->next;
delete p;
length--;
}
}
}
}
/**
* Destroy the list
*/
template <class T>
void LList<T> :: destroy()
{
node<T> *p;
while ( first != NULL )
{
p = first;
first = first->next;
delete p;
}
length = 0;
}
/**
* function to copy a list
*/
template <class T>
void LList<T> :: copy ( const LList<T> & other )
{
length = other.length;
if ( other.first == NULL )
first = NULL;
else
{
first = new node<T>;
first->info = other.first->info;
node<T> *p = other.first->next;
node<T> *q = first;
while ( p != NULL )
{
q->next = new node<T>;
q = q->next;
q->info = p->info;
p = p->next;
}
q->next = NULL;
}
}
/**
* Returns current length of list
*/
template <class T>
int LList<T> :: getLength()
{
return length;
}
/**
* Returns true if parameter item is in the list, false otherwise
*/
template <class T>
bool LList<T> :: searchItem(T item)
{
node<T> *p = first;
while ( p != NULL && p->info <= item )
{
if ( p->info == item )
return true;
p = p->next;
}
return false;
}
/**
* Print all items in the list. Print message if list is empty.
*/
template <class T>
void LList<T> :: printList()
{
if ( first == NULL)
cout<<"\nEMPTY LIST\n";
else
{
cout<<"\nLIST: ";
node<T> *p = first;
while ( p != NULL)
{
cout<<p->info<<" ";
p = p->next;
}
}
}
main.cpp
#include "LList.cpp"
using namespace std;
//******************** function prototypes ********************//
int printMenu();
void insertListItem ( LList<int> & );
void deleteListItem ( LList<int> & );
void searchListItem ( LList<int> );
//******************** main function ********************//
int main()
{
// Create an empty list of integers
LList<int> l;
int choice;
cout <<"\nOperations allowed on the unsorted list of integers are below."
<<"\nPlease enter the number of your choice and press return.\n\n";
choice = printMenu();
while ( choice != 6 )
{
switch ( choice )
{
case 1 : insertListItem( l );
break;
case 2 : deleteListItem ( l );
break;
case 3 : l.printList();
break;
case 4 : searchListItem ( l );
break;
case 5 : cout<<"\nThe list contains "<<l.getLength()
<< " items\n\n";
break;
default :cout<<"\nNumber is not correct. Please look at "
<<"choices and reenter\n\n";
break;
}
choice = printMenu();
}
LList<int> l2;
l2 = l;
cout<<"\nPrinting a new list with the same values as the old list \n";
l2.printList();
cout<<"\nProgram terminated\n\n";
return 0;
}
//******************** functions implementation ********************//
/**
* Prints the menu and returns the user's choice
*/
int printMenu ()
{
int c;
cout<<"\n1: Add an item to the list.";
cout<<"\n2: Delete an item from the list.";
cout<<"\n3: Print the list.";
cout<<"\n4: Search the list for a given item";
cout<<"\n5: Return the number of items in the list";
cout<<"\n6: Quit.\n\n";
cin>>c;
return c;
}
/**
* Inserts a number into the list
*/
void insertListItem ( LList<int> &l )
{
int num;
cout<<"\nEnter the number to insert : ";
cin>>num;
l.insertItem(num);
cout<<"\nThe number has been inserted\n\n";
}
/**
* Deletes a number from the list
*/
void deleteListItem ( LList<int> &l )
{
int num;
cout<<"\nEnter the number to delete : ";
cin>>num;
if ( l.searchItem (num))
{
l.deleteItem (num);
cout<<"\nThe number has been deleted\n\n";
}
else cout<<"\nThe number is NOT in the list\n\n";
}
/**
* Searches for a number in the list
*/
void searchListItem ( LList<int> l )
{
int num;
cout<<"\nEnter the number to search for : ";
cin>>num;
if ( l.searchItem (num))
cout<<"\nThe number is in the list\n\n";
else cout<<"\nThe number is NOT in the list\n\n";
}
Compile and Run
$ g++ -std=c++11 LList.cpp main.cpp -o LinkedListDemo
$ ./LinkedListDemo
Operations allowed on the unsorted list of integers are below.
Please enter the number of your choice and press return.
1: Add an item to the list.
2: Delete an item from the list.
3: Print the list.
4: Search the list for a given item
5: Return the number of items in the list
6: Quit.
1
Enter the number to insert : 20
The number has been inserted
1: Add an item to the list.
2: Delete an item from the list.
3: Print the list.
4: Search the list for a given item
5: Return the number of items in the list
6: Quit.
1
Enter the number to insert : 10
The number has been inserted
1: Add an item to the list.
2: Delete an item from the list.
3: Print the list.
4: Search the list for a given item
5: Return the number of items in the list
6: Quit.
3
LIST: 10 20
...
LList.h
LList.cpp
main.cpp
Compile and Run