The Gateway to Computer Science Excellence
+7 votes
862 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 by Veteran (52.2k points)
recategorized by | 862 views

3 Answers

+19 votes
Best answer

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

1. Y->next = X-> next

2. X->next = Y

by Boss (23.8k points)
edited by
+3

d->next = dj->next

dj->next = d

+9 votes

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

by Boss (30.7k points)
0 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.

by (13 points)

Related questions

Quick search syntax
tags tag:apple
author user:martin
title title:apple
content content:apple
exclude -tag:apple
force match +apple
views views:100
score score:10
answers answers:2
is accepted isaccepted:true
is closed isclosed:true
50,647 questions
56,459 answers
195,378 comments
100,274 users