# GATE1993-13

1.1k views
Consider a singly linked list having $n$ nodes. The data items $d_1, d_2, \dots d_n$ are stored in these $n$ nodes. Let $X$ be a pointer to the $j^{th}$ node $(1 \leq j \leq n)$ in which $d_j$ is stored. A new data item $d$ stored in node with address $Y$ is to be inserted. Give an algorithm to insert $d$ into the list to obtain a list having items $d_1, d_2, \dots, d_{j}, d,\dots, d_n$ in order without using the header.
in DS
recategorized
0
Generally we don't have a pointer to the node after which we wish to insert a new node, which is given to us here. Without this pointer the time complexity becomes $O(n)$ because the worst case is end-of-list insertion. With it, the time becomes $O(1)$.

Following $2$ lines are enough to realise above constraint :->>

1. Y->next = X-> next 2. X->next = Y

edited by
3

d->next = dj->next

dj->next = d

these steps are mandatory for the algorithm :
\begin{align*} temp &= X \rightarrow next\\ X \rightarrow next &= Y \\ Y \rightarrow next &= temp \end{align*}

As one can notice all the answers given are trying to insert d at (j+1)th index instead of jth index as asked in the question ( see the position of d in the sequence given in last line).

I have used the following approach.

## Related questions

1
921 views
Prove by the principal of mathematical induction that for any binary tree, in which every non-leaf node has $2$-descendants, the number of leaves in the tree is one more than the number of non-leaf nodes.
The following Pascal program segments finds the largest number in a two-dimensional integer array $A[0\dots n-1, 0\dots n-1]$ using a single loop. Fill up the boxes to complete the program and write against $\fbox{A}, \fbox{B}, \fbox{C} \text{ and } \fbox{D}$ in your answer book Assume that max is ... begin if A[i, j]>max then max:=A[i, j]; if |C| then j:=j+1; else begin j:=0; i:=|D| end end end
Let $P$ be a singly linked list. Let $Q$ be the pointer to an intermediate node $x$ in the list. What is the worst-case time complexity of the best-known algorithm to delete the node $x$ from the list ? $O(n)$ $O(\log^2 n)$ $O(\log n)$ $O(1)$