Log In
7 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^{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 by
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)$.

3 Answers

20 votes
Best answer

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

1. Y->next = X-> next

2. X->next = Y

edited by

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*}$

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.

Related questions

15 votes
2 answers
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.
asked Sep 30, 2014 in DS Kathleen 921 views
15 votes
2 answers
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
asked Sep 30, 2014 in DS Kathleen 1.7k views
38 votes
9 answers
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)$
asked Nov 2, 2014 in DS Ishrat Jahan 6.9k views
4 votes
1 answer
The following relations are used to store data about students, courses, enrollment of students in courses and teachers of courses. Attributes for primary key in each relation are marked by *'. Students (rollno*, sname, saddr) courses (cno*, cname) enroll(rollno*, cno*, grade) teach ... )? If yes, prove that it is in 3 NF. If not normalize, the relations so that they are in 3NF (without proving)?
asked Feb 5, 2018 in Databases jothee 587 views