ISRO2018-63

Question

Consider a singly linked list of the form where $F$ is a pointer to the first element in the linked list and $L$ is the pointer to the last element in the list. The time of which of the following operations depends on the length of the list?

1. Delete the last element of the list
2. Delete the first element of the list
3. Add an element after the last element of the list
4. Interchange the first two elements of the list

Answer 1

A. as we need to traverse (n-1) element to delete n^thelement. time taken to do so depends on length of linked list => O(n)

B. Temp=F.

    F=F->NEXT

    FREE(TEMP)

 O(1) and it doesnt depend on the length of list

C.  F->NEXT=TEMP;

     F=TEMP; WHERE TEMP is our new element

D. CONSTANT TIME OPERATION

Ans. Is A

Answer 2

option a)if we delete last node then previous node next part must be null . so we need to traverse the list so it will take o(n) time.

option b,c and D will take o(1) time . it dosent depend upon length of list

Answer 3

Answer : A) Delete the last element of the list

consider an example:-

option A) to delete last element 5 , we need to move from start to second last of the linked list i.e 4 to make it NULL    –  O(N).

option B) delete first element 1, using F(pointer) to make it F=F->NEXT    2->3->4->5->null   – O(1).

option C) add an element after the last element of the list,  suppose to add [6,NULL] , using L (pointer)  L->NEXT=6    – O(1).

option D) interchange the first two elements of the list, 

                TEMP=F->DATA;

                F->DATA=L->DATA

                L->DATA=TEMP,       

                :-O(1)