1

This is a program trying to make a linked list.

#include <iostream>
using namespace std;

struct node {
char name[20];
int age;
int height;
node* next; // Pointer to the next node
 };
 node* startPTR = NULL; // Start Pointer (root)
                   // This pointer permanantly points to the start of the list
                   // Initially there are no nodes

void addNode_AT_END(); // prototype for the function that 'adds nodes at the end'

int main() {
   do {
 addNode_AT_END();
     cout << "Add more ?";
     char ch;
     cin >> ch;
   } while( ch == 'y');
}

void addNode_AT_END() {
node *temp1;
node *temp2;
temp1 = new node;  // We declare space for a pointer item and assign a temporary pointer to it  
                   //*temp1 is the node that it points to
cout << "Enter the name : ";
cin >> temp1->name;
cout << endl << "Enter the age : ";
cin >> temp1->age;
cout << endl << "Enter height : ";
cin >> temp1->height;
temp1->next = NULL; // indicates that this node when inserted in the list will be the last node
  if( startPTR == NULL) {
    startPTR = temp1;  // In the empty list last node will be the first node
  }  else {
        temp2 = startPTR;
        while( temp2->next != NULL )
            temp2 = temp2->next;
        temp2->next = temp1;
     }

}

From this yet to be completed program this is what i understand :

enter image description here

If the figure after the second call to the function addNode_AT_END is true, then what does temp2->next in the statement while( temp2->next != NULL ) contain ?

6
  • There Is a homework tag you know ;-)
    – Valmond
    Aug 31, 2011 at 16:48
  • @Suhail Gupta startPTR is not pointing to temp1, it is pointing the starting node which is pointed by temp1. Hence your diagram needs correction. Aug 31, 2011 at 16:52
  • @ EAGER_STUDENT Then what does startPTR = temp1 mean ? Aug 31, 2011 at 16:57
  • @Suhail Gupta And startPTR is a pointer and how come in your diagram temp2 points to startPTR? Aug 31, 2011 at 16:59
  • @ Nicolas Grebille For some situations i will like to introduce a self satisfaction tag Aug 31, 2011 at 17:00

2 Answers 2

2

It contains NULL, and that is because of this line:

temp1->next = NULL; 

Every new node has nextpointer which you make NULL by doing the above step, and the new node is appended at the end of the list, as a result of which, the end of the list is alwaysNULL. The while loop is traversing to the end of the list, and while(temp2->next != NULL) sets the condition which says until next of temp2 becomes NULL, do temp2 = temp2->next.

1
  • every time the value is set to null before,therefore the while loop should never execute ?! Aug 31, 2011 at 17:45
1

Your diagrams are incorrect. start = temp2 does means that start and temp2 pointers both point to the same node. Your diagram shows the next field of the temp2 pointer holds the address of start . Also after doing start->next = temp1 does not mean that if you get some new node value in temp1 (in the next function call), the start->next will still keep pointing to the new value just allocated in temp1. It will hold the old value that was in before you overwrote it with the new one. start->next = temp1 simply copies the value in temp1 ie. an address to the variable (pointer variable) the next component of the node pointed by start which is start->next . After that there is no connection between start and temp1.

In linked list context "temp1 ----> temp2" means the next field of the node whose address is stored in temp1, holds the address of the node with an address which was held or is held by temp2 . Now after you change the value of the pointer variable temp2 does not change the next field of the node held at address stored in temp1. temp1->next still contains the value which it stored before.

The next links does not point to some variable name, that is, start->next = temp will not make start node's next node always pointing to the whatever node temp1 contains, but it start->next will contain the address which temp1 stored at the time of the assignment.

note that by saying "start is pointing to temp1" means that the address

while (temp2->next != NULL)
  temp2 = temp2->next;

will break when temp2->next = NULL which means that temp2 points to the last node of the list. At this point temp2->next = temp1 links the newly allocated node after the node currently pointed by temp2. Which is simply adds the new node at the end.

  At the end of the above while loop

                                                              temp2
                                                                |
                                                                V

(start) ----> (n1) ----> (n2) ----> (n3) . . . (n(n-1)) ----> (nn) ----> NULL


   temp2->next = temp1    makes


                                                              temp2
                                                                |
                                                                V

(start) ----> (n1) ----> (n2) ----> (n3) . . . (n(n-1)) ----> (nn) ----> (temp1)--->NULL


 because temp2 holds the address of (nn) therefore linking the new node to the next node of the last node.

UPDATE

First time:

start = NULL
a new address is allocated and the address stored into temp1 pointer. Also temp->next = NULL
if condition becomes true and temp1 is assigned to start
start = temp1

List state


start = addr1;
 |
 V
(addr1) ----> (NULL)

Second time:

a new node is allocated and the address of the new node is stored into `temp1`. Let this address be `addr2`. Now `temp1` contains the value `addr2`

start is NOT NULL, as start has addr1 in it from the last call.So the else part is true and we get the address of the start node `addr1` into temp2.

temp2 = start;

which means temp2 now points to `addr1`

while loop is encountered. The first iteration the condition `temp2->next != NULL` is FALSE. This is because `temp2` points to `addr1` and the next pointer field of `addr1` has NULL from the last time the function is called. Therefore the while loop terminates.

The next statement does `temp2->next = temp1` . `temp2` points to `addr1` address, and the address of the newly allocated node `addr2` contained in `temp1` is assigned into the next field of the node whose address is stored into `temp2`. Which actually assigns the address `addr2` to the next field of the node identified by the address `addr1`.


temp1 = addr2     after allocation

start = addr1;
 |
 V
(addr1) ----> (NULL)      at begining
 ^
 |
 temp2


after temp2->next = temp1

start = addr1;
 |
 V
(addr1) ----> (addr2) ----> (NULL)      at end
 ^
 |
 temp2

Third time:

temp1 = addr3      new node address allocated

start = addr1;
 |
 V
(addr1) ----> (addr2) ----> (NULL)      at start
 ^
 |
 temp2


start = addr1;
 |
 V
(addr1) ----> (addr2) ----> (NULL)      next iteration after temp2=temp2->next
                 ^                      
                 |
               temp2


we can see temp2->next = NULL and while condition is false. Note that temp2 contains itself the address addr2, and thus temp2->next is NOT addr2, it is NULL.

start = addr1;
 |
 V
(addr1) ----> (addr2) ----> (NULL)      next iteration after temp2=temp2->next
                 ^                      
                 |
               temp2



After linking: temp2->next = temp1;

start = addr1;               temp1         the address addr3 (new node)
 |                             |          is stored in temp1. this address is assigned
 V                             V         to the next node of temp2, replacing NULL
(addr1) ----> (addr2) ----> (addr3) ----> (NULL)      
                 ^                      
                 |
               temp2

The pointers are the means to travel/traverse through the list. The starting address of the list is held in a pointer start. As the next field of each node points to the next node, if we get the start node, then by following the next fields sequentially we can visit each node. temp1 and temp2 are pointers with which the traversals are done, they act as temporary pointers, temp1 is used to hold the newly allocated node, and temp2 is used to travel through the list by following the next links till the last, when the last link is found (detected by the NULL pointer in the next field), the NULL link of this last node is replaced by the newly allocated node held by temp1 . As now the node held by temp1 is linked/added to the end of the list, temp1 is reused to hold another new node.

10
  • @Code Monkey: only for the first iteration, after which the new node is linked after the head node, and from the next call the while loop will be entered.
    – phoxis
    Aug 31, 2011 at 16:55
  • 3
    @downvoter: a justification for the downvote would be appreciated.
    – phoxis
    Aug 31, 2011 at 16:57
  • 1
    read the text in bold in my answer. temp2->next = temp1 means that the address value currently stored in temp1 is copied into the next field of the node with an address which is currently stored in temp2. I will ask you to get a copy and a pen (phisical) and try tracing whats going on. once you link the nodes the node structure stays intact as they are held by the next field of each node.
    – phoxis
    Sep 1, 2011 at 4:22
  • 1
    @ phoxis thank you ! It did, And why you stressed on physical with the pen ? ! Sep 1, 2011 at 8:19
  • 1
    @Suhail Gupta: most of people open the image editor or the text editor when asked for scribbling something. The physical pen and paper is still the best way to draft ideas, understand things, and take notes, i believe that. I am very happy to know that you were able to get the job done.
    – phoxis
    Sep 1, 2011 at 16:30

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.