Question

Below is a definition of the class of a simple link list.

class Chain;

class ChainNode {

friend class Chain;

private:

int data;

ChainNode *link ;

};

class Chain{

public:

...

private:

ChainNode *first; // The first node points.

}

Write a member function that inserts a node with an x value just in front of a node with a val value by taking two parameters, x and val. If no node has a val value, insert the node with an x value at the end of the list.

void Chain:BeforeInsert(int x, int val) {

Answer 1

class Chain;

class ChainNode {

friend class Chain;

private:

int data;

ChainNode *link ;

};

class Chain{

public:
   void BeforeInsert(int x, int val);

private:

ChainNode *first; // The first node points.

};

void Chain::BeforeInsert(int x, int val) {
   ChainNode* current = first, *prev = first;
  
   ChainNode* newNode = new ChainNode;
   newNode->data = x;
   newNode->link = NULL;
  
   if(first->data == val){
       newNode->link = first;
       first = newNode;
       return;
   }
   while(current != NULL && current->data != val){
       prev = current;
       current = current->link;
   }
   newNode->link = current;
   prev->link = newNode;
}