3,081 views
27 votes
27 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.

2 Answers

Best answer
52 votes
52 votes

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;
}
edited by
0 votes
0 votes
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

Related questions

3 votes
3 votes
3 answers
3
go_editor asked Feb 8, 2018
1,793 views
Consider the set of relationsEMP (Employee-no. Dept-no, Employee-name, Salary)DEPT (Dept-no. Dept-name, Location)Write an SQL query to:Calculate, for each department numb...