473,246 Members | 1,938 Online
Bytes | Software Development & Data Engineering Community
Post Job

Home Posts Topics Members FAQ

Join Bytes to post your question to a community of 473,246 software developers and data experts.

How to insert node in Linked list without temp pointer

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.

Jan 3 '08 #1
10 10450
On Jan 3, 7:17*am, Aditya <aditya.to...@gmail.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
Jan 3 '08 #2
On Jan 3, 4:35*pm, fred.l.kleinschm...@boeing.com wrote:
On Jan 3, 7:17*am, Aditya <aditya.to...@gmail.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
Jan 3 '08 #3
Aditya <ad**********@gmail.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
Jan 3 '08 #4
On 3 Jan, 15:51, Aditya <aditya.to...@gmail.comwrote:
On Jan 3, 4:35*pm, fred.l.kleinschm...@boeing.com wrote:


On Jan 3, 7:17*am, Aditya <aditya.to...@gmail.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

Jan 3 '08 #5
On Jan 3, 10:51 am, Aditya <aditya.to...@gmail.comwrote:
On Jan 3, 4:35 pm, fred.l.kleinschm...@boeing.com wrote:
On Jan 3, 7:17 am, Aditya <aditya.to...@gmail.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
Jan 3 '08 #6

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 ...?

Jan 3 '08 #7
On Jan 3, 10:41*am, Aditya <aditya.to...@gmail.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

Jan 3 '08 #8
jxh
On Jan 3, 10:41*am, Aditya <aditya.to...@gmail.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
Jan 4 '08 #9
On Jan 4, 2:10*am, jxh <j...@despammed.comwrote:
On Jan 3, 10:41*am, Aditya <aditya.to...@gmail.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
Jan 4 '08 #10
On 3 Jan, 15:17, Aditya <aditya.to...@gmail.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.
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.
Jan 13 '08 #11

This thread has been closed and replies have been disabled. Please start a new discussion.

Similar topics

10
by: Fabio | last post by:
Hi everyone, Is there anybody who can suggest me a link where I can find information about 'Persistent linked list' ? I need to implement a linked list where every node is a structure like the...
8
by: farhanb | last post by:
hello, I am writing a simple linked list implementation. When I use function insert1 I must allocate to head in my main to get it to work otherwise list stays empty but when I use function...
3
by: chellappa | last post by:
hi this simple sorting , but it not running...please correect error for sorting using pointer or linked list sorting , i did value sorting in linkedlist please correct error #include<stdio.h>...
13
by: XXXXXX.working.in.my.blood | last post by:
hi all, i need help with linked lists... the problem is this, "reverse the contents of a singly linked list without using a temporary node"... solution with code will be appreciated...
5
by: Y2J | last post by:
I am working through this book on C++ programming, the author is speaking of using linked lists. He gave and example which I found confusing to say the least. So I rewrote the example in a way that...
6
by: Baltazar007 | last post by:
Does anyone know how to make quicksort for single linked list without using array? I know that mergesort is maybe better but I need quicksort!! thnx
10
by: AZRebelCowgirl73 | last post by:
This is what I have so far: My program! import java.util.*; import java.lang.*; import java.io.*; import ch06.lists.*; public class UIandDB {
5
by: WarmDismalAgony | last post by:
hey, can anyone figure out why this insert function is setting all nodes in the list to have the same item? void insert_list (list_ref list, list_item item) { listnode_ref new = malloc...
0
by: Atos | last post by:
SINGLE-LINKED LIST Let's start with the simplest kind of linked list : the single-linked list which only has one link per node. That node except from the data it contains, which might be...
0
by: stefan129 | last post by:
Hey forum members, I'm exploring options for SSL certificates for multiple domains. Has anyone had experience with multi-domain SSL certificates? Any recommendations on reliable providers or specific...
1
by: davi5007 | last post by:
Hi, Basically, I am trying to automate a field named TraceabilityNo into a web page from an access form. I've got the serial held in the variable strSearchString. How can I get this into the...
0
by: MeoLessi9 | last post by:
I have VirtualBox installed on Windows 11 and now I would like to install Kali on a virtual machine. However, on the official website, I see two options: "Installer images" and "Virtual machines"....
0
by: DolphinDB | last post by:
The formulas of 101 quantitative trading alphas used by WorldQuant were presented in the paper 101 Formulaic Alphas. However, some formulas are complex, leading to challenges in calculation. Take...
0
by: DolphinDB | last post by:
Tired of spending countless mintues downsampling your data? Look no further! In this article, you’ll learn how to efficiently downsample 6.48 billion high-frequency records to 61 million...
0
by: Aftab Ahmad | last post by:
Hello Experts! I have written a code in MS Access for a cmd called "WhatsApp Message" to open WhatsApp using that very code but the problem is that it gives a popup message everytime I clicked on...
0
isladogs
by: isladogs | last post by:
The next Access Europe meeting will be on Wednesday 6 Mar 2024 starting at 18:00 UK time (6PM UTC) and finishing at about 19:15 (7.15PM). In this month's session, we are pleased to welcome back...
0
by: marcoviolo | last post by:
Dear all, I would like to implement on my worksheet an vlookup dynamic , that consider a change of pivot excel via win32com, from an external excel (without open it) and save the new file into a...
0
isladogs
by: isladogs | last post by:
The next Access Europe meeting will be on Wednesday 6 Mar 2024 starting at 18:00 UK time (6PM UTC) and finishing at about 19:15 (7.15PM). In this month's session, we are pleased to welcome back...

By using Bytes.com and it's services, you agree to our Privacy Policy and Terms of Use.

To disable or enable advertisements and analytics tracking please visit the manage ads & tracking page.