How to insert node in Linked list without temp pointer

[Aditya]

Hi All,

I would like to know how it is possible to insert a node in a linked
list without using a temp_pointer. If the element is the first element
then there is no problem but if it is in between then what is the best
solution.

[fred.l.kleinschmidt]

On Jan 3, 7:17*am, Aditya <aditya.to...@g mail.comwrote:

Hi All,

I would like to know how it is possible to insert a node in a linked
list without using a temp_pointer. If the element is the first element
then there is no problem but if it is in between then what is the best
solution.

Why would a temp pointer ever be needed?

To insert node c between a and b:
a->next = c
c->prev = a
c->next = b
b->prev = c
--
Fred Kleinschmidt

[Aditya]

On Jan 3, 4:35*pm, fred.l.kleinsch [e-mail] wrote:

On Jan 3, 7:17*am, Aditya <aditya.to...@g mail.comwrote:

Hi All,

I would like to know how it is possible to insert a node in a linked
list without using a temp_pointer. If the element is the first element
then there is no problem but if it is in between then what is the best
solution.

Why would a temp pointer ever be needed?

To insert node c between a and b:
a->next = c
c->prev = a
c->next = b
b->prev = c
--
Fred Kleinschmidt

Hi ,

It is a Single Link list not a double link list...!

Aditya

[Ben Pfaff]

Aditya <ad**********@g mail.comwrites:

I would like to know how it is possible to insert a node in a linked
list without using a temp_pointer. If the element is the first element
then there is no problem but if it is in between then what is the best
solution.

Pointers can be confusing, so I would write the code to be as
clear as possible. If that involves using a temporary pointer
variable, so be it.
--
Ben Pfaff
http://benpfaff.org

[Gus Gassmann]

On 3 Jan, 15:51, Aditya <aditya.to...@g mail.comwrote:

On Jan 3, 4:35*pm, fred.l.kleinsch [e-mail] wrote:

On Jan 3, 7:17*am, Aditya <aditya.to...@g mail.comwrote:

Hi All,

I would like to know how it is possible to insert a node in a linked
list without using a temp_pointer. If the element is the first element
then there is no problem but if it is in between then what is the best
solution.

Why would a temp pointer ever be needed?

To insert node c between a and b:
a->next = c
c->prev = a
c->next = b
b->prev = c
--
Fred Kleinschmidt

*Hi ,

It is a Single Link list not a double link list...!

Aditya- Hide quoted text -

- Show quoted text -

So what's wrong with
c->next = a->next
a->next = c

[andreyvul]

On Jan 3, 10:51 am, Aditya <aditya.to...@g mail.comwrote:

On Jan 3, 4:35 pm, fred.l.kleinsch [e-mail] wrote:

On Jan 3, 7:17 am, Aditya <aditya.to...@g mail.comwrote:

Hi All,

I would like to know how it is possible to insert a node in a linked
list without using a temp_pointer. If the element is the first element
then there is no problem but if it is in between then what is the best
solution.

Why would a temp pointer ever be needed?

To insert node c between a and b:
a->next = c
c->prev = a
c->next = b
b->prev = c
--
Fred Kleinschmidt

Hi ,

It is a Single Link list not a double link list...!

Aditya

Even simpler:
a->next = c
c->next = b

[Aditya]

We have only start pointer which points to the start of link list say
there are currently 4 nodes in link list a,b,d,e. We need to insert a
node c between b and d .

1.) step would be to create the new node c and temp pointer will point
to the C.

Now tell me how will we insert it

c->next = a->next
a->next = c

above logic will work if we know the address of node a but as we have
only start point then how will be manage this ...?

[spaglia]

On Jan 3, 10:41*am, Aditya <aditya.to...@g mail.comwrote:

We have only start pointer which points to the start of link list say
there are currently 4 nodes in link list a,b,d,e. We need to insert a
node c between b and d .

