Please complete the two functions below based on the specification comments stru

Question

Please complete the two functions below based on the specification comments

struct Node {
Point xy;
Node* next;
Node* prev;
};
class DLinkedList {
public:
Node* head;
Node* tail;
DLinkedList() : head(nullptr), tail(nullptr) {}
void addNode(Node*); // add a Node to the list
Node* removeNode(Point); //remove a Node from the list
};
void DLinkedList::addNode(Node* node) {
  
// Fill in the missing code with the assumption that a new Node is added to the end
// of the list, which involves using the current “tail” pointer value to access the previous
// Node to update it’s “next” pointer value to point to the newly added Node, and then
// updating the “tail” pointer to also point to the newly added Node. CAREFUL to deal
// correctly with an “empty” list (i.e. both “head” and “tail” pointers are nullptr).
}
Node* DLinkedList::removeNode(Point XY) {
// Fill in the missing code with the assumption that the removed Node will always be
// the first Node in the list who’s “xy” Point matches the “XY” Point param. If there
// is no matching Point in the list then the function should return nullptr, otherwise it
// should return a pointer to the removed Node. When removing a Node remember to
// connect up the previous Node in the list and the next Node in the list by correctly
// updating the previous Node “next” pointer and the next Node “prev” pointer.
// CAREFUL to correctly handle cases where the removed Node is either the first and/or
// last Node in the list (which requires updating the list’s “head” and/or “tail” pointers),
// and of course the case where the list is “empty”.
}

Explanation / Answer

struct Node {
   Point xy;
   Node* next;
   Node* prev;
};

class DLinkedList {
   public:
   Node* head;
   Node* tail;
   DLinkedList() : head(nullptr), tail(nullptr) {}
   void addNode(Node*); // add a Node to the list
   Node* removeNode(Point); //remove a Node from the list
};

void DLinkedList::addNode(Node* node) {
  
   // Fill in the missing code with the assumption that a new Node is added to the end
   // of the list, which involves using the current “tail” pointer value to access the previous
   // Node to update it’s “next” pointer value to point to the newly added Node, and then
   // updating the “tail” pointer to also point to the newly added Node. CAREFUL to deal
   // correctly with an “empty” list (i.e. both “head” and “tail” pointers are nullptr).

   // when list is empty
   if(head == NULL){

       head = node;
       tail = head;

   }
   else{
       // adding at end
       tail->next = node;
       node->prev = tail;

       tail = node;

   }
}

Node* DLinkedList::removeNode(Point XY) {

   // Fill in the missing code with the assumption that the removed Node will always be
   // the first Node in the list who’s “xy” Point matches the “XY” Point param. If there
   // is no matching Point in the list then the function should return nullptr, otherwise it
   // should return a pointer to the removed Node. When removing a Node remember to
   // connect up the previous Node in the list and the next Node in the list by correctly
   // updating the previous Node “next” pointer and the next Node “prev” pointer.
   // CAREFUL to correctly handle cases where the removed Node is either the first and/or
   // last Node in the list (which requires updating the list’s “head” and/or “tail” pointers),
   // and of course the case where the list is “empty”.

   if(head == nullptr){
       return nullptr;
   }

   // according to question, removed node is preset at head/first node

   Node *node = NULL;

   if(head->xy == XY){
       node = head;
       head = head->next;
   }else{
       Node *temp = head;
       while(temp->next != NULL){

           if(temp->next->xy == XY){

               node = temp->next; // node to be deleted
               temp->next = temp->next->next;

               if(temp->next != NULL){
                   temp->next->prev = temp;
               }else{
                   tail = temp;
               }

               break;
           }

           temp =vtemp->next;
       }
   }

   return node;

}

Related Questions

Navigate

• Browse (All)
• Browse P
• Subjects

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.