Problem printing out linked-list

Question

I am trying to create my own datatype that is like a vector or an array.

I am having troubles with my print function; When I go to print the list, it only prints the last item in the list.

// LinkedListClass.cpp : Defines the entry point for the console application.

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

class Node
{
public:
 int value;
 Node* next;

 Node::Node(int val)
 {
  value = val;
 };
};

class List
{
public:
 Node* firstNode;
 Node* currentNode;
 int size;

 List::List()
 {
  firstNode = NULL;
  currentNode = firstNode;
  size = 0;
 };

 void push(Node* node)
 {
  if(firstNode == NULL)
  {
   firstNode = node;
   firstNode->next = currentNode;
   size++;
  }
  else
  {
   currentNode = node;
   currentNode = currentNode->next;
   size++;
  }
 };

 void print()
 {
  if(firstNode != NULL)
  {
   Node* printNode = firstNode;
   while(printNode->next != NULL)
   {
    std::cout << "List Item " << printNode->value << std::endl;
    printNode = printNode->next;
   }
  }
 };
};

int _tmain(int argc, _TCHAR* argv[])
{
 List ll = List();
 for(int i = 0; i < 10; ++i)
 {
  Node val = Node(i);
  ll.push(&val);
 }
 std::cout << ll.firstNode->value << std::endl;
 ll.print();
 std::cout << "Size " << ll.size << std::endl;
 std::cin.ignore();
 return 0;
}

/* Output

9
Size 10

*/

I know this is nowhere near completed, but if you have any other pointers (lol), please feel free to suggest.

Answer 1

The following lead to undefined behavior:

  Node val = Node(i);
  ll.push(&val); // take address of temporary
  ...
  firstNode = node; // store address of temporary here
  ...
  ll.print(); // temporary `val` was destroyed, but all nodes are point to it

You could change your code as follows:

  Node* val = new Node(i);
  ll.push( val );

And don't forget to delete all nodes later.

Answer 2

Your push() method is incorrect. The first time you push a node, it correctly assigns it to firstNode, but every subsequent push() just sets currentNode to the new node, and then sets currentNode to NULL -- you're not actually adding anything to your list.

I think it bears mentioning that pointers are not reference-by-name in C++. For instance, setting firstNode->next = currentNode doesn't make currentNode the next element in the list; it just makes firstNode->next point to the same address that currentNode does (in this case, NULL).

I'm not going to write the code for you, but here's how your push() function should work. The key is that you should be setting the 'next' field of an existing node to your new node, rather than currentNode to the new node:

1. In the case where firstNode is NULL, set firstNode to the new node and set firstNode->next to NULL (since it has no next element). You can also set currentNode = firstNode here for convenience.

2. In the case where firstNode is not NULL, we need to walk from firstNode down the chain until we find a node whose next field is NULL, then set its next field to the new node. Alternatively, we can use that currentNode pointer to access the last element in list and do the same thing, being sure to set currentNode to point to the new node when we're done.

You basically have part 1 done, but part 2 still needs to be implemented. Feel free to ask for clarification/give criticism. :)

Answer 3

try it like

 Node* val=new Node(i) 

previously u were storing the temporary variable. so no store the ndoe in dynamic memory so seprate memory can be given. when u were creating the node it is create for temparary purpose &temporary address were stored so when u traverse back the temporary memory had been released u will find there some garbage. value.

Answer 4

There are three important errors:

push() --- fixed

void push(Node* node)
 {
  if(firstNode == NULL)
  {
   firstNode = node;
   currentNode = node;
   // firstNode->next = currentNode; --> this does nothing useful!
   size++;
  }
  else
  {
   currentNode->next = node;
   currentNode = node;
   //currentNode = node;               -|
   //currentNode = currentNode->next;  -|----> why? what? Do explain.
   size++;
  }
 }

I think by assigning firstNode->next = currentNode; you expected the next time currentNode was updated, it would update firstNode->next as well.

It doesn't work that way.

firstNode->next = currentNode; implies that the address stored in currentNode is now in firstNode->next. So next time you store something in currentNode = node; you're not storing it in firstNode->next. So you have a broken linked list --- which is why your output didn't go very far.

Also, this is really bad. By setting currentNode=node before setting the current node's next pointer to node, you've broken the list again. You should first point currentNode->next to node and then set the currentNode as node (node being the node which you're pushing onto your list).

Node val = Node(i);

The scope of val is only within that iteration of your loop. Once you loop around, it's off the stack and doesn't exist anymore. But you've copied the pointer of val to your list --- so now with the right push method, you're just adding a dangling pointer.

Node *val = new Node(i);
ll.push(val);

You need to put it on the heap so it stays on till you don't need it anymore.

... which leads us to your destructor!

Since you've allocated a node, you'll need to deallocate it. So do that in your destructor --- traverse your list and deallocate all those nodes.