1.) step would be to create the new node c and temp pointer will point
to the C.

Now tell me how will we insert it

c->next = a->next
a->next = c

above logic will work if we know the address of node a but as we have
only start point then how will be manage this ...?

You have not yet made your question clear. To insert the c node
between b and d you must walk the list untul you get to the b node
then insert with:

c->next = b->next
b->next = c

Are you trying to not walk the list?

Steve

[jxh]

On Jan 3, 10:41*am, Aditya <aditya.to...@g mail.comwrote:

We have only start pointer which points to the start of
link list say there are currently 4 nodes in link list
a,b,d,e. We need to insert a node c between b and d .

1.) step would be to create the new node c and temp
pointer will point to the C.

Now tell me how will we insert it

c->next = a->next
a->next = c

above logic will work if we know the address of node a but
as we have only start point then how will be manage this
...?

Assuming this is an interview question, you should first assert
that in a real program you would do whatever it takes to make sure
the program is written correctly and clearly, which would probably
involve using a temporary.

Second, since a linked list is not a random access data structure,
positional insertion should not be required, since an O(n) search
will be required to retrive the item later anyway, it doesn't
really matter what position it is at. Efficient search retrieval
should be achieved using a data structure that is designed for that
purpose, such as a hash or a search tree.

Understanding that the limitations are being artificially imposed
for the purpose of the interview, you should attempt to get some
clarifications.

How is the point of insertion being communicated to the code
that is being written?

Are you writing a function that is performing an insertion?

Is the list circular?

Does the position of the head matter after the end of the
insertion?

Are multiple passes allowd?

In any case, one possible solution is this:

node *insert (node *head, void *data, unsigned pos)
{
node *n = new_node();
n->next = head;
head = n;
while (pos 0 && n->next) {
n->data = n->next->data;
n = n->next;
--pos;
}
n->data = data;
return head;
}

-- James

[Aditya]

On Jan 4, 2:10*am, jxh <j...@despammed .comwrote:

On Jan 3, 10:41*am, Aditya <aditya.to...@g mail.comwrote:

We have only start pointer which points to the start of
link list say there are currently 4 nodes in link list
a,b,d,e. We need to insert a node c between b and d .

1.) step would be to create the new node c and temp
pointer will point to the C.

Now tell me how will we insert it

c->next = a->next
a->next = c

above logic will work if we know the address of node a but
as we have only start point then how will be manage this
...?

Assuming this is an interview question, you should first assert
that in a real program you would do whatever it takes to make sure
the program is written correctly and clearly, which would probably
involve using a temporary.

Second, since a linked list is not a random access data structure,
positional insertion should not be required, since an O(n) search
will be required to retrive the item later anyway, it doesn't
really matter what position it is at. *Efficient search retrieval
should be achieved using a data structure that is designed for that
purpose, such as a hash or a search tree.

Understanding that the limitations are being artificially imposed
for the purpose of the interview, you should attempt to get some
clarifications.

How is the point of insertion being communicated to the code
that is being written?

Are you writing a function that is performing an insertion?

Is the list circular?

Does the position of the head matter after the end of the
insertion?

Are multiple passes allowd?

In any case, one possible solution is this:

node *insert (node *head, void *data, unsigned pos)
{
* * node *n = new_node();
* * n->next = head;
* * head = n;
* * while (pos 0 && n->next) {
* * * * n->data = n->next->data;
* * * * n = n->next;
* * * * --pos;
* * }
* * n->data = data;
* * return head;

}

-- James

Hi James,

Yes it was an interview question where the things were not cleared to
add confusion.

The solution you had proposed it the best way to deal it.

The question was asked because in the current implementation we were
using an temp pointer to insert a node in the link list so the next
question in interview asked was if we don't allow you to use the temp
pointer then how will you insert the node in the link list.

Now the things are clear ...!

Thanks to all of you who had participated in the discussion.

Aditya