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]

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

 

[Aditya]

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

Hi ,

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

Aditya

 

[Ben Pfaff]

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.

 

[Gus Gassmann]

 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]

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]

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]

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]

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

 

[gw7rib]

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.

From what you have said elsethread, I think what the interviewer may
have been looking for is something like the following trick:

Question:
Given a singly linked list, a pointer to a node a in the list, and a
pointer to a new node n, but no other information, how do you insert
node n before node a in the list?

First thoughts:
This is impossible. You need to find the node before a in the list,
and there is no way to do this if you aren't given a pointer to the
start of the list (or at least, to a node somewhere before a in the
list). Indeed, if a is the first node in the list, you need to be able
to change the pointer to the start of the list (to get it to point to
n).

"Solution":
However, one way of achieving a similar result is as follows. You swap
a and n's data over. Then you add node n (which now has a's data)
after a in the list. Result - the new list has a node with n's data
before a node with a's data. This however is not quite the same as
simply inserting node n before node a - any pointers which pointed to
node a before you started will now be pointing to node n's data
instead.

This technique can be used with similar questions. For instance,
suppose you are given the start of the list - but you are told that
you have to do the insertion in constant time, meaning that you don't
have time to "walk" the list to find the node before a. Or, you could
be told you cannot use any pointers other than the ones to a and n.
This latter question may be the one you were asked.

Hope this is helpful.
Paul.