public class HeadList ( Node head: / Points to the first node ot the list ) publ
ID: 3904417 • Letter: P
Question
public class HeadList ( Node head: / Points to the first node ot the list ) public class HeadTailList ( Node head; // Points to the first node of the list Node tail; // Points to the last node of the list h. (1 marks) How do you recognise the last node in a HeadList i. (5 marks) In class HeadList a write a method to add a new node at the end of a HeadList with the following specification: HeadList addToEnd (HeadList list, Node x); // Post: adds x as the last node in list and returns the result Write down the worst case time complexity of your algorithm in terms of the length of the list j. (5 marks) In class HeadTailList write a method to add a new node at the end of a HeadTailList with the following specification HeadTailList addToEnd (HeadTailList 1ist, Node x); // Post: adds x as the last node in list and returns the result Write down the worst case time complexity of your algorithm in terms of the length of the list k. (5 marks) Which type of list out of HeadList and HeadTailList is better for implement- ing a queue data structure? State reasons. (Write no more than 3 lines.)Explanation / Answer
Answers for each questions are explained below.
h. How do you recognize the last node in a HeadList?
Answer: To recognize the last node in a HeadList, we have to iterate through all nodes starting from head node, and if we see a node with no next node (null), we can say that it is the last node.
i. method to add a new node at the end of the HeadList.
Answer: Below is the required code for the method. The time complexity is O(n) as we have to visit all nodes in the list to find the last node.
/**
* method to add a node at the end of the list
*
* @Time complexity: O(n)
* @return - the updated list
*/
HeadList addToEnd(HeadList list, Node x) {
if (list.head == null) {
// first node
list.head = x;
} else {
/**
* looping until the last node
*/
Node tmp = list.head;
while (tmp.next != null) {
tmp = tmp.next;
}
// setting new node as the next node of the last node
tmp.next = x;
}
return list;
}
j. method to add a new node at the end of the HeadTailList.
Answer: Below is the required code for the method. The time complexity is O(1) as we have to check for the tail node only to insert a new node
/**
* method to add a node at the end of the HeadTailList
*
* @Time complexity: O(1)
* @return - the updated list
*/
HeadTailList addToEnd(HeadTailList list, Node x) {
if (list.tail == null) {
// first node
list.head = x;
list.tail = head;
} else {
// we can simply add new node as the next node of the tail
list.tail.next = x;
}
return list;
}
k. Which type of list among the above to is better for a queue data structure?
Answer: The HeadTailList is obviously the better choice as it holds references to the head and tail nodes. So it would be easy to add a node at the end and remove a node from the front and O(1) time complexity.
Hope you are clear. Thanks.
Related Questions
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.