C++ Linked List Runtime Error: Unhandled Exception - Writing Location Violation

Question

I am trying to build my own implementation of a linked list in C++. My code is compiling but apparently there is some issue with my pointers referring to invalid memory addresses.

Here is my implementation:

#include <iostream>
#include <string>

using namespace std;

class Node
{
    private:
        string _car;
        Node* nextNode;

    public:
        void setCar(string car)
        {
            _car = car;
        }

        string getCar()
        {
            return _car;
        }

        void setNextNode(Node* node)
        {
            nextNode = node;
        }

        Node* getNextNode()
        {
            return nextNode;
        }
};

Node* findLast(Node* node)
{
    Node* nodeOut = NULL;
    while (node->getNextNode() != NULL)
    {
        nodeOut = node->getNextNode();
    }
    return nodeOut;
}

string toString(Node* node)
{
    string output = "";
    while (node->getNextNode() != NULL)
    {
        output += node->getCar() + " ";
        node = node->getNextNode();
    }
    return output;
}

int main()
{
    char xit;
    //ser head node to NULL
    Node* headNode = NULL;

    //create node 1
    Node* node1 = new Node();
    node1->setCar("Mercedes");

    //create node 2
    Node* node2 = new Node();
    node2->setCar("BMW");

    //set node links
    headNode->setNextNode(node1);
    node1->setNextNode(node1);
    node2->setNextNode(node2);

    headNode = node1;

    Node* lastNode = findLast(headNode);

    lastNode->setNextNode(NULL);

    cout << toString(headNode) << endl;

    //pause console
    cin >> xit;
}

Answer 1

When you allocate a new Node, the pointer nextNode is not initialized, it's just random junk. You will need to explicitly set it to NULL (probably in a constructor for Node).

Also, I assume you know that the standard C++ library has a linked list built in and you're just doing this for learning ;-)

Answer 2

Reread this:

node1->setNextNode(node1);
node2->setNextNode(node2);

...and think about what you're doing here.

If you're going to write linked-list code, I'd advise at least looking at the interface for std::list. Right now, you're interface is at such a low level that you'd be at least as well off just manipulating pointers directly.

Answer 3

The cause of your actual error is:

headNode->setNextNode(node1);

headNode is still set to NULL, thus you're dereferencing a NULL pointer. As noted by Jerry, you're also calling having nodes point to themselves, which is not what you want.

It would be cleaner if you took the car as a constructor parameter.

Answer 4

You need to relook at your code.

headNode = node1;

This assignment should be done before accesing any member function of the instance headNode. Intially you have assigned NULL to this pointer. After creating node1 you are setting to headNode that is invalid instance. This is the cause of crash. Be ensure with your objective and then try to implement do some rough work on paper , make some diagram that way you would be more clear that what you are exactly trying to achive. why setNextNode ??? i don't undeerstand what you wanted to achieve. be clear first.

As per my undertanding this code should be implemented like below..

#include <iostream> 
#include <string> 

using namespace std; 

class Node 
{ 
    private: 
        string _car; 
        Node* nextNode; 

    public: 
        void setCar(string car) 
        { 
            _car = car; 
        } 

        string getCar() 
        { 
            return _car; 
        } 

        void setNextNode(Node* node) 
        { 
            nextNode = node; 
        } 

        Node* getNextNode() 
        { 
            return nextNode; 
        } 
}; 

Node* findLast(Node* node) 
{ 
    Node* nodeOut = node->getNextNode(); 
    while ( nodeOut->getNextNode()!= NULL) 
    { 
        nodeOut = nodeOut->getNextNode(); 
    } 
    return nodeOut; 
} 

string toString(Node* node) 
{ 
    string output = ""; 
    while (node != NULL) 
    { 
        output += node->getCar() + " "; 
        node = node->getNextNode(); 
    } 
    return output; 
} 

int main() 
{ 
    char xit; 
    //ser head node to NULL 
    Node* headNode = NULL; 

    //create node 1 
    Node* node1 = new Node(); 
    node1->setCar("Mercedes"); 
    node1->setNextNode(NULL);//Make null to each next node pointer 

    headNode = node1; //assign the node1 as headNode

    //create node 2 
    Node* node2 = new Node(); 
    node2->setCar("BMW"); 
    node2->setNextNode(NULL);

    //set node links 
     node1->setNextNode(node2);




    Node* lastNode = findLast(headNode); 

    lastNode->setNextNode(NULL); 

    cout << toString(headNode) << endl; 

    //pause console 
    cin >> xit; 
}

Hope it would be useful for the beginner who implement ing the linklist in c++.

Answer 5

Thanks for all the suggestions, here is my final code after major cleanup:

// LinkedListProject.cpp : main project file.

#include "stdafx.h"

#include <iostream>
#include <string>

using namespace System;
using namespace std;

class Node
{
    public:
        Node()
            :_car(""), _nextNode(NULL)
        {
        }

        void SetCar(string car)
        {
            _car = car;
        }

        string GetCar()
        {
            return _car;
        }

        void SetNextNode(Node *node)
        {
            _nextNode = node;
        }

        Node * GetNextNode()
        {
            return _nextNode;
        }

    private:
        string _car;
        Node *_nextNode;
};

string GetData();
Node * AddNode(Node *firstNode, Node *newNode);
Node * DeleteNode(Node *firstNode, string nodeData);
void PrintNodes(Node *firstNode);

int main(int argc, char *argv[])
{
    string command = "";
    string data = "";
    Node *firstNode = NULL;

    do
    {
        cout << "Enter command: ";
        cin >> command;

        if(command == "add")
        {
            data = GetData();

            Node *newNode = new Node();
            newNode->SetCar(data);

            firstNode = AddNode(firstNode, newNode);
        }
        else if(command == "delete")
        {
            data = GetData();

            firstNode = DeleteNode(firstNode, data);
        }
        else if(command == "print")
        {
            PrintNodes(firstNode);
        }
    } while(command != "stop");

    return 0;
}

string GetData()
{
    string data = "";

    cout << "Enter data: ";
    cin >> data;

    return data;
}

Node * AddNode(Node *firstNode, Node *newNode)
{
    //add new node to front of queue
    newNode->SetNextNode(firstNode);
    firstNode = newNode;

    return firstNode;
}

Node * DeleteNode(Node *firstNode, string nodeData)
{
    Node *currentNode = firstNode;
    Node *nodeToDelete = NULL;

    if (firstNode != NULL)
    {
        //check first node
        if(firstNode->GetCar() == nodeData)
        {
            nodeToDelete = firstNode;
            firstNode = firstNode->GetNextNode();
        }
        else //check other nodes
        {
            while (currentNode->GetNextNode() != NULL &&
                   currentNode->GetNextNode()->GetCar() != nodeData)
            {
                currentNode = currentNode->GetNextNode();
            }

            if (currentNode->GetNextNode() != NULL &&
                currentNode->GetNextNode()->GetCar() == nodeData)
            {
                nodeToDelete = currentNode->GetNextNode();
                currentNode->SetNextNode(currentNode->GetNextNode()->GetNextNode());
            }
        }

        if(nodeToDelete != NULL)
        {
            delete nodeToDelete;
        }
    }

    return firstNode;
}

void PrintNodes(Node *firstNode)
{
    Node *currentNode = firstNode;
    while(currentNode != NULL)
    {
        cout << currentNode->GetCar() << endl;
        currentNode = currentNode->GetNextNode();
    }
}