Given the (partial) definition of the template class linkedlist below, please wr
ID: 3871332 • Letter: G
Question
Given the (partial) definition of the template class linkedlist below, please write the code for its member functions insert_before, remove_before, push_back, and remove_back. The precondition and postcondition of each function is included.
template <typename T>
class node
{
public:
T element;
node* next;
node(const T& e) { element = e; next = NULL; }
};
template <typename T>
class linkedlist
{
private:
node<T>* head;
void insert_before(node<T>* p, node<T>* np);
// precondition: p is a pointer which points to a node in
// the list, np is a pointer to a node.
// postcondition: node np is inserted into the list before p.
void remove_before(node<T>* p);
// precondition: p is a pointer which points to a node in
// the list.
// postcondition: the node before the node at p is removed
// from the list and deleted.
public:
linkedlist();
~linkedlist();
void push_back(node<T>* np);
// precondition: np is a pointer to a node.
// postcondition: node np is appended to the end of the list.
void remove_back();
// postcondition: the last node is removed from the list
// and deleted.
}
Explanation / Answer
template <typename T>
class node
{
public:
T element;
node* next;
node(const T& e) { element = e; next = NULL; }
};
template <typename T>
class linkedlist
{
private:
node<T>* head;
void insert_before(node<T>* p, node<T>* np){
node<T>* tempNode=head;
while(tempNode!=nullptr){
if(tempNode->next==p)
break;
else
tempNode=tempNode->next;
}
//tempNode is the node before p
tempNode->next=np;
np->next=p;
}
// precondition: p is a pointer which points to a node in
// the list, np is a pointer to a node.
// postcondition: node np is inserted into the list before p.
void remove_before(node<T>* p){
node<T>* tempNode=head;
while(tempNode!=nullptr){
if(tempNode->next->next==p)
break;
else
tempNode=tempNode->next;
}
//tempnode points to 2 node before the p so now we can remove the node before p
tempNode->next=p;
}
// precondition: p is a pointer which points to a node in
// the list.
// postcondition: the node before the node at p is removed
// from the list and deleted.
public:
linkedlist();
~linkedlist();
void push_back(node<T>* np){
node<T>* tempNode=head;
while(tempNode!=nullptr){
if(tempNode->next==nullptr)
break;
else
tempNode=tempNode->next;
}
//tempNode is last element in the list
tempNode->next=np;
}
// precondition: np is a pointer to a node.
// postcondition: node np is appended to the end of the list.
void remove_back(){
node<T>* tempNode=head;
while(tempNode!=nullptr){
if(tempNode->next->next==nullptr)
break;
else
tempNode=tempNode->next;
}
//we got he 2nd last element from last and can use that to remove the last one.
tempNode->next=nullptr;
}
// postcondition: the last node is removed from the list
// and deleted.
}
Related Questions
drjack9650@gmail.com
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.