C++ Linked List Node with class

Question

Specifically, the goal here is to create a linked structure that has some number of nodes, between 5 and 2 million. Don’t worry that this number is large or that values may wrap around past the max size of integer. If you have created your linked structure correctly, a modern computer can breeze through this code very quickly. Notice that the comments describe exactly how this main should work. Here are the highlights:

Create three loops The first loop creates the linked structure, hooking together the “next” fields of each node and giving each node an integer value between 0 and the randomly chosen size. The second loop adds up all of the nodes and counts them. Counting the nodes in this case should be used only as check to make sure you are not missing one. The third loop traverses all nodes again, this time deleting them.

Node.h

class Node {
public:
    Node();
    Node(const Node& orig);
    virtual ~Node();
    bool hasNext();
    Node* getNext();
    void setNext(Node* newNext);
    int getValue();
    void setValue(int val);
private:
    Node* next;
    int value;
};

#endif

Node.cpp

include "Node.h"
include <iostream>

Node::Node() {
    next = NULL;
}

Node::Node(const Node& orig) {
    next = orig.next;
    value = orig.value;
}

Node::~Node() {

}

bool Node::hasNext(){
    if (next != NULL)
        return true;
    else
        return false;
}

Node* Node::getNext(){
    return next;
}

void Node::setNext(Node* newNext){
    if(newNext == NULL)
        next = NULL;
    else
        next = newNext->next;
}

int Node::getValue(){
    return value;
}

void Node::setValue(int val){
    value = val;
}

main.cpp

include <cstdlib>
include <iostream>
include "Node.h"
include <time.h>

using namespace std;

int main(int argc, char** argv) {
    //This is the node that starts it all
    Node *tail;
    Node* head = new Node();

    //select a random number between 5 and 2,000,000
    srand(time(NULL));
    int size = (rand() % 2000000) + 5;
    int total = 0;
    int counter = 0;
    //print out the size of the list that will be created/destroyed
    cout << "The total size is: " << size << endl;

    head->setValue(0);
    tail = head;
    Node *newNode = new Node;
    for (int i = 1; i < size; i++){  
        Node *newNode = new Node;
        newNode->setValue(i);
        newNode->setNext(NULL);
        tail->setNext(newNode);
        tail = newNode;
    }

    //Create a list that counts from 0 to 2,000,000
    //Link all of the nodes together
    //A for loop is easiest here
    cout << head->getNext()->getValue();

    Node* current = head;
    while (current != NULL){ 
        counter += current->getValue();
        cout << current->getValue();
        current = current->getNext();
        total++;
    }

    //Traverse the list you created and add up all of the values
    //Use a while loop

    //output the number of nodes. In addition, print out the sum
    //of all of the values of the nodes.
    cout << "Tracked " << total << " nodes, with a total count of " << counter << endl;

    //Now loop through your linked structure a third time and
    //delete all of the nodes
    //Again, I require you use a while loop

    cout << "Deleted " << total << " nodes. We're done!" << endl;
    return 0;
}

It is printing out the total size then... I am getting a Seg fault:11. I am also missing some parts in the main, I am confused on how to write these as well.

Answer 1

First of all, avoid using getter functions in your Abstract Data Type. Those should be reserved for your client test application; keep them out of your ADT. Instead, pass any values in as parameters as re: the prototype. Second, avoid void returning methods in your classes. Rather, return a bool or int. Zero or false for error, and true or some non-zero integer for your success message.

That aside, I was looking up ways to use classes to build nodes, and your post came up. Interesting start. We'll see where we go with this.

Ciao, Lewsutt

Answer 2

it should be next = newNext; instead of next = newNext->next;

void Node::setNext(Node* newNext){
    if(newNext == NULL)
        next = NULL;
    else
        next = newNext;
}