GATE CSE 1999 | Question: 11b

Question

Write a constant time algorithm to insert a node with data $D$ just before the node with address $p$ of a singly linked list.

Comments

// 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

---

It’s better than the best answer because in the best answer, instead of inserting a node before a node with address “p”, we are changing the address “p” itself.but this ans feels perfect.

Answer 1

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

Let the 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} = D_{addr}$
$D_{addr}→ next = F_{addr}$

$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 will 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;
}

Comments

@srestha

This will also work if p is pointing to last node?

---

As per question, a new node whose data is D have to insert before a node whose address is p. But you just insert the new node as the next node of p and copied the data D at the node whose address is p. Still address p comes before new node. but address p should come after new node or data D comes before address p..

Correct code should be:

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

Any comment ??

---

Such nice logic

Answer 2

Suppose initially we have LL : A,B,C

p points to B

new node: B1

Now,

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

B1→value=temp

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