Confused about insertion into linked list

Question

This is the code for the node class itself:

struct Node {
  int data;
  struct Node * next;
  Node(int x) {
    data = x;
    next = NULL;
  }
};

The code below inserts a new node at the beginning of a linked list. My question is why the fourth line doesn't mess up the order of the list. If head was previously in the position after new_node, wouldn't setting head equal to new_node mess up the list. When I run the code it works as intended but I'm not sure why.

Node *insertAtBegining(Node *head, int newData) {
   Node* new_node = new Node(newData);
   new_node -> next = head;
   head = new_node;
   return head;
}

My second question is about the following code which is supposed to insert an item at the end of the linked list. I understand how this one works, I just don't understand why a simplified version of it doesn't also work.

Node *insertAtEnd(Node *head, int newData)  {
    Node* new_node = new Node(newData);
    if(head == nullptr){
        head = new_node;
        return head;
    }
    else{
        Node* trav = head;
       while(trav -> next != nullptr){
           trav = trav -> next;
       }    
       trav -> next = new_node;
       return head;
    }
}

Simplified version

Node *insertAtEnd(Node *head, int newData)  {
    Node* new_node = new Node(newData);
    Node* trav = head;
    while(trav != nullptr){
        trav = trav -> next;
    }
    trav = new_node;
}

The simplified version only attaches the last node that you attempt to add to the end of the list. So if you try to attach 1, 2, and 3, only 3 gets added. Shouldn't it be doing the same thing since the trav pointer just becomes that last next pointer?

Answer 1

In insertAtEnd, if the list is empty, head will be null. If head is null, then head needs to be set. You can then return the new head.

if(trav != nullptr) {do something}
else head = new_node;

Now it will update the head but not the next value. You can fix this by stopping on the last value and setting its "next" pointer to the new_node pointer.

while(trav->next != nullptr){
    trav = trav -> next;
}
trav->next = new_node;

so the end result looks something like this:

Node *insertAtEnd(Node *head, int newData)  {
    Node* new_node = new Node(newData);
    Node* trav = head;
    if(trav != nullptr) {
        while(trav->next != nullptr) 
            trav = trav -> next;
        trav->next = new_node;
    }else head = new_node;
    return head;
}

Answer 2

First Code:

you are creating a newnode and for inserting at front you need to set the next of newnode to current head and then make the newnode as head (and returning it to store as the current head)

This is what first code is exactly doing. So no problem here.

Second code (simplified version):

• Here you are not storing the head (like the 1st code where you returned the head and stored appropriately)
• Also you are traversing till it becomes null (you are past the last element) and creating newnode
• you are not linking newnode to the end of the linked list

Solution for Second code (simplified version)

Node *insertAtEnd(Node *head, int newData)  {
    
    Node* new_node = new Node(newData);

    // if this is the first node (head will be NULL)
    if (!head) {
       return new_node; 
    }

    Node* trav = head;
    while(trav->next != nullptr){
        trav = trav -> next;
    }
    trav->next = new_node;
    return head;
}

Answer 3

head is not a node. It's a variable which holds the address of a node.

head = new_node; does not move any nodes! It looks at the value in the new_node variable (which is the address of a node) and stores that same value into the head variable. It doesn't change the list. It only changes the head variable.

This line changes the new node. It says that the node after the new node is the one whose address is currently in the head variable.

new_node -> next = head;

Note that we don't count the new node as part of the list yet, because you can't get to it from the first node (the one whose address is in the head variable).

This line:

head = new_node;

sets head to the address of the new node. Now we can say that the new node is in the list, because now the "first node" - the one whose address is in the head variable - is the new one. Not because we changed the node, but because we changed the head variable.

---

Note that head is a local variable within the function. If you call this function and you just do insertAtBeginning(head, 5) then it won't "change the list" because your head variable still points at the one it did before. The one in the function got changed, but that variable isn't used any more. You have to do head = insertAtBeginning(head, 5).