Insert a Node at the Tail of a Linked List Using C++ You are given the pointer t
ID: 3904188 • Letter: I
Question
Insert a Node at the Tail of a Linked List Using C++
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 of the linked list formed after inserting this new node. The given head pointer may be null, meaning that the initial list is empty.
Input Format
You have to complete the SinglyLinkedListNode insertAtTail(SinglyLinkedListNode head, int data) method. It takes two arguments: the head of the linked list and the integer to insert at tail. You should not read any input from the stdin/console.
The input is handled by code editor and is as follows:
The first line contains an integer n , denoting the elements of the linked list.
The next n lines contain an integer each, denoting the element that needs to be inserted at tail.
Constraints
Output Format
Insert the new node at the tail and just return the head of the updated linked list. Do notprint anything to stdout/console.
The output is handled by code in the editor and is as follows:
Print the elements of the linked list from head to tail, each in a new line.
Sample Input
Sample Output
Explanation
First the linked list is NULL. After inserting 141, the list is 141 -> NULL.
After inserting 302, the list is 141 -> 302 -> NULL.
After inserting 164, the list is 141 -> 302 -> 164 -> NULL.
After inserting 530, the list is 141 -> 302 -> 164 -> 530 -> NULL. After inserting 474, the list is 141 -> 302 -> 164 -> 530 -> 474 -> NULL, which is the final list.
Please explain the insertNodeAtTail and add comments to as many code lines as possible. Explain how you added a node at the tail of a linked list.
Why do you have the line SinglyLinkedListNode *tail; ?
What does this line SinglyLinkedListNode *n = new SinglyLinkedListNode(); accomplish?
Can you explain what the lines n->data = data; and n->next = NULL; do? If the head is NULL then why do we need to set head = n? Why are we setting tail = head;? I don't see how tail->next = n; attaches a new node to the last node.
SinglyLinkedListNode* insertNodeAtTail(SinglyLinkedListNode* head, int data) {
SinglyLinkedListNode *n = new SinglyLinkedListNode();
SinglyLinkedListNode *tail;
n->data = data;
n->next = NULL;
if(head == NULL) //empty list
head = n;
else
{
//look for end of list i.e. get hold of last node in list
tail = head;
while(tail->next != NULL)
tail = tail->next;
//attach new node to last node
tail->next = n;
}
return head;
}
Explanation / Answer
Hello Student!
I am happy to help you. I have added the comments as much as possible. If you want to ask something. You can in the comments section.
// Here our function starts
// It consists of two input arguement which are the head of the node and the data to be inserted
SinglyLinkedListNode* insertNodeAtTail(SinglyLinkedListNode* head, int data) {
// *n creates a new node in the linked list Currently, n->next = NULL and n->data is nothing.
SinglyLinkedListNode *n = new SinglyLinkedListNode();
// Here, tail pointer is declared
// Currently no other use of tail pointer is defined
SinglyLinkedListNode *tail;
// data is stored in the n pointer
n->data = data;
// It will point to NULL currently.
n->next = NULL;
// If our list is currently empty i.e. our head is NULL then -
if(head == NULL) //empty list
// Make our new node as the head and return (There must be a return statement here. Please, add it).
head = n;
else
{
//look for end of list i.e. get hold of last node in list
// Now, we need to add the node at the tail of the linked list
// We only have the head pointer. We will currently make our tail pointer to point to the head.
// Now we will traverse till the end of the linked list until we get tail->next as NULL
tail = head;
// Here we will start traversing till the end of the linked list till will encounter NULL.
while(tail->next != NULL)
tail = tail->next;
// Now we have reached the end we will make it point to the new_node which was 'n'
//attach new node to last node
tail->next = n;
}
return head;
}
Why do you have the line SinglyLinkedListNode *tail; ?
Please consider it as a dummy pointer for reaching till the end. We need to insert the element at the end of the linked list and we only have the head pointer. So, we will traverse till the end and once we found the end of the linked list we will add the new node which was 'n' in our code.
What does this line SinglyLinkedListNode *n = new SinglyLinkedListNode(); accomplish?
It is for allocating memory to the pointer you can use statement like malloc as well
Can you explain what the lines n->data = data; and n->next = NULL; do? If the head is NULL then why do we need to set head = n? Why are we setting tail = head;? I don't see how tail->next = n; attaches a new node to the last node.
struct SinglyLinkedListNode {
int data;
SinglyLinkedListNode *next;
};
That's how our struct will look like-
Now we have created 'n'. So it will have two pointers that is data and next
n->data will store the data value which we need to store
n->next will point to NULL currently. If it doesn't then it will make a segmentation fault.
Now, if head is null then we will initialize our new node as head. Because head is needed for the traversal.
We are not exactly settling tail to head, we need our tail pointer to reach till the end. So, we take the starting pointer and move till the end because we cannot directly go to the tail. We need to take the next references.
tail->next = n;
we know after traversal we had tail->next = null
if we add tail->next = n
We will add a new node.
Thank you. Feel free to ask anything. Please upvote, if you like the answer. Thank you again.