The Gateway to Computer Science Excellence
+20 votes
702 views
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 by Veteran (431k points) | 702 views
+20
// 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;
}
	
0
good one @ mcjoshi

1 Answer

+34 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\_D.next \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 = p.data$
$p.data= p.next.data$
$p.next.data= 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;
}
by Veteran (60.9k points)
edited by
+1
Your logic is awesome ! Try for part a too !
+2

I think instead of this:

PnextAddress_of_D
Address_of_D.nextAddress_of_F

this should be there:

Address_of_D.nextAddress_of_F

PnextAddress_of_D

–1
Wat a soluchan :p  =D

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,737 questions
57,321 answers
198,394 comments
105,144 users