Please Help I am confused with the following question:- Answer the following que
ID: 3825606 • Letter: P
Question
Please Help I am confused with the following question:- Answer the following question (C++ ONLY)
1) What is the advantage derived by avoiding the sentinel for the deleted list?
2) How many times is the special case, testing for an empty list, executed within the main while loop ( while (0 != prv) )?
3) What's the reason for setting the next field of an instance to NULL before deleting it ( node->setNext(NULL) )?
Below is the coding for the above questions :-
class State
{
std::string name;
State *next;
public:
State(std::string &s);
State *getNext() const;
State *setNext(State *w);
};
State::State(std::string& s)
{
name = s;
next = 0;
}
State *State::getNext() const
{
return next;
}
State *State::setNext(State *n)
{
return next = n;
}
int main()
{
std::ifstream inputFile;
std::string path = "./states.txt";
std::string state;
State *head, *tail, *nxt, *prv, *temp = NULL;
State *delHead = NULL, *delTemp = NULL;
int rcd;
std::string sent = "$$";
inputFile.open(path.c_str());
if (!inputFile)
{
cout << "file not found:" << path << endl;
return -1;
}
tail = head = new State(sent);
rcd = 0;
while (getline(inputFile, state))
{
++rcd;
tail = tail->setNext(new State(state));
}
inputFile.close();
std::cout << "Created " << rcd << " State instances" << std::endl;
prv = head;
while (0 != prv)
{
nxt = prv->getNext();
if (0 != nxt)
{
prv->setNext(nxt->getNext());
nxt->setNext(NULL);
if (delHead == NULL) {
delHead = delTemp = nxt;
}
else {
delTemp = delTemp->setNext(nxt);
}
}
prv = prv->getNext();
}
rcd = 0;
nxt = head->getNext();
while (0 != nxt)
{
++rcd;;
nxt = nxt->getNext();
}
std::cout << "There are " << rcd << " State instances remaining" << std::endl;
rcd = 0;
delTemp = delHead;
while (delTemp != NULL)
{
++rcd;
delTemp = delTemp->getNext();
}
std::cout << "The number of States that got deleted are: " << rcd << std::endl;
prv = head;
while (prv != NULL)
{
temp = prv;
prv = prv->getNext();
temp->setNext(NULL);
delete temp;
}
head = NULL;
delTemp = delHead;
while (delTemp != NULL)
{
temp = delTemp;
delTemp = delTemp->getNext();
temp->setNext(NULL);
delete temp;
}
delHead = NULL;
return 0;
}
Thank you so much.
Explanation / Answer
1) A sentinel node is a specifically designated node used with linked lists and trees as a traversal path terminator. This type of node does not hold or reference any data managed by the data structure.This has the drawback of adding overhead, but is advantageous in that it makes it possible to avoid "special-casing".
To avoid special-casing in operations such as inserting at the front of the list, some list classes use sentinel nodes. These are dummy nodes that serve the sole purpose of acting as the (seemingly paradoxical) predecessor to the first node in the list. If we combine this with iterators, we can avoid the awkward insert_after / erase_after syntax. However, this creates some extra overhead, because each list must contain at least one node. This is problematic in cases where we may have a lot of empty lists. (for example, a hash table implementation) It is also very difficult to correctly implement "off-by-one" iterators.
2) Per my understanding loop ( while (0 != prv) ) is going to run once as in the program getline function os going to read one line from the file, which will be deleted when loop execute first time. While loop won't be executed next time as variable prv will be equal to 0 this time.
3) ( node->setNext(NULL) ) will set the last node address to NULL to identify that this is the last node. Let's assume that we have not set the last node to NULL then, in this scenario it will be dificult to identify the last node while performiing a search for insert/delete/sort. Hence, we have to set the last node as NULL in order to make the list consistent.
If you find my answer useful, then Please Rate Well! Good Luck!