Linked list push method

Question

I'm working on a templated generic linked list in C++, and I'm having trouble with the push() method. I think I know the problem, but I can't figure out a solution. Here is the push method I have.

template <class T> void DLL<T>::pushFront(T value) {
  Node<T> node(value);
  temp = node;
  temp->setPrev(*head);
  temp->setNext(*(head->getNext()));
  head->setNext(*temp);
  temp->getNext()->setPrev(*temp);                                                                                                                                    
  this->length++;                                                                                                                                                     
}

After pushing some integers into the list, traversing through the list and printing off the values results in printing off numbers that appear to be random space in memory. I think this is because of something to do with the node variable being destroyed after the push function returns. Anyone know why this isn't working? All of the setNext/Prev() and getNext/Prev() functions work correctly in my other tests. I'm stumped...

edit*

The variables head and temp are globals of type Node< T >*

Is line 3 supposed to be temp = &node?

tmpearce
– tmpearce

2012-03-13 03:25:14 +00:00
Commented Mar 13, 2012 at 3:25 — tmpearce
– tmpearce, Commented Mar 13, 2012 at 3:25

mfontanini · Accepted Answer · 2012-03-13 03:22:17Z

1

You should use pointers to store the Nodes in your list.

Node<T> node(value);
temp = node;

After this code has come out of scope, the memory allocated for "node" will be freed, corrupting your linked list. Use pointers instead:

template <class T> void DLL<T>::pushFront(T value) {
  Node<T> *node = new Node<T>(value);
  node->setPrev(head);
  node->setNext(head->getNext());
  head->setNext(node);
  node->getNext()->setPrev(node);
  this->length++;
}

Where your class Node should be something like:

template<class T> class Node {
public:
    /* ... */
private:
    Node<T> *next;
    T data;
};

answered Mar 13, 2012 at 3:22

mfontanini

22k5 gold badges71 silver badges74 bronze badges

Sign up to request clarification or add additional context in comments.

2 Comments

Jay Elrod Over a year ago

Even doing it this way still has the same results. Is there some specific way I need to keep the "new Node<T>(value)" alive? It is ok that it is declared within the method, right?

mfontanini Over a year ago

Yes, it is okay. You probably have a problem in your node structure, it's hard to tell what is it since you only gave us that method.

Jerry Coffin · Accepted Answer · 2012-03-13 03:48:05Z

First of all, head should not be a global -- it should be a member of DLL, so each dll (poor abbreviation, IMO) has a head (and probably a tail).

Second, the getnext, setnext, getprev and setprev seem to me a 100% pointless waste of time. You're gaining nothing in the way of encapsulation or readability by using them instead of reading/assigning variables.

Third, as @fontanini already pointed out, when you push a node, you need to actually allocate a node, not try to re-use a single node every time.

Fourth, it looks to me like you're over-complicating the pointer manipulation involved, probably at least in part due to the ugliness/unreadability of the getnext/setprev, etc. Once you have a node, splicing it to the front of a linked list only takes three operations (plus incrementing the length):

template <class T> 
void DLL<T>::pushFront(T value) { 
   node<T> *tmp = new node<T>(value);
   tmp -> next = head;
   tmp -> next -> prev = tmp;
   head = tmp;
   ++length;
}

When I've done it, I've found it a bit simpler to just pass the pointers to node's ctor though. In that case, it comes out something like this:

template <class T> 
void DLL<T>::pushFont(T value) { 
   // These parameters are value, prev, and next, respectively.                             
   node<T> *tmp = new node<T>(value, NULL, head);
   tmp->next->prev = tmp;
   head = tmp;
   ++length;
}

Collectives™ on Stack Overflow

Linked list push method

2 Answers 2

2 Comments

Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

2 Answers 2

2 Comments

Comments

Your Answer

Sign up or log in

Post as a guest

Related