CODEWITHSUNDEEP
c++linked-list
Jay Elrod
Jay Elrod

Reputation: 738

C++ templated linked list trouble

I have made a few linked lists before and the concepts all make sense to me, but for a project I have to make a templated one in C++, which I haven't used a whole lot, and I am having some trouble. Please help. I have spent far too much time on such a simple thing.

I have some of the list class already, but the problem lies somewhere in here. When I make three nodes in a test case and link them all up, if I call

node1.getNext().show();

That works fine, but if I 

node1.getNext().getNext().show();

I get a segfault (core dumped). What is wrong here? I have tried changing the pointers on the return values of getNext() and getPrev() a bunch of times with no luck. I feel stupid asking this question, but I'm having some serious trouble. My node class is below, followed by a sample test case that gives a segfault.

Node.h:

template <class T> class Node
{
 public:
  Node();
  Node(T value);
  void setPrev(Node<T> node);
  void setValue(T value);
  void setNext(Node<T> node);
  Node<T> getPrev();
  T getValue();
  Node<T> getNext();
  void show();
  ~Node() { }

 private:
  Node<T> *prev;
  Node<T> *next;
  T value;
};

//default construct                                                                                                                                                     
template <class T> Node<T>::Node() {
  this->prev = NULL;
  this->value = NULL;
  this->next = NULL;
};

//overloaded construct                                                                                                                                                  
template <class T> Node<T>::Node(T value) {
  this->prev = NULL;
  this->value = value;
  this->next = NULL;
}

template <class T> void Node<T>::setPrev(Node<T> node) {
  this->prev = &node;
}

template <class T> void Node<T>::setValue(T value) {
  this->value = value;
}

template <class T> void Node<T>::setNext(Node<T> node) {
  this->next = &node;
}

template <class T> Node<T> Node<T>::getPrev() {
  return this->prev;
}

template <class T> T Node<T>::getValue() {
  return this->value;
}

template <class T> Node<T> Node<T>::getNext() {
  return this->next;
}

template <class T>
void Node<T>::show() {
  cout << value << endl;
}

Test case:

int main(int argc, char **argv) {

  typedef Node<int> IntNode;

  IntNode head(NULL);
  IntNode node1(23);
  IntNode node2(45);
  IntNode node3(77);
  IntNode tail(NULL);
  node1.setPrev(head);
  node1.setNext(node2);
  node2.setPrev(node1);
  node2.setNext(node3);
  node3.setPrev(node2);
  node3.setNext(tail);

  node1.show();
  node2.show();
  node3.show();

  cout << node1.getNext().getValue() << endl;
  cout << node1.getNext().getNext().getValue() << endl;
}

Upvotes: 1

Views: 264

Answers (3)

Konrad
Konrad

Reputation: 40947

You should be storing your next/previous members as pointers. When you set your previous and next nodes you are taking the parameters by value and therefore copying.

This means when you step through to the second .getNext() in node1.getNext().getNext().getValue() you will encounter a dangling pointer, this is why your code is failing.

Adding nodes by hand is laborious, the way something like std::list works is by having a begin and end pointer to the collection it owns. When a new node is pushed on the front or back of the list the collection creates the node, stores the value and links up the pointers ready for the next node and/or traversal.

Upvotes: 2

George Skoptsov
George Skoptsov

Reputation: 3951

You need to pass values by reference rather than by value.

When your node1.setNext(node1) is executed, setNext() gets a copy of node1 on the stack, not the variable you define in main(). Once setNext() exits, the address stored in next is no longer valid.

For starters, redefine functions setPrev and setNext as

template <class T> void Node<T>::setPrev(Node<T> &node) {
  this->prev = &node;
}

template <class T> void Node<T>::setNext(Node<T> &node) {
  this->next = &node;
}

and that will fix your immediate segfaults. However, you really need to think more about design of your code and what happens when you pass by reference or by value, to write this correctly and avoid further problems.

Upvotes: 4

Mark B
Mark B

Reputation: 96243

The big problem is that your setNext and setPrev functions take their parameters by value, so you get a copy of the nodes you declare in main.

If you want to proceed with this, pass those parameters by reference or by pointer. Passing by pointer would probably make more semantic sense and prevents this sort of accidental mistake.

Upvotes: 1

Related Questions