Search code examples
c++data-structureslinked-listsingly-linked-list

linked-list: why extend a single-node list by adding the new node to head->next, but not head=head->next and then adding to head


A simple linked-list code:

#include<iostream>

struct node {
  int    data;
  node*  next;
};

int main() {
  node *head, *head1;
  head = new node;
  head1 = head; //we'll use head1 to print the entire list at the end

  head->data =  2;

the following block of code, commented out, doesn't add new node to the list

  /* head = head->next;
  head = new node;
  head -> data = 20;*/

but the (seemingly similar) below method works, and we print the entire list in the end

  head->next = new node; 
  head = head->next; 
  head->data = 20;
  
  while (head1 != nullptr) {
    std::cout<<head1->data<<std::endl;
    head1 = head1->next;
  }
}

Since both head and head->next are of type node*, how to understand that head->next = new node; works, but not head = head->next; head=new node;


Solution

  • The code shown works.

    If you try head = head->next; head=new node; it will fail because head->next at this point is null, so now head is null. You can assign a new node to it, but that does not affect the next member of the object head was previously pointing to.

    Here's how things start out:

    +----------+
    | *head    |
    +----------+
         |
         |
         V
    +----------+               +--------+
    | node     |<--------------| *head1 |
    | -------- |               +--------+
    | data = 2 |       ??????
    | *next ---------->?????? 
    +----------+       ??????
    

    Now, if we try what you're asking about, we end up with:

    +----------+               +--------+
    | node     |<--------------| *head1 |
    | -------- |               +--------+
    | data = 2 |       ??????
    | *next ---------->?????? 
    +----------+       ??????
    
    +----------+
    | *head    |
    +----------+
         |
         |
         V
    +-----------+             
    | node      |
    | --------- |           
    | data = 20 |      ??????
    | *next ---------->?????? 
    +-----------+      ??????
    

    Note that head1 still points to the original node containing the value 2, but there is nothing linking that node to the node containing the value 20.