c++ programming. please explain to me, thanks Consider the node structure for a

Question

c++ programming. please explain to me, thanks

Consider the node structure for a linked list struct Node int data; struct Node next ; The following code is for appending a node to a linked list passed as head_ref. The data of the new node is passed as new_data. What is the best worst case complexity of the function? The linked list has n elements in it. void append (struct Noder head_ref, int new_data) Node* new _node = new Node (); new node-data = new data ; Node *last *head _ref; new_node-next = NULL ; if (*head_ref== NULL ) *head_ref = new node ; return; while (last->next != NULL ) last = last->next; last->next = new node ; return; Select one. o a. Best NY 1) and Worst: on ) o D. Best a X log n ) and worst on logn ) 0 C. Best: an ) and worst of nnº ) 0 a. Best : nX 1) and worst of n ?) Check

Explanation / Answer

The linked list basically consists of memory blocks that are located at random memory locations. Now, one would ask how are they connected or how they can be traversed? Well, they are connected through pointers. Usually, a block in a linked list is represented by a structure like this :

Struct Node{ // Structure is created with name of Node
int data; // Structure member of int type
struct Node *next; // here next define pointers to structures in very similar way as you -
//- define the pointer to any other variable.
}

So as you can see here, this structure contains a value ‘data’ and a pointer to a structure of the same type. The value ‘data’ can be any value (depending upon the data that the linked list is holding) while the pointer ‘next’ contains the address of next block of this linked list. So linked list traversal is made possible through these ‘next’ pointers that contain the address of the next node. The ‘next’ pointer of the last node (or for a single node linked list) would contain a NULL.

// ( here two parameters is passing one is head_ref a double pointer which points to head
(or start ) the pointer of the linked list. The second one is new_data of integer data type)

void append (struct Node ** head_ref, int new_data)
{
Node * new_node= new Node(); // here creating new_node of pointer type which basically we can refference

new_node->data =new_data; // assigning value by using the -> operator, you can modify the node
a pointer (new_node in this case) points to.
//Creating one more variable of Node type(pointer variable) which points to the head of the node.
Node *last= *head_ref;

new_node->next=NULL; //The node new_node points to has its next pointer
// set equal to a null pointer.
//here if the condition is checking that whether the head of Node is NULL or not.Here head_ref is pointing to the first node.If the condition is true than head_ref pointing to new_node and return.
if(*head_ref==NULL)
*head_ref=new_node; return
}
//let assume that above if the condition is false then it means Node is not null.
// while loop running and this loop will terminate when last will reach to end of the Node.Till then it will move one node to the another.
while(last->next!=NULL)
last=last->next;
//After coming out of the loop last already pointing to the last node now one more time the last pointer is shifted to next node but no node is remaining so last will point to null. And return.
last=last->next;
return;
The above program is a part of link list where the new node is created and assigned the value to them if the node is empty than href_head point to the new node.Or node is having already a list of node than by while loop traverse to the last node.

Related Questions

Navigate

• Browse (All)
• Browse C
• Subjects

---

---

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.