Rewrite the code, build the linked list without dummy node!!! using namespace st

Question

Rewrite the code, build the linked list without dummy node!!!

using namespace std;
#include <iostream>
#include <iomanip>
#include <string>

struct Node {
int info;
Node* next ;
};
// recycleList -- recycle the nodes in the list referenced by current
void recycleList (Node * current) {
if (current != nullptr) {
recycleList (current->next);
delete (current); // return the storage ref'd by current
}
}
int main () {
int n;
cout << "How long a list do you want? " << endl;
cin >> n;
Node *head = new Node (); // dummy node
head->info =0; // irrelevant -- not used
head->next = nullptr;
Node *current = head; // start iterator at dummy node
for (int i = 1 ; i <= n; i ++) { // Append n nodes
current->next = new Node (); // append a node
current->next->info = i; // insert the value
current = current->next; // move to the next node
}
current->next = nullptr; // Terminate the list
cout << "Printing the list:" << endl;
current = head->next; // Start at appended list
while (current != nullptr) { // For each node in the list
cout << current->info << ' '; // print the current element
current = current->next; // move to the next element
}
cout << endl;
recycleList(head); // Not needed, just illustrating deleting the list
return 0;
}

Explanation / Answer

using namespace std;

#include <iostream>
#include <iomanip>
#include <string>

struct Node {
   int info;
   Node* next ;
};

// recycleList -- recycle the nodes in the list referenced by current
void recycleList (Node * current) {
   if (current != nullptr) {
   recycleList (current->next);
   delete (current); // return the storage ref'd by current
   }
}

int main () {
   int n;
   cout << "How long a list do you want? " << endl;
   cin >> n;
   /* Node *head = new Node (); // dummy node */
   Node *current = new Node();
   current->info = 1;
   current->next = nullptr;
   /*
   head->info =0; // irrelevant -- not used
   head->next = nullptr;
   Node *current = head; // start iterator at dummy node
   */

   for (int i = 2 ; i <= n; i ++) { // Append n nodes
   current->next = new Node(); // append a node
   current->next->info = i; // insert the value
   current = current->next; // move to the next node
   }

   current->next = nullptr; // Terminate the list
   /*
   cout << "Printing the list:" << endl;
   current = head->next; // Start at appended list

   while (current != nullptr) { // For each node in the list
   cout << current->info << ' '; // print the current element
   current = current->next; // move to the next element
   }
   */

   cout << endl;

/*
   recycleList(head); // Not needed, just illustrating deleting the list

*/
   return 0;
}

------------------

Please take a note of below two points :-

1). As the question asks to build a linked list without using a dummy node. I have only did that part.

If you want to print the list OR recycle the list, then some code changes will be required. Because, ideally the two things are not possible without dummy node head. So, in case you need the two functionalities; we will have to introduce Node* prev in the structure. Using prev we will find the start of the list, and then do the operations.

2). The italicized part of the code is the one that I have commented in your previous code. The new/changed code introduced is in bold.

3). If you are expecting a similar solution with a class, then use below definition for Node instead of struct.

class Node {

int info;
Node* next;

public:
Node(int info) {this.info = info; this.next=NULL;};
Node(int info, Node* next) {this.info = info; this.next=next;};
};

And then you will have to change the Node initialization code also. Ex :-

Node *head = new Node (); // dummy node
head->info =0; // irrelevant -- not used
head->next = nullptr;

will be changed to

Node *head = new Node(0, nullptr);

Related Questions

Navigate

• Browse (All)
• Browse R
• Subjects

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