C++ – Simple C++ Linked List

clinked list

I have plenty of previous experience with linked lists in Java, but I seem to have confused myself with this simple attempt in C++. I am getting a segmentation fault at runtime, which from what I understand has to do with assigning a null pointer, but I am at a loss for a solution.

Edit: Thank you all for the very helpful responses. The code is now working, but trying to use 

delete p;

at the end of linkedList::addNode results in a segmentation fault at runtime. Just curious if anyone knew why that is?

Here is my updated code:

#include <iostream>
using namespace std;

class Node{
    public:
        int data;
    Node * next;
    Node(int x){
        data = x;
        next = NULL;
        }
    Node(int x, Node * y){
        data = x; 
        next = y;
        }
    };


class linkedList{
Node *head;
public:
    linkedList(){
        head = NULL;
        }
    void addNode(int value){
        Node *p;
        if(head == NULL)
            head = new Node (value, NULL);
        else{
            p=head;
            while(p->next !=NULL)
                p=p->next;
            p->next = new Node (value, NULL);
            }
        }
    void print(){
        Node * p;
        p = head;
        while(p != NULL){
            cout << p->data << "\n";
            p = p->next;
            }
        }
};


int main(void){
linkedList test;
test.addNode(4);
test.addNode(76);
test.addNode(12);
test.print();
return(0);
}

Best Answer

First, in linkedList::addNode method, you have the construction if (head = NULL), which will wind up assigning to head; you want the == operator.

Second, about the line:

head = &(Node (value, NULL));

For somewhat unintuitive reasons, this won't work. You'll get a reference to a Node, but that node will go out of scope as soon as the method ends, and attempts to reference it will lead to a segmentation fault. You need to use the new operator (same with the other similar line):

head = new Node(value, NULL);

If you add a method for removing a node, make sure to delete the node then—it won't get automatically garbage-collected like it will in Java.

Sidebar: Think of what happens like this: when you do Node(value, NULL), you're using a temporary variable that's declared like this:

Node hiddenTempNode(value, NULL);

This doesn't allocate space for an object anywhere except on the stack—it's very similar to allocating space for an int and a Node * on the stack as separate variables. As a result, as soon as you leave the method, the object disappears and the pointer to it will do weird things when used.

Third, beware: you may want to set next = NULL in your single-parameter constructor, to ensure that it always has a value. Similarly for your default constructor.

Fourth: your linkedList::print method is looping until p->next is NULL and printing the value of p->next; those occurrences of p->next should probably be changed to just p if you want to get the first and last items.

Related Topic