Log In
22 votes
Write a constant time algorithm to insert a node with data $D$ just before the node with address $p$ of a singly linked list.
in DS 1.2k views
// node is a struct containing an int and next pointer
void insert(int D, node* p){
	node* temp = (node*)malloc(sizeof(node));
	temp->next = p->next; // make temp point to the node where p was pointing
	p->next = temp; // attach node temp next to node p 
	/*till this point it is simialr to inserting node after a node
	whose pointer p is given. Now change the data of both nodes p and temp to get desired result*/
	temp->data = p->data; // copy the data of current node to new node
	p->data = D;
good one @ mcjoshi

2 Answers

39 votes
Best answer

Let $A,B,C,D,E,F$ be the data.
$A \rightarrow B \rightarrow C \rightarrow E  \rightarrow F$

Let pointer to $E$ be $p$.

A node with data $D$ has to be inserted before $E$.
I'll do one thing - add $D$ just after node $E$ and it'll take constant time.
$p.{next} \rightarrow Address\_of\_D$
$Address\_of\ \rightarrow Address\_of\_F$

$A \rightarrow B \rightarrow C \rightarrow E \rightarrow D \rightarrow F$

Take a temporary variable and swap the values $E$ and $D$..
$temp =$
$ temp$

Now linked list wil look like
$A \rightarrow B \rightarrow C \rightarrow D \rightarrow E  \rightarrow F$
still one more work left - now pointer $p$ pointing to $D$ so increment pointer $p$ to point data $E$.
$p= p \rightarrow next$

void InsertBeforeGivenPointer(struct node* p, int D){
	struct node* temp = (node*)malloc(sizeof(struct node));
	temp->next = p->next;
	p->next = temp;
	temp->data = p->data;
	p->data = D;

edited by
Your logic is awesome ! Try for part a too !

I think instead of this:


this should be there:



Wat a soluchan :p  =D

This will also work if p is pointing to last node?
0 votes
Suppose initially we have LL : A,B,C

p points to B

new node: B1


B1->next = p->next;

p->next = B1


This will give the LL: A,B,B1,C

Now swap the values of B and B1

temp = p->value

p->value = B1->value


This will make the LL: A,B1,B,C

Related questions

17 votes
3 answers
In binary tree, a full node is defined to be a node with $2$ children. Use induction on the height of the binary tree to prove that the number of full nodes plus one is equal to the number of leaves. Draw the min-heap that results from insertion of the following elements in order into an initially empty min-heap: $7, 6, 5, 4, 3, 2, 1$. Show the result after the deletion of the root of this heap.
asked Sep 24, 2014 in DS Kathleen 2.1k views
4 votes
4 answers
Consider the following solution to the producer-consumer problem using a buffer of size 1. Assume that the initial value of count is 0. Also assume that the testing of count and assignment to count are atomic operations. Producer: Repeat Produce an item; if count = ... Producer); Consume item; Forever; Show that in this solution it is possible that both the processes are sleeping at the same time.
asked Feb 28, 2018 in Operating System jothee 1.2k views
2 votes
3 answers
Consider the set of relations EMP (Employee-no. Dept-no, Employee-name, Salary) DEPT (Dept-no. Dept-name, Location) Write an SQL query to: Calculate, for each department number, the number of employees with a salary greater than Rs. 1,00,000
asked Feb 8, 2018 in Databases jothee 568 views
13 votes
4 answers
Mr. X claims the following: If a relation R is both symmetric and transitive, then R is reflexive. For this, Mr. X offers the following proof: “From xRy, using symmetry we get yRx. Now because R is transitive xRy and yRx together imply xRx. Therefore, R is reflexive”. Give an example of a relation R which is symmetric and transitive but not reflexive.
asked Sep 24, 2014 in Set Theory & Algebra Kathleen 1.4k views