#include

using namespace std;

template

struct NodeType

{

ItemType info;

NodeType* next;

};

template

class SortedType {

private:

NodeType *listData;

int length;

public:

void InsertItem(ItemType item);

void DeleteItem(ItemType item);

};

template

void FindItem(NodeType* listData,

ItemType item,

NodeType*& location,

NodeType*& predLoc,

bool& found)

// Pre: List is not empty.

// Post:If there is an element someItem whose key matches item's

// key, then found = true; otherwise, found = false.

// If found, location contains the address of someItem and

// predLoc contains the address of someItem's predecessor;

// otherwise, location contains the address of item's logical

// successor and predLoc contains the address of item's

// logical predecessor.

{

bool moreToSearch = true;

location = listData->next;

predLoc = listData;

found = false;

while (moreToSearch && !found)

{

if (item.ComparedTo(location->info) < 0)

moreToSearch = false;

else if (item.ComparedTo(location->info)== 0)

found = true;

else

{

predLoc = location;

location = location->next;

moreToSearch = (location != listData->next);

}

}

}

template

void SortedType::InsertItem(ItemType item)

{

NodeType* newNode;

NodeType* predLoc;

NodeType* location;

bool found;

newNode = new NodeType;

newNode->info = item;

if (listData != NULL)

{

FindItem(listData, item, location, predLoc, found);

newNode->next = predLoc->next;

predLoc->next = newNode;

// If this is last node in list, reassign listData.

if ((listData->info.ComparedTo(item)) < 0)

listData = newNode;

}

else // Inserting into an empty list.

{

listData = newNode;

newNode->next = newNode;

}

length++;

}

template

void SortedType::DeleteItem(ItemType item)

{

NodeType* location;

NodeType* predLoc;

bool found;

FindItem(listData, item, location, predLoc, found);

if (predLoc == location) // Only node in list?

listData = NULL;

else

{

predLoc->next = location->next;

if (location == listData) // Deleting last node in list?

listData = predLoc;

}

delete location;

length--;

}

int main() {

return 0;

}

*** CAN IT BE ALTERED TO READ IN A STRING AND OR STIRNGS AND PRINT OUT C++ NEED A DRIVER (MAIN) TO TEST