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.
On Jan 3, 7:17 am, Aditya <aditya.to...@gmail.com> wrote:
> 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
> On Jan 3, 7:17 am, Aditya <aditya.to...@gmail.com> wrote:
> > 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 <aditya.to...@gmail.com> writes: > 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
> On Jan 3, 4:35 pm, fred.l.kleinschm...@boeing.com wrote:
> > On Jan 3, 7:17 am, Aditya <aditya.to...@gmail.com> wrote:
> > > 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
> On Jan 3, 4:35 pm, fred.l.kleinschm...@boeing.com wrote:
> > On Jan 3, 7:17 am, Aditya <aditya.to...@gmail.com> wrote:
> > > 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...!
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 ...?
On Jan 3, 10:41 am, Aditya <aditya.to...@gmail.com> wrote:
> 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:
On Jan 3, 10:41 am, Aditya <aditya.to...@gmail.com> wrote:
> 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?
> On Jan 3, 10:41 am, Aditya <aditya.to...@gmail.com> wrote:
> > 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?
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.
On 3 Jan, 15:17, Aditya <aditya.to...@gmail.com> wrote:
> 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.
|
