Implementing a Linked List

Question

I am working on implementing a Linked List in C++. While I have done this in java in the past, I do not understand how to do it in C++ with pointers, as the code compiles but it is giving me a Segmentation Fault when I run it. What am I doing wrong?

My node.h File

#ifndef NODE_H
#define NODE_H

#include <string>
using namespace std;

class Node
{
public:

    Node(const string, const int) ;
    ~Node() { }
    void setNext(Node *); // setter for the next variable
    Node * getNext();     // getter for the next variable
    string getKey();      // getter for the key variable
    int getDistance();    // getter for the dist variable

private:
   Node *next;
   int dist;
   string key;
};

#endif

My Node.cpp File

#include "node.h"
#include <string>

Node::Node(string key, int dist){
    key = key;
    dist = dist;
}

void Node::setNext(Node * next){
    next->next;
}

Node * Node::getNext(){
    return this->next;
}

string Node::getKey(){
    return key;
}

int Node::getDistance(){
    return dist;
}

And my main.cpp File

#include "node.h"
#include <iostream>

using namespace std;

int main(){
    Node* nptr1 = new Node("Test1", 2);
    Node* nptr2 = new Node("Test2", 2);
    Node* temp;

    nptr1->setNext(nptr2);
    temp = nptr1->getNext();
    cout << temp->getKey() << "-" << temp->getDistance() << endl;
}

Any help would be greatly appreciated. Thanks.

list<> or slist<> are the correct ways to do it in C++. Only in C do you have to get your hands dirty like this... — Michael Dorgan
– Michael Dorgan, Commented Feb 14, 2013 at 18:44
@MichaelDorgan They're the correct way to do it when you want to solve a different problem. When you want to implement a linked list, be it for education or experimentation or because you have a very special case where you can beat the stdlib (because you can make more assumptions), you implement a linked list. — user395760
– user395760, Commented Feb 14, 2013 at 18:47
Then mark the tag C instead - being snarky a bit I know. I think I need another cup of coffee :) — Michael Dorgan
– Michael Dorgan, Commented Feb 14, 2013 at 18:48
In your setters "key = key; dist = dist;" etc. don't do anything. All you do is set the local function var to itself. Add this.key=key; etc. to destinguish between local names and member names — eladidan
– eladidan, Commented Feb 14, 2013 at 18:49

Olaf Dietsche · Accepted Answer · 2013-02-14 18:49:25Z

You should initialize all your members to a defined value. You shouldn't name parameters and members the same, this leads almost always to confusion or, more likely, to bugs

Node::Node(string key_val, int distance)
    : next(0)
{
    key = key_val;
    dist = distance;
}

better yet, use member initialization

Node::Node(string key_val, int distance)
    : next(0),
      key(key_val),
      dist(distance)
{
}

as commenters already pointed out, you must set the next pointer in setNext() to the given parameter and you should not modify the parameter, but the this->next member

void Node::setNext(Node * next_ptr){
    next = next_ptr;
}

NickW · Accepted Answer · 2013-02-16 18:36:18Z

The key to linked lists and other data structures in languages with pointers/dynamic memory allocation is to map out all possible states (cases) for each operation. You must make sure that your code correctly handles the pointers and memory at each case. This is probably the reason why you are being asked to implement it: to teach you how to think about pitfalls that arise. Thus, I will not simply give you a direct solution, but rather outline how you can seize this opportunity to understand fundamental concepts that will help you and others on this problem and problems in the future.

Even in what appears to be a stage1 (extremely basic) linked list with tail insertion, you should develop some sort of mapping scheme. My personal experience has been that for each line within a main():

draw a box for each object
list all data variables in the boxes
list any initialized/assigned value beside the non-pointer variables
draw arrows from pointer variables to objects you know are being pointed to
draw arrows from pointer variables to a blank area for pointers which are not assigned

One thing that is critical to know is that uninitialized data and pointers exhibit undefined properties that vary based on os/compiler, thus it often crucial that you define most of them with suitable initial values. I have found that always initializing to a safe default on declaration has served me well (there are cases where it isn't possible or creates performance issues, but those can be handled as needed - e.g. Lazy Initialization). Unlike Java, basic C++ does not raise null pointer exceptions, provide initial value, or garbage collect by default (it is highly dependent on compiler/library and passed options). At best, your program will segfault (a more general exception that usually means you have accessed memory you weren't supposed to), in worse cases it will either still work but behave unpredictably or crash with no feedback. Therefore, you should use your mapping scheme to verify that you are not performing operations on pointers to NULL or pointers to objects that have had free/delete performed on them. Further, you will want to make sure that where they point to makes sense. Like any linking scheme, you can have paradoxes like linking a node to itself or otherwise creating a circular link.

So, as mentioned, keeping track of all possible cases for each operation is also important. If this program is a means of learning data structures or pointers, as I suspect it is, you will undoubtedly be asked to implement more advanced lists. The more advanced lists can be tricky, so you should get in the habit early of trying to determine how performing a particular operation may require extra care (corner cases). For lists, you should consider cases where the list is empty, has 1 element, has 2 elements, or 2+ elements. You might also need to consider if an element is being inserted/removed from the start, end, or somewhere in-between. Again, make extensive use of mapping to understand how these cases will play out. You really should try to think this through using the aforementioned methods, but you can also check wikipedia or a data structures textbook for more information.

BTW, as Raymond mentioned, you can use a debugger to help you see the problem. In fact, if you haven't used a C/C++ debugger before, this is the perfect time to learn. After you have this working, look up the documentation on the C/C++ debugger for your platform. Try to using it to step through the main() of your non-working code and see if the data values match the expectations in your mappings. This kind of skill will prove invaluable later on.

Also, note that this is usually a pointer in C++, so do not confuse it with how it is used in Java/Python: member data is accessed using this->somedata NOT this.somedata as some have suggested. With that being said, you might want to use the convention of this->somedata = somedata in places where you have parameter names that are the same as member variables, for added clarity. Of course, the advise of using different parameter names works, too.

Collectives™ on Stack Overflow

Implementing a Linked List

2 Answers 2

Comments

Comments

Hot Network Questions

Collectives™ on Stack Overflow

2 Answers 2

Comments

Comments

Related