recategorized by
3,594 views
14 votes
14 votes
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^{\text{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.
recategorized by

4 Answers

Best answer
33 votes
33 votes

Following $2$ lines are enough to realize above constraint :

  1. Y->next = X-> next
  2. X->next = Y
edited by
10 votes
10 votes

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

2 votes
2 votes

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

19 votes
19 votes
2 answers
1
Kathleen asked Sep 29, 2014
2,897 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 ...
30 votes
30 votes
4 answers
4
Kathleen asked Sep 29, 2014
4,524 views
Let $\left(\{ p,q \},*\right)$ be a semigroup where $p*p=q$. Show that:$p*q=q*p$ and$q*q=q$