السؤال
Part A (3 points)
1. Create a new project in which you add the two header files: “linkedList.h” and “linkedListImplement.h” (provided in blackboard).
2. Add a new .cpp file named assignment3 to your project.
3. In the file assignment3-02 include the header file “linkedListImplement.h”.
4. Declare three linkedListType objects named list1 and list2 to handle integer items.
5. Insert the following items in list1: 11,9, 7, 20, 3, and 6.
6. Print the elements of list1.
Part B (4 points)
7. Add a member function
replaceAt to the class linkedListType to replace the data value in node index
position, passed as a parameter, by another parameter
newItem. The index of the first node is 0 and increases by 1 for each subsequent node. If the list is
empty or the index is invalid then return false, else return true.
Add the function prototype to the header file linkedList.h and implement it in the header file linkedListImplement.h:
bool replaceAt(int position, const Type& newItem);
a. Call the function replaceAt to replace the element at position 0 of list2 by 100.
b. Call the function replaceAt to replace the element at position -1 of list1 by 100.
c. Call the function replaceAt to replace the element at position 2 of list1 by 100.
d. Print the elements of list1.
Part C (3 points)
8. Add a member function
insertAt to the class linkedListType to insert a data value
newItem at index
position. Index
position and data value
newItem are passed as parameters to the function
. The index of the first node is 0 and increases by 1 for each subsequent node. If the index is invalid (less than zero or greater than count) then the function does not insert
newItem and returns
false. Else, insert the new item at the given position and returns
true after insertion (treat the special cases where index = zero or index = count).
Add the function prototype to the header file linkedList.h and implement it in the header file linkedListImplement.h:
bool insertAt(int position, const Type& newItem);
Example:
Before insertion
list: 5 10 20 15 22 33
position: 2 newItem: 30
After insertion
list: 5 10 30 20 15 22 33
a. Call the function insertAt with the two parameters -2 and 6 for list1.
b. Call the function insertAt with the two parameters 7 and -1 for list1.
c. Call the function insertAt with the two parameters 6 and 200 for list1.
d. Call the function insertAt with the two parameters 0 and -1 for list2.
e. Display list1 and list2.
الجواب ممكن أحد يشوف لي وش الايرور؟؟
PHP:
#include<iostream>
using namespace std;
template<class Type>
struct nodeType
{
Type info;
nodeType<Type> *link;
};
template<class Type>
class linkedListType
{
public:
const linkedListType<Type>& operator=(const linkedListType<Type>&);
void initializeList();
bool isEmpty();
int length();
void destroyList();
Type front();
Type back();
bool search(const Type& searchItem);
void insertFirst(const Type& newItem);
void insertLast(const Type& newItem);
void deleteNode(const Type& deleteItem);
linkedListType();
linkedListType(const linkedListType<Type>& otherList);
~linkedListType();
bool print() ;
bool replaceAt(int position, const Type& newItem);
bool insertAt(int position ,const Type &Item) ;
bool retrieveAt(int pos,Type & item) ;
void insertArray(const Type array[],int size) ;
//protected:
int count;
nodeType<Type> *first;
nodeType<Type> *last;
private:
void copyList(const linkedListType<Type>& otherList);
};
template<class Type>
ostream& operator<<(ostream&, const linkedListType<Type>&);
#include"linkedList.h"
#include<cassert>
template<class Type>
ostream& operator<<(ostream& osObject, const linkedListType<Type>& list)
{
nodeType<Type> *current; // pointer to traverse the list
current = list.first;
while(current != NULL)
{
osObject<<current->info<<" ";
current = current->link;
}
return osObject;
}
template<class Type>
const linkedListType<Type>& linkedListType<Type>::operator=(const linkedListType<Type>& otherList)
{
if(this != &otherList) //avoid self-copy
copyList(otherList);
return *this;
}
template<class Type>
void linkedListType<Type>::initializeList()
{
destroyList();
}
template<class Type>
bool linkedListType<Type>::isEmpty()
{
return(first == NULL);
}
template<class Type>
int linkedListType<Type>::length()
{
return count;
}
template<class Type>
void linkedListType<Type>::destroyList()
{
nodeType<Type> *temp;
while(first != NULL)
{
temp = first;
first = first->link;
delete temp;
}
last = NULL;
count = 0;
}
template<class Type>
Type linkedListType<Type>::front()
{
assert(last != NULL);
return first->info;
}
template<class Type>
Type linkedListType<Type>::back()
{
assert(last != NULL);
return last->info;
}
template<class Type>
bool linkedListType<Type>::search(const Type& searchItem)
{
nodeType<Type> *current;
bool found;
current = first;
found = false;
while(current != NULL && !found)
if(current->info == searchItem)
found = true;
else
current = current->link;
return found;
}
template<class Type>
void linkedListType<Type>::insertFirst(const Type& newItem)
{
nodeType<Type> *newNode;
newNode = new nodeType<Type>;
assert(newNode != NULL);
newNode->info = newItem;
newNode->link = first;
first = newNode;
count++;
if(last == NULL)
last = newNode;
}
template<class Type>
void linkedListType<Type>::insertLast(const Type& newItem)
{
nodeType<Type> *newNode;
newNode = new nodeType<Type>;
assert(newNode != NULL);
newNode->info = newItem;
newNode->link = NULL;
if(first == NULL)
{
first = newNode;
last = newNode;
}
else
{
last->link = newNode;
last = newNode;
}
count++;
}
template<class Type>
void linkedListType<Type>::deleteNode(const Type& deleteItem)
{
nodeType<Type> *current; // pointer to traverse the list
nodeType<Type> *trailCurrent; //pointer just before current
bool found;
if(first == NULL)
cout<<"Cannot delete from an empty list."<<endl;
else
{
if(first->info == deleteItem)
{
current = first;
first = first->link;
count--;
if(first == NULL) // list has only one node
last = NULL;
delete current;
}
else // search the list for the node with the given info
{
found = false;
trailCurrent = first;
current = first->link;
while(current != NULL && !found)
{
if(current->info != deleteItem)
{
trailCurrent = current;
current = current->link;
}
else
found = true;
}
if(found)
{
trailCurrent->link = current->link;
count--;
if(last == current) //node to be deleted is the last node
last = trailCurrent;
delete current;
}
else
cout<<"Item to be deleted is not in the list."<<endl;
}
}
}
template<class Type>
linkedListType<Type>::linkedListType()
{
first = NULL;
last = NULL;
count = 0;
}
template<class Type>
linkedListType<Type>::linkedListType(const linkedListType<Type>& otherList)
{
first = NULL;
copyList(otherList);
}
template<class Type>
linkedListType<Type>::~linkedListType()
{
destroyList();
}
template<class Type>
void linkedListType<Type>::copyList(const linkedListType<Type>& otherList)
{
nodeType<Type> *newNode; //pointer to create a node
nodeType<Type> *current; //pointer to traverse the list
if(first != NULL)
destroyList();
if(otherList.first == NULL) //otherList is empty
{
first = NULL;
last = NULL;
count = 0;
}
else
{
current = otherList.first; //current points to the lis to be copied
count = otherList.count;
first = new nodeType<Type>; //create the node
assert(first != NULL);
first->info = current->info; //copy the info
first->link = NULL; //set the link field of the node to NULL
last = first; //make last point to the first node
current = current->link; //make current point to the next node
while(current != NULL) //copy the remaining list
{
newNode = new nodeType<Type>; //create a node
assert(newNode != NULL);
newNode->info = current->info; //copy the info
newNode->link = NULL; //set the link of newNode to NULL
last->link = newNode; //attach newNode after last
last = newNode; //make last point to the actual last node
current = current->link; //make current point to the next node
}
}
}
template<class Type>
bool linkedListType<Type>::print()
{
nodeType<Type> *current;
if(first == NULL)
{
cout<<"Cannot retrieve in an empty list."<<endl<<endl;
return false;
}
else
{
current = first;
for(int i=0; i<count; i++)
{ cout << " " << current->info << " ";
current = current->link;
}
return true;
}
}
template<class Type>
bool linkedListType<Type>::replaceAt(int position, const Type& newItem)
{
nodeType<Type> *current;
if(first == NULL)
{
cout<<"\n Cannot replace in an empty list."<<endl<<endl;
return false;
}
else if(position < 0 || position > count)
{
cout<<"\n Invalid position."<<endl<<endl;
return false;
}
else
{
current = first;
for(int i=0; i<position; i++)
current = current->link;
current->info = newItem;
return true;
}
}
template <class Type>
bool linkedListType<Type>::insertAt(int position ,const Type &Item)
{
if(position < 0 || position > count )
{
cerr << "\n Invalid Position \n" << endl;
return false ;
}
nodeType <Type> *current , *newNode ;
newNode = new nodeType <Type>;
assert (newNode != NULL);
newNode -> info = Item ;
newNode -> link = NULL ;
if ( first == NULL)
{
first = newNode ;
last = newNode;
count++;
return true ;
}
else if ( position == 0 )
{
newNode -> link = first ;
first = newNode ;
count++;
return true;
}
else if ( position == count )
{
last->link = newNode ;
last = newNode;
count++;
return true ;
}
current = first ;
for (int i = 0 ; i <position-1 ; ++i)
current = current -> link ;
}
#include <iostream>
#include <cassert>
using namespace std;
template<class Type>
ostream& operator<<(ostream& osObject, const linkedListType<Type>& list)
{
nodeType<Type> *current; // pointer to traverse the list
current = list.first;
while(current != NULL)
{
osObject<<current->info<<" ";
current = current->link;
}
return osObject;
}
template<class Type>
const linkedListType<Type>& linkedListType<Type>::operator=(const linkedListType<Type>& otherList)
{
if(this != &otherList) //avoid self-copy
copyList(otherList);
return *this;
}
template<class Type>
void linkedListType<Type>::initializeList()
{
destroyList();
}
template<class Type>
bool linkedListType<Type>::isEmpty()
{
return(first == NULL);
}
template<class Type>
int linkedListType<Type>::length()
{
return count;
}
template<class Type>
void linkedListType<Type>::destroyList()
{
nodeType<Type> *temp;
while(first != NULL)
{
temp = first;
first = first->link;
delete temp;
}
last = NULL;
count = 0;
}
template<class Type>
Type linkedListType<Type>::front()
{
assert(last != NULL);
return first->info;
}
template<class Type>
Type linkedListType<Type>::back()
{
assert(last != NULL);
return last->info;
}
template<class Type>
bool linkedListType<Type>::search(const Type& searchItem)
{
nodeType<Type> *current;
bool found;
current = first;
found = false;
while(current != NULL && !found)
if(current->info == searchItem)
found = true;
else
current = current->link;
return found;
}
template<class Type>
void linkedListType<Type>::insertFirst(const Type& newItem)
{
nodeType<Type> *newNode;
newNode = new nodeType<Type>;
assert(newNode != NULL);
newNode->info = newItem;
newNode->link = first;
first = newNode;
count++;
if(last == NULL)
last = newNode;
}
template<class Type>
void linkedListType<Type>::insertLast(const Type& newItem)
{
nodeType<Type> *newNode;
newNode = new nodeType<Type>;
assert(newNode != NULL);
newNode->info = newItem;
newNode->link = NULL;
if(first == NULL)
{
first = newNode;
last = newNode;
}
else
{
last->link = newNode;
last = newNode;
}
count++;
}
template<class Type>
void linkedListType<Type>::deleteNode(const Type& deleteItem)
{
nodeType<Type> *current; // pointer to traverse the list
nodeType<Type> *trailCurrent; //pointer just before current
bool found;
if(first == NULL)
cout<<"Cannot delete from an empty list."<<endl;
else
{
if(first->info == deleteItem)
{
current = first;
first = first->link;
count--;
if(first == NULL) // list has only one node
last = NULL;
delete current;
}
else // search the list for the node with the given info
{
found = false;
trailCurrent = first;
current = first->link;
while(current != NULL && !found)
{
if(current->info != deleteItem)
{
trailCurrent = current;
current = current->link;
}
else
found = true;
}
if(found)
{
trailCurrent->link = current->link;
count--;
if(last == current) //node to be deleted is the last node
last = trailCurrent;
delete current;
}
else
cout<<"Item to be deleted is not in the list."<<endl;
}
}
}
template<class Type>
linkedListType<Type>::linkedListType()
{
first = NULL;
last = NULL;
count = 0;
}
template<class Type>
linkedListType<Type>::linkedListType(const linkedListType<Type>& otherList)
{
first = NULL;
copyList(otherList);
}
template<class Type>
linkedListType<Type>::~linkedListType()
{
destroyList();
}
template<class Type>
void linkedListType<Type>::copyList(const linkedListType<Type>& otherList)
{
nodeType<Type> *newNode; //pointer to create a node
nodeType<Type> *current; //pointer to traverse the list
if(first != NULL)
destroyList();
if(otherList.first == NULL) //otherList is empty
{
first = NULL;
last = NULL;
count = 0;
}
else
{
current = otherList.first; //current points to the lis to be copied
count = otherList.count;
first = new nodeType<Type>; //create the node
assert(first != NULL);
first->info = current->info; //copy the info
first->link = NULL; //set the link field of the node to NULL
last = first; //make last point to the first node
current = current->link; //make current point to the next node
while(current != NULL) //copy the remaining list
{
newNode = new nodeType<Type>; //create a node
assert(newNode != NULL);
newNode->info = current->info; //copy the info
newNode->link = NULL; //set the link of newNode to NULL
last->link = newNode; //attach newNode after last
last = newNode; //make last point to the actual last node
current = current->link; //make current point to the next node
}
}
}
template<class Type>
bool linkedListType<Type>::print()
{
nodeType<Type> *current;
if(first == NULL)
{
cout<<"Cannot retrieve in an empty list."<<endl<<endl;
return false;
}
else
{
current = first;
for(int i=0; i<count; i++)
{ cout << " " << current->info << " ";
current = current->link;
}
return true;
}
}
template<class Type>
bool linkedListType<Type>::replaceAt(int position, const Type& newItem)
{
nodeType<Type> *current;
if(first == NULL)
{
cout<<"\n Cannot replace in an empty list."<<endl<<endl;
return false;
}
else if(position < 0 || position > count)
{
cout<<"\n Invalid position."<<endl<<endl;
return false;
}
else
{
current = first;
for(int i=0; i<position; i++)
current = current->link;
current->info = newItem;
return true;
}
}
template <class Type>
bool linkedListType<Type>::insertAt(int position ,const Type &Item)
{
if(position < 0 || position > count )
{
cerr << "\n Invalid Position \n" << endl;
return false ;
}
nodeType <Type> *current , *newNode ;
newNode = new nodeType <Type>;
assert (newNode != NULL);
newNode -> info = Item ;
newNode -> link = NULL ;
if ( first == NULL)
{
first = newNode ;
last = newNode;
count++;
return true ;
}
else if ( position == 0 )
{
newNode -> link = first ;
first = newNode ;
count++;
return true;
}
else if ( position == count )
{
last->link = newNode ;
last = newNode;
count++;
return true ;
}
current = first ;
for (int i = 0 ; i <position-1 ; ++i)
current = current -> link ;
}
template<class Type>
struct nodeType
{
Type info;
nodeType<Type> *link;
};
template<class Type>
class linkedListType
{
public:
const linkedListType<Type>& operator=(const linkedListType<Type>&);
void initializeList();
bool isEmpty();
int length();
void destroyList();
Type front();
Type back();
bool search(const Type& searchItem);
void insertFirst(const Type& newItem);
void insertLast(const Type& newItem);
void deleteNode(const Type& deleteItem);
linkedListType();
linkedListType(const linkedListType<Type>& otherList);
~linkedListType();
bool print() ;
bool replaceAt(int position, const Type& newItem);
bool insertAt(int position ,const Type &Item) ;
bool retrieveAt(int pos,Type & item) ;
void insertArray(const Type array[],int size) ;
//protected:
int count;
nodeType<Type> *first;
nodeType<Type> *last;
private:
void copyList(const linkedListType<Type>& otherList);
};
template<class Type>
ostream& operator<<(ostream&, const linkedListType<Type>&);
template<class Type>
ostream& operator<<(ostream& osObject, const linkedListType<Type>& list)
{
nodeType<Type> *current; // pointer to traverse the list
current = list.first;
while(current != NULL)
{
osObject<<current->info<<" ";
current = current->link;
}
return osObject;
}
template<class Type>
const linkedListType<Type>& linkedListType<Type>::operator=(const linkedListType<Type>& otherList)
{
if(this != &otherList) //avoid self-copy
copyList(otherList);
return *this;
}
template<class Type>
void linkedListType<Type>::initializeList()
{
destroyList();
}
template<class Type>
bool linkedListType<Type>::isEmpty()
{
return(first == NULL);
}
template<class Type>
int linkedListType<Type>::length()
{
return count;
}
template<class Type>
void linkedListType<Type>::destroyList()
{
nodeType<Type> *temp;
while(first != NULL)
{
temp = first;
first = first->link;
delete temp;
}
last = NULL;
count = 0;
}
template<class Type>
Type linkedListType<Type>::front()
{
assert(last != NULL);
return first->info;
}
template<class Type>
Type linkedListType<Type>::back()
{
assert(last != NULL);
return last->info;
}
template<class Type>
bool linkedListType<Type>::search(const Type& searchItem)
{
nodeType<Type> *current;
bool found;
current = first;
found = false;
while(current != NULL && !found)
if(current->info == searchItem)
found = true;
else
current = current->link;
return found;
}
template<class Type>
void linkedListType<Type>::insertFirst(const Type& newItem)
{
nodeType<Type> *newNode;
newNode = new nodeType<Type>;
assert(newNode != NULL);
newNode->info = newItem;
newNode->link = first;
first = newNode;
count++;
if(last == NULL)
last = newNode;
}
template<class Type>
void linkedListType<Type>::insertLast(const Type& newItem)
{
nodeType<Type> *newNode;
newNode = new nodeType<Type>;
assert(newNode != NULL);
newNode->info = newItem;
newNode->link = NULL;
if(first == NULL)
{
first = newNode;
last = newNode;
}
else
{
last->link = newNode;
last = newNode;
}
count++;
}
template<class Type>
void linkedListType<Type>::deleteNode(const Type& deleteItem)
{
nodeType<Type> *current; // pointer to traverse the list
nodeType<Type> *trailCurrent; //pointer just before current
bool found;
if(first == NULL)
cout<<"Cannot delete from an empty list."<<endl;
else
{
if(first->info == deleteItem)
{
current = first;
first = first->link;
count--;
if(first == NULL) // list has only one node
last = NULL;
delete current;
}
else // search the list for the node with the given info
{
found = false;
trailCurrent = first;
current = first->link;
while(current != NULL && !found)
{
if(current->info != deleteItem)
{
trailCurrent = current;
current = current->link;
}
else
found = true;
}
if(found)
{
trailCurrent->link = current->link;
count--;
if(last == current) //node to be deleted is the last node
last = trailCurrent;
delete current;
}
else
cout<<"Item to be deleted is not in the list."<<endl;
}
}
}
template<class Type>
linkedListType<Type>::linkedListType()
{
first = NULL;
last = NULL;
count = 0;
}
template<class Type>
linkedListType<Type>::linkedListType(const linkedListType<Type>& otherList)
{
first = NULL;
copyList(otherList);
}
template<class Type>
linkedListType<Type>::~linkedListType()
{
destroyList();
}
template<class Type>
void linkedListType<Type>::copyList(const linkedListType<Type>& otherList)
{
nodeType<Type> *newNode; //pointer to create a node
nodeType<Type> *current; //pointer to traverse the list
if(first != NULL)
destroyList();
if(otherList.first == NULL) //otherList is empty
{
first = NULL;
last = NULL;
count = 0;
}
else
{
current = otherList.first; //current points to the lis to be copied
count = otherList.count;
first = new nodeType<Type>; //create the node
assert(first != NULL);
first->info = current->info; //copy the info
first->link = NULL; //set the link field of the node to NULL
last = first; //make last point to the first node
current = current->link; //make current point to the next node
while(current != NULL) //copy the remaining list
{
newNode = new nodeType<Type>; //create a node
assert(newNode != NULL);
newNode->info = current->info; //copy the info
newNode->link = NULL; //set the link of newNode to NULL
last->link = newNode; //attach newNode after last
last = newNode; //make last point to the actual last node
current = current->link; //make current point to the next node
}
}
}
template<class Type>
bool linkedListType<Type>::print()
{
nodeType<Type> *current;
if(first == NULL)
{
cout<<"Cannot retrieve in an empty list."<<endl<<endl;
return false;
}
else
{
current = first;
for(int i=0; i<count; i++)
{ cout << " " << current->info << " ";
current = current->link;
}
return true;
}
}
template<class Type>
bool linkedListType<Type>::replaceAt(int position, const Type& newItem)
{
nodeType<Type> *current;
if(first == NULL)
{
cout<<"\n Cannot replace in an empty list."<<endl<<endl;
return false;
}
else if(position < 0 || position > count)
{
cout<<"\n Invalid position."<<endl<<endl;
return false;
}
else
{
current = first;
for(int i=0; i<position; i++)
current = current->link;
current->info = newItem;
return true;
}
}
template <class Type>
bool linkedListType<Type>::insertAt(int position ,const Type &Item)
{
if(position < 0 || position > count )
{
cerr << "\n Invalid Position \n" << endl;
return false ;
}
nodeType <Type> *current , *newNode ;
newNode = new nodeType <Type>;
assert (newNode != NULL);
newNode -> info = Item ;
newNode -> link = NULL ;
if ( first == NULL)
{
first = newNode ;
last = newNode;
count++;
return true ;
}
else if ( position == 0 )
{
newNode -> link = first ;
first = newNode ;
count++;
return true;
}
else if ( position == count )
{
last->link = newNode ;
last = newNode;
count++;
return true ;
}
current = first ;
for (int i = 0 ; i <position-1 ; ++i)
current = current -> link ;
}
#include<iostream>
using namespace std;
template<class Type>
struct nodeType
{
Type info;
nodeType<Type> *link;
};
template<class Type>
class linkedListType
{
public:
const linkedListType<Type>& operator=(const linkedListType<Type>&);
void initializeList();
bool isEmpty();
int length();
void destroyList();
Type front();
Type back();
bool search(const Type& searchItem);
void insertFirst(const Type& newItem);
void insertLast(const Type& newItem);
void deleteNode(const Type& deleteItem);
linkedListType();
linkedListType(const linkedListType<Type>& otherList);
~linkedListType();
bool print() ;
bool replaceAt(int position, const Type& newItem);
bool insertAt(int position ,const Type &Item) ;
bool retrieveAt(int pos,Type & item) ;
void insertArray(const Type array[],int size) ;
//protected:
int count;
nodeType<Type> *first;
nodeType<Type> *last;
private:
void copyList(const linkedListType<Type>& otherList);
};
template<class Type>
ostream& operator<<(ostream&, const linkedListType<Type>&);
#include<cassert>
#include <iostream>
using namespace std ;
template<class Type>
ostream& operator<<(ostream& osObject, const linkedListType<Type>& list)
{
nodeType<Type> *current; // pointer to traverse the list
current = list.first;
while(current != NULL)
{
osObject<<current->info<<" ";
current = current->link;
}
return osObject;
}
template<class Type>
const linkedListType<Type>& linkedListType<Type>::operator=(const linkedListType<Type>& otherList)
{
if(this != &otherList) //avoid self-copy
copyList(otherList);
return *this;
}
template<class Type>
void linkedListType<Type>::initializeList()
{
destroyList();
}
template<class Type>
bool linkedListType<Type>::isEmpty()
{
return(first == NULL);
}
template<class Type>
int linkedListType<Type>::length()
{
return count;
}
template<class Type>
void linkedListType<Type>::destroyList()
{
nodeType<Type> *temp;
while(first != NULL)
{
temp = first;
first = first->link;
delete temp;
}
last = NULL;
count = 0;
}
template<class Type>
Type linkedListType<Type>::front()
{
assert(last != NULL);
return first->info;
}
template<class Type>
Type linkedListType<Type>::back()
{
assert(last != NULL);
return last->info;
}
template<class Type>
bool linkedListType<Type>::search(const Type& searchItem)
{
nodeType<Type> *current;
bool found;
current = first;
found = false;
while(current != NULL && !found)
if(current->info == searchItem)
found = true;
else
current = current->link;
return found;
}
template<class Type>
void linkedListType<Type>::insertFirst(const Type& newItem)
{
nodeType<Type> *newNode;
newNode = new nodeType<Type>;
assert(newNode != NULL);
newNode->info = newItem;
newNode->link = first;
first = newNode;
count++;
if(last == NULL)
last = newNode;
}
template<class Type>
void linkedListType<Type>::insertLast(const Type& newItem)
{
nodeType<Type> *newNode;
newNode = new nodeType<Type>;
assert(newNode != NULL);
newNode->info = newItem;
newNode->link = NULL;
if(first == NULL)
{
first = newNode;
last = newNode;
}
else
{
last->link = newNode;
last = newNode;
}
count++;
}
template<class Type>
void linkedListType<Type>::deleteNode(const Type& deleteItem)
{
nodeType<Type> *current; // pointer to traverse the list
nodeType<Type> *trailCurrent; //pointer just before current
bool found;
if(first == NULL)
cout<<"Cannot delete from an empty list."<<endl;
else
{
if(first->info == deleteItem)
{
current = first;
first = first->link;
count--;
if(first == NULL) // list has only one node
last = NULL;
delete current;
}
else // search the list for the node with the given info
{
found = false;
trailCurrent = first;
current = first->link;
while(current != NULL && !found)
{
if(current->info != deleteItem)
{
trailCurrent = current;
current = current->link;
}
else
found = true;
}
if(found)
{
trailCurrent->link = current->link;
count--;
if(last == current) //node to be deleted is the last node
last = trailCurrent;
delete current;
}
else
cout<<"Item to be deleted is not in the list."<<endl;
}
}
}
template<class Type>
linkedListType<Type>::linkedListType()
{
first = NULL;
last = NULL;
count = 0;
}
template<class Type>
linkedListType<Type>::linkedListType(const linkedListType<Type>& otherList)
{
first = NULL;
copyList(otherList);
}
template<class Type>
linkedListType<Type>::~linkedListType()
{
destroyList();
}
template<class Type>
void linkedListType<Type>::copyList(const linkedListType<Type>& otherList)
{
nodeType<Type> *newNode; //pointer to create a node
nodeType<Type> *current; //pointer to traverse the list
if(first != NULL)
destroyList();
if(otherList.first == NULL) //otherList is empty
{
first = NULL;
last = NULL;
count = 0;
}
else
{
current = otherList.first; //current points to the lis to be copied
count = otherList.count;
first = new nodeType<Type>; //create the node
assert(first != NULL);
first->info = current->info; //copy the info
first->link = NULL; //set the link field of the node to NULL
last = first; //make last point to the first node
current = current->link; //make current point to the next node
while(current != NULL) //copy the remaining list
{
newNode = new nodeType<Type>; //create a node
assert(newNode != NULL);
newNode->info = current->info; //copy the info
newNode->link = NULL; //set the link of newNode to NULL
last->link = newNode; //attach newNode after last
last = newNode; //make last point to the actual last node
current = current->link; //make current point to the next node
}
}
}
template<class Type>
bool linkedListType<Type>::print()
{
nodeType<Type> *current;
if(first == NULL)
{
cout<<"Cannot retrieve in an empty list."<<endl<<endl;
return false;
}
else
{
current = first;
for(int i=0; i<count; i++)
{ cout << " " << current->info << " ";
current = current->link;
}
return true;
}
}
template<class Type>
bool linkedListType<Type>::replaceAt(int position, const Type& newItem)
{
nodeType<Type> *current;
if(first == NULL)
{
cout<<"\n Cannot replace in an empty list."<<endl<<endl;
return false;
}
else if(position < 0 || position > count)
{
cout<<"\n Invalid position."<<endl<<endl;
return false;
}
else
{
current = first;
for(int i=0; i<position; i++)
current = current->link;
current->info = newItem;
return true;
}
}
template <class Type>
bool linkedListType<Type>::insertAt(int position ,const Type &Item)
{
if(position < 0 || position > count )
{
cerr << "\n Invalid Position \n" << endl;
return false ;
}
nodeType <Type> *current , *newNode ;
newNode = new nodeType <Type>;
assert (newNode != NULL);
newNode -> info = Item ;
newNode -> link = NULL ;
if ( first == NULL)
{
first = newNode ;
last = newNode;
count++;
return true ;
}
else if ( position == 0 )
{
newNode -> link = first ;
first = newNode ;
count++;
return true;
}
else if ( position == count )
{
last->link = newNode ;
last = newNode;
count++;
return true ;
}
current = first ;
for (int i = 0 ; i <position-1 ; ++i)
current = current -> link ;
}
template<class Type>
struct nodeType
{
Type info;
nodeType<Type> *link;
};
template<class Type>
class linkedListType
{
public:
const linkedListType<Type>& operator=(const linkedListType<Type>&);
void initializeList();
bool isEmpty();
int length();
void destroyList();
Type front();
Type back();
bool search(const Type& searchItem);
void insertFirst(const Type& newItem);
void insertLast(const Type& newItem);
void deleteNode(const Type& deleteItem);
linkedListType();
linkedListType(const linkedListType<Type>& otherList);
~linkedListType();
bool print() ;
bool replaceAt(int position, const Type& newItem);
bool insertAt(int position ,const Type &Item) ;
bool retrieveAt(int pos,Type & item) ;
void insertArray(const Type array[],int size) ;
//protected:
int count;
nodeType<Type> *first;
nodeType<Type> *last;
private:
void copyList(const linkedListType<Type>& otherList);
};
template<class Type>
ostream& operator<<(ostream&, const linkedListType<Type>&);
int main()
{
int item ;
linkedListType<int>list1,list2 ;
list1.insertLast(11) ;
list1.insertLast(9) ;
list1.insertLast(7) ;
list1.insertLast(20) ;
list1.insertLast(3) ;
list1.insertLast(6) ;
list1.print();
cout<<endl;
list2.replaceAt(0,100);
list1.replaceAt(-1,100);
list1.replaceAt(2,100);
cout<<"\nList 1 : ";
list1.print();
list1.insertAt( -2 , 6 );
list1.insertAt( 7 , -1 );
list1.insertAt( 6 , 200 );
list2.insertAt( 0 , -1 );
cout <<"\nList 1 : " ;
list1.print();
cout <<"\nList 2 : ";
list2.print();
cout <<endl <<endl;
system("pause");
return 0 ;
}
