TIFR CSE 2021 | Part B | Question: 2

Question

Let $L$ be a singly-linked list $X$ and $Y$ be additional pointer variables such that $X$ points to the first element of $L$ and $Y$ points to the last element of $L$. Which of the following operations cannot be done in time that is bound above by a constant?

• A. Delete the first element of $L$.
• B. Delete the last element of $L$.
• C. Add an element after the last element of $L$.
• D. Add an element before the first element of $L$.
• E. Interchange the first two elements of $L$.

Comments

answer is B .

if we want to delete last element then we have  to find the 2^nd last element by which all things settle down as earlier (AFTER DELETION) so we required N-1 comparisons, for  that required O(n).

Answer 1

$(A)$
$ Y \to next = Y \to next \to next$
$X = Y \to next$

$(C)$
$temp = \text{(int *)(malloc(sizeof(int)))}$
$temp \to data = val$
$temp \to next = X$
$Y \to next = temp$
$Y = temp$

$(D)$
$temp = \text{(int *)(malloc(sizeof(int)))}$
$temp \to data = val$
$temp \to next = X$
$Y \to next = temp$
$X = temp$

$(E)$
$temp = X \to next \to data$
$X \to next \to data = X \to data$
$X \to data = temp$

 

Now, let's look at the Part $(B)$
Let’s copy the data of $X$ in $Y$ and then delete $X$.

$Y \to data = X \to data$
$Y \to next = X \to next$
$X = Y$

Now we need to point $Y$ to the previous node of the newly set $X$. How do we do that in constant time?
For that, we need to iterate starting from $X$ to the last node which will take $O(n)$ time where $n$ is the number of nodes in the list.

So, the answer should be $(B)$