Answer to Question #198041 in Java | JSP | JSF for David

Question

A. A single linked list provides pointers to the next node in the sequence.

Consider the below structure of the linked list and answer the questions that follow:

Assuming the front is the 1st node and the back is the Nth node, state and explain the running times for the below:

i. Find a node from the front. [2 marks]

ii. Find a node from the back. [2 marks]

iii. Insert a node at the front. [2 marks]

iv. Insert a node at the back. [2 marks]

v. Erase a node from the front. [2 marks]

vi. Erase a node from the back. [2 marks]

Answer 1

1) In this case the pointer moves to the first node, which is the object of the class Node and stores the referrences to the adjacent elements, the previous and the next, and the current item of the parametrized type E. Moving step by step from the current element to the next one using the referrence Node<E> next and comparing the "item" field with the sought element, we can find the index of it or make sure that it is not in the list and return -1.

2) This algorithm is similarly is similar to the previous one excepting that we use the last node as the start point and use the "prev" referrence field moving towards the first element similarly comparing the current item with the sought one and finding its index or lack thereof.

3) When the element is inserted at the front it sets as the first element of the list, the referrence to the ex-first node sets as its next element referrence, or it can be null if the list is still empty, and added element becomes the previous for the ex-first assigning the referrence field "prev".

4) When the element is inserted at the back it sets as the last element of the list, the referrence to the ex-last node sets as its previous element referrence, or it can be null if the list is still empty, it could be the first and the last element at the same time in that case, and added element becomes the next for the ex-last assigning the referrence field "next".

5) When the first element is erased, its next element doesn't points on it as the previous, this referrence field repoints to the header and the second element after the erased becomes the new first element assigning the first element link of the list. There is no more links to the erased element, thus it is no longer a member of the list. It can be picked up by the garbage collector if there is no referrences pointing on it in other places of the code.

6) When the last element is erased, its previous element doesn't points on it as the next one, this referrence field repoints to the header and the element before the erased becomes the new last element assigning the last element link of the list. There is no more links to the erased element, thus it is no longer a member of the list.