Insert a Node at the Tail of a Linked List

Question

I've solved this question, but have a small question. In the while loop we check if (temp->next != NULL), why wouldn't work if we check (temp != NULL). Isn't it the same, both checks will get us to the end of the linked list? Also any code review is appreciated!

You are given the pointer to the head node of a linked list and an integer to add to the list. Create a new node with the given integer. Insert this node at the tail of the linked list and return the head node. The given head pointer may be null, meaning that the initial list is empty.

/*
  Insert Node at the end of a linked list 
  head pointer input could be NULL as well for empty list
  Node is defined as 
  struct Node
  {
     int data;
     struct Node *next;
  }
*/
Node* Insert(Node *head,int data)
{
  // creates a temp to hold the last node and set last's data and next
    Node *last = new Node;
    last->data = data;
    last->next = NULL;
    // if the linked list is empty then set head = last
    if (head == NULL) {
        head = last;
    } else { // if the linked list is not empty
        // creates a temp node and sets it to head
        Node *temp = new Node;
        temp = head;
        // uses temp to find the last node
        // Why do we have to use temp->next here instead of temp? wouldn't it be the same?
        while (temp->next != NULL) {
            temp = temp->next;
        }
        // appends the last node with last
        temp->next = last;
    }
    // returns head of linked list
    return head;
}

Answer 1

temp != NULL shouldn't work because - well, imagine this:

temp = temp->next runs and now temp is set to the last node. Then, the check is ran temp != NULL. Because the last node is not null, it will run temp = temp->next, and because you're already on the last node this means that temp becomes null. The check then runs again, and as temp is null it moves out of the loop and attempts temp->next = last, which doesn't work (and probably triggers an error) as temp is null. You're gonna want it to check the next node before it sets temp to that value, as it does currently.

As for code review, the logic seems sound, and presentation is up to you, however if this were my code there would be a few things I'd do personally, however I'll put an example instead of points:

/*
  Insert Node at the end of a linked list 
  head pointer input could be NULL as well for empty list
  Node is defined as 
  struct Node
  {
     int data;
     struct Node *next;
  }
*/
Node* Insert(Node *head,int data)
{
    // Creates a temp to hold the last node and set last's data and next
    Node *last = new Node;

    last->data = data;
    last->next = NULL;

    // If the linked list is empty then set head = last
    if (head == NULL) {
        head = last;
    } else {
        // Creates a temp node and sets it to head
        Node *temp = new Node;

        temp = head;

        // Uses temp to find the last node
        while (temp->next != NULL) {
            temp = temp->next;
        }

        // Appends the last node with last
        temp->next = last;
    }

    // Returns head of linked list
    return head;
}

But do whatever suits you - as long as you follow the standards of any projects you're working on, the presentation of what you code in your own time is totally your decision (many will disagree with the way I've presented the code and many will agree - opinion varies from person to person, and there's no one way to present that pleases everyone).

Furthermore, a comment about your comments. I didn't fix them in my example above, however I would be more specific to the code you're commenting by. So, for example: // Creates a temp to hold the last node and set last's data and next. That comment mentions things that aren't happening in the line directly below - I would make sure to comment each line as it happens in this case. I would also be a bit more explanatory about each line - so for example, in that same line that I was just commenting on I would say rather than set last's data and next, something along the lines of set the data that the node contains, as well as a pointer to the next node - although I would describe each process on separate occasions, as I mentioned, rather than together like I just did for the sake of example.

Answer 2

Memory Leak

These lines here create a memory leak, because you allocate a node and never free it:

    // creates a temp node and sets it to head
    Node *temp = new Node;
    temp = head;

You don't need to allocate another node there, because you aren't actually ever using it. You can just set the temp pointer directly to head:

    Node *temp = head;