Linked list problem

Question

Hello, I got some problem with the linked list I've written. I dunno if it's either my insert function that the problem, or if it's my traverse function that's not correct. I hope for some input. A side note, I'm initalising the list in main now since I don't know if my initNode function is correct.

#include <iostream>

using namespace std;

typedef struct Node
{
   int data;
   Node *next;
};

void initNode(Node *head)
{
   head = new Node;
   head->next = NULL;
}

void insertNode(Node *head, int x)
{
   Node *temp;
   temp = new Node;
   temp->data = x;

   temp->next = head;
   head = temp;

}

void traverse(Node *head)
{
   Node *temp;
   temp = head;

   if(head == NULL)
   {
      cout << "End of list. " << endl;
   }
   else
   {
      while(temp != NULL)
      {
         cout << temp->data << " ";
         temp = temp->next;
      }
   }

}

int main()
{
   Node *head;
   head = NULL;

   insertNode(head, 5);
   insertNode(head, 5);

   traverse(head);

   return 0;
}

Answer 1

Your insertNode() function takes a pointer to a node; when you change where that pointer points, it only affects the pointer in that function (the pointer is copied when you call the function).

You need to pass a reference to a pointer or a pointer to a pointer:

void insertNode(Node*& head, int x)     // or...
void insertNode(Node** head, int x)

If you had attached a debugger, you would have found that head was still null after calling insertNode(); that would have been a good clue that that's where the problem was.

Answer 2

The way you have you initNode function written will result in memory leaks. You've passed in a pointer, but you need to pass in a reference to a pointer. (Same issue that James and casablanca mentioned for insertNode.)

Answer 3

Your head isn't being returned to main from insertNode. Note that even though head is a pointer, the pointer itself is a value and any changes to the pointer value are not reflected in main. The simplest solution is to pass back the updated value of head:

Node *insertNode(Node *head, int x)
{
  ...
  return head;
}

And update it in main:

head = insertNode(head, 5);

The other common way of doing this is to pass a pointer to a pointer and update it directly:

void insertNode(Node **head, int x)
{
   Node *temp;
   temp = new Node;
   temp->data = x;

   temp->next = *head;
   *head = temp;
}

And call it like this:

insertNode(&head, 5);