Hi all,
Please clarify the following piece of code:
<CODE>
/* delete node containing i from list pointed to by lp */
struct list *lp, *prevlp;
for(lp = list; lp != NULL; lp = lp->next)
{
if(lp->item == i)
{
if(lp == list) //Confusion!!
list = lp->next;
else prevlp->next = lp->next;
break;
}
prevlp = lp;
}
}
</CODE>
found at http://www.eskimo.com/~scs/cclass/int/sx8.html
I have a confusion as to what is meant by `list' in the `if' statement.
That appears to me to be a typo...
Regards
Suman 14 1350
suman kar wrote: Hi all,
Please clarify the following piece of code: <CODE> /* delete node containing i from list pointed to by lp */
struct list *lp, *prevlp; for(lp = list; lp != NULL; lp = lp->next)
^^^^^^^^ { if(lp->item == i) { if(lp == list) //Confusion!!
do not use line comments in newsgroups! list = lp->next; else prevlp->next = lp->next; break; } prevlp = lp; } } </CODE>
found at http://www.eskimo.com/~scs/cclass/int/sx8.html
I have a confusion as to what is meant by `list' in the `if' statement. That appears to me to be a typo...
First: I have not looked at the URL but that seems not to be
necessary.
Unfortunately, you seem to have snipped the part where the identifier
"list" comes in. Note that there can be a variable "list" because
the name spaces of tags (struct list) and variables (assumed here:
struct list *list) do not clash.
The "list" in the if statement is exactly the same "list" as in the
part marked by me (lp = list).
If this confuses you, replace it by, say, "first".
Reason: "list" seems to be the start of a linked list.
If we eliminate some list node, we link its predecessor to its
successor -- unless it is the first node which has no predecessor;
in this case, we say the successor of the node to be deleted is the
new first node of the list.
Cheers
Michael
--
E-Mail: Mine is an /at/ gmx /dot/ de address.
Michael Mair <in*****@invalid.invalid> wrote in message news:<2v*************@uni-berlin.de>... suman kar wrote:
Hi all,
Please clarify the following piece of code: <CODE> /* delete node containing i from list pointed to by lp */
struct list *lp, *prevlp; for(lp = list; lp != NULL; lp = lp->next) ^^^^^^^^ { if(lp->item == i) { if(lp == list) > do not use line comments in newsgroups! list = lp->next; else prevlp->next = lp->next; break; } prevlp = lp; } } </CODE>
found at http://www.eskimo.com/~scs/cclass/int/sx8.html
I have a confusion as to what is meant by `list' in the `if' statement. That appears to me to be a typo...
First: I have not looked at the URL but that seems not to be necessary.
Unfortunately, you seem to have snipped the part where the identifier "list" comes in. Note that there can be a variable "list" because the name spaces of tags (struct list) and variables (assumed here: struct list *list) do not clash. The "list" in the if statement is exactly the same "list" as in the part marked by me (lp = list). If this confuses you, replace it by, say, "first".
Ignorance, sheer ignorance on my part.I was really thinking
of something on the lines of :
int int;
which of course is not legal. Reason: "list" seems to be the start of a linked list. If we eliminate some list node, we link its predecessor to its successor -- unless it is the first node which has no predecessor; in this case, we say the successor of the node to be deleted is the new first node of the list.
Cheers Michael
This part(you were correct as to what `list' is doing) is ok.
One more thing, possibly OT,
given the address of a particular node in a singly linked list, is it
possible to delete that element from the list without traversing the
list?
Not exactly homework but was put across in an interview.The
interviewer is
supposed to have said something regarding memory copying required to
do this.
Since I was not the one on the wrong side of the table I am unable to
give you
the interviewer's solution verbatim.Also I am curious as to know if
any such thing is possible.Lists are not given contiguous blocks of
memory so memory copying can't help us out here.
You can choose to ignore my query so vaguely described and also the
fact that
I apparently did not put much effort to solve it ;-)But then I am an
optimist...
Thanks a lot for the express response.
Regards
Suman.
suman kar wrote: This part(you were correct as to what `list' is doing) is ok.
One more thing, possibly OT, given the address of a particular node in a singly linked list, is it possible to delete that element from the list without traversing the list? Not exactly homework but was put across in an interview.The interviewer is supposed to have said something regarding memory copying required to do this. Since I was not the one on the wrong side of the table I am unable to give you the interviewer's solution verbatim.Also I am curious as to know if any such thing is possible.Lists are not given contiguous blocks of memory so memory copying can't help us out here.
You can choose to ignore my query so vaguely described and also the fact that I apparently did not put much effort to solve it ;-)But then I am an optimist...
It is possible. Let us first consider the whole thing in the
array context:
| a[0] | a[1] | ... | a[i] | a[i+1] | ... | a[size-1] |
If we want to get rid of a[i] we can memmove() (size-i-1)*sizeof a[0]
bytes starting at &a[i+1] to &a[i].
Of course, we can also do it by hand:
for (k=i;k<size;k++)
a[k] = a[k+1];
Both give us
| a[0] | a[1] | ... | a[i-1] | "a[i+1]" | ... | "a[size-1]" |
where "a[i+1]" means "formerly a[i+1]".
Then, you can of course do the same with the list:
next = lp->next;
while (next!=NULL) {
memcpy(lp,lp->next, sizeof *lp);
lp->next = next;
}
(Untested)
Nonetheless, this makes not much sense as usually the size of a
node is too large for this to be efficient.
Cheers
Michael
--
E-Mail: Mine is a gmx dot de address.
Michael Mair wrote: suman kar wrote:
This part(you were correct as to what `list' is doing) is ok.
One more thing, possibly OT, given the address of a particular node in a singly linked list, is it possible to delete that element from the list without traversing the list? Not exactly homework but was put across in an interview.The interviewer is supposed to have said something regarding memory copying required to do this. Since I was not the one on the wrong side of the table I am unable to give you the interviewer's solution verbatim.Also I am curious as to know if any such thing is possible.Lists are not given contiguous blocks of memory so memory copying can't help us out here.
You can choose to ignore my query so vaguely described and also the fact that I apparently did not put much effort to solve it ;-)But then I am an optimist...
It is possible. Let us first consider the whole thing in the array context:
| a[0] | a[1] | ... | a[i] | a[i+1] | ... | a[size-1] |
If we want to get rid of a[i] we can memmove() (size-i-1)*sizeof a[0] bytes starting at &a[i+1] to &a[i]. Of course, we can also do it by hand: for (k=i;k<size;k++) a[k] = a[k+1];
Both give us | a[0] | a[1] | ... | a[i-1] | "a[i+1]" | ... | "a[size-1]" | where "a[i+1]" means "formerly a[i+1]".
Then, you can of course do the same with the list:
next = lp->next; while (next!=NULL) { memcpy(lp,lp->next, sizeof *lp); lp->next = next;
Forgot the increment, sorry:
lp = next;
next = lp->next; }
(Untested) Nonetheless, this makes not much sense as usually the size of a node is too large for this to be efficient.
Cheers Michael
--
E-Mail: Mine is a gmx dot de address.
suman kar wrote: Michael Mair <in*****@invalid.invalid> wrote in message news:<2v*************@uni-berlin.de>... suman kar wrote:
Hi all,
Please clarify the following piece of code: <CODE> /* delete node containing i from list pointed to by lp */
struct list *lp, *prevlp; for(lp = list; lp != NULL; lp = lp->next) ^^^^^^^^ { if(lp->item == i) { if(lp == list) > do not use line comments in newsgroups! list = lp->next; else prevlp->next = lp->next; break; } prevlp = lp; } } </CODE>
found at http://www.eskimo.com/~scs/cclass/int/sx8.html
I have a confusion as to what is meant by `list' in the `if' statement. That appears to me to be a typo...
First: I have not looked at the URL but that seems not to be necessary.
Unfortunately, you seem to have snipped the part where the identifier "list" comes in. Note that there can be a variable "list" because the name spaces of tags (struct list) and variables (assumed here: struct list *list) do not clash. The "list" in the if statement is exactly the same "list" as in the part marked by me (lp = list). If this confuses you, replace it by, say, "first".
Ignorance, sheer ignorance on my part.I was really thinking of something on the lines of : int int; which of course is not legal.
Reason: "list" seems to be the start of a linked list. If we eliminate some list node, we link its predecessor to its successor -- unless it is the first node which has no predecessor; in this case, we say the successor of the node to be deleted is the new first node of the list.
Cheers Michael
This part(you were correct as to what `list' is doing) is ok.
One more thing, possibly OT, given the address of a particular node in a singly linked list, is it possible to delete that element from the list without traversing the list?
For a double linked list, it's very simple.
link -> prev -> next = link -> next
link -> next -> prev = link -> prev
The you can either free the link's data and the link,
or do something else with the link.
For a single linked list,
you somehow need to find the address of the previous link,
so you can do
previous_link -> next = list -> next
--
pete
Michael Mair wrote: Then, you can of course do the same with the list:
next = lp->next; while (next!=NULL) { memcpy(lp,lp->next, sizeof *lp); lp->next = next; }
(Untested) Nonetheless, this makes not much sense as usually the size of a node is too large for this to be efficient.
It's easier than that. Just overwrite the node to be deleted with a
copy of the following one (*without* adjusting its 'next' pointer) and
free the original, and you're done. (Think about where the pointer
still points...)
--
chris th******@yahoo.co.uk wrote: Michael Mair wrote:
Then, you can of course do the same with the list:
next = lp->next; while (next!=NULL) { memcpy(lp,lp->next, sizeof *lp); lp->next = next; }
(Untested) Nonetheless, this makes not much sense as usually the size of a node is too large for this to be efficient.
It's easier than that. Just overwrite the node to be deleted with a copy of the following one (*without* adjusting its 'next' pointer) and free the original, and you're done. (Think about where the pointer still points...)
*hitsforehead* Ouch!
Thank you very much for pointing that out... Must have sat on the
energy supply for the gray stuff :-)
Cheers
Michael
--
E-Mail: Mine is a gmx dot de address. th******@yahoo.co.uk wrote in message news:<10**********************@c13g2000cwb.googleg roups.com>... Michael Mair wrote:
Then, you can of course do the same with the list:
next = lp->next; while (next!=NULL) { memcpy(lp,lp->next, sizeof *lp); lp->next = next; }
(Untested) Nonetheless, this makes not much sense as usually the size of a node is too large for this to be efficient.
It's easier than that. Just overwrite the node to be deleted with a copy of the following one (*without* adjusting its 'next' pointer) and free the original, and you're done. (Think about where the pointer still points...)
Thanks a zillion tonnes to Michael and Chris!
I was thinking more on the lines of Chris, though.
Regards,
Suman.
On Mon, 08 Nov 2004 07:57:07 -0800, thorpecp wrote: Michael Mair wrote:
Then, you can of course do the same with the list:
next = lp->next; while (next!=NULL) { memcpy(lp,lp->next, sizeof *lp); lp->next = next; }
(Untested) Nonetheless, this makes not much sense as usually the size of a node is too large for this to be efficient.
It's easier than that. Just overwrite the node to be deleted with a copy of the following one (*without* adjusting its 'next' pointer) and free the original, and you're done. (Think about where the pointer still points...)
But consider cases where this will fail. E.g. when the node is the last in
the list, or if there are pointers to list nodes held elsewhere by the
program; having list nodes stay at the same location for their lifetime is
a typical and sometimes useful property of a linked list. The normal
solution to the stated problem is a doubly linked list.
Lawrence Kirby wrote: On Mon, 08 Nov 2004 07:57:07 -0800, thorpecp wrote:
Michael Mair wrote:
Then, you can of course do the same with the list:
next = lp->next; while (next!=NULL) { memcpy(lp,lp->next, sizeof *lp); lp->next = next; }
(Untested) Nonetheless, this makes not much sense as usually the size of a node is too large for this to be efficient. It's easier than that. Just overwrite the node to be deleted with a copy of the following one (*without* adjusting its 'next' pointer) and free the original, and you're done. (Think about where the pointer still points...)
But consider cases where this will fail. E.g. when the node is the last in the list,
This is uncritical -- a SecondToLast node pointer can be afforded
in exchange for the advantage of having not to run through the list...
or if there are pointers to list nodes held elsewhere by the program; having list nodes stay at the same location for their lifetime is a typical and sometimes useful property of a linked list.
I think this really is a reason to do it the right way...
BTW: My inferior code makes this bug source easier to find ;-)
The normal solution to the stated problem is a doubly linked list.
Indubitably correct. If the data a node contains is not "large enough",
the additional pointer gives a noticeable increase in memory cost,
though. It's the old problem: We would like to ideally have an array
with the advantages of a doubly linked list... :-)
As for the problem: It was more a question of whether it is possible
than whether it is sensible. The answer to the former is "yes" and
the latter gives us the ", but ..."
Cheers
Michael
--
E-Mail: Mine is a gmx dot de address.
On Wed, 10 Nov 2004 17:16:05 +0100, Michael Mair wrote:
Lawrence Kirby wrote: On Mon, 08 Nov 2004 07:57:07 -0800, thorpecp wrote:
....
But consider cases where this will fail. E.g. when the node is the last in the list,
This is uncritical -- a SecondToLast node pointer can be afforded in exchange for the advantage of having not to run through the list...
How will you update that pointer to point to the new second-to-last node
(assuming there is one) when the last node is removed?
Lawrence
Lawrence Kirby wrote: On Wed, 10 Nov 2004 17:16:05 +0100, Michael Mair wrote:
Lawrence Kirby wrote:
On Mon, 08 Nov 2004 07:57:07 -0800, thorpecp wrote:
...
But consider cases where this will fail. E.g. when the node is the last in the list,
This is uncritical -- a SecondToLast node pointer can be afforded in exchange for the advantage of having not to run through the list...
How will you update that pointer to point to the new second-to-last node (assuming there is one) when the last node is removed?
Today really is not my day...
Of course you have to run through the list for getting rid of the
last node.
Thanks :-)
Cheers
Michael
--
E-Mail: Mine is an /at/ gmx /dot/ de address.
On Wed, 10 Nov 2004, Michael Mair wrote: Lawrence Kirby wrote:
On Wed, 10 Nov 2004 17:16:05 +0100, Michael Mair wrote:
Lawrence Kirby wrote:
But consider cases where this will fail. E.g. when the node is the last in the list,
This is uncritical -- a SecondToLast node pointer can be afforded in exchange for the advantage of having not to run through the list...
How will you update that pointer to point to the new second-to-last node (assuming there is one) when the last node is removed?
Today really is not my day... Of course you have to run through the list for getting rid of the last node. Thanks :-)
You don't need to run through the list to get rid of the
last node--if you pad the list with a `special' node at the end:
+-----------+ next +-----------+ next
| last node | ----> | `special' | ----> NULL
+-----------+ +-----------+
then you can use memcpy(node, node->next, sizeof *node) to remove
any node, including the last. Obviously, the list traversal
algorithm would have to change (to hide the `special' node):
for (p = list; (q = p->next) != NULL; p = q)
do_great_things_with(p);
Tak-Shing
Tak-Shing Chan wrote: then you can use memcpy(node, node->next, sizeof *node) to remove any node, including the last.
You don't like the assignment operator for that?
*node = *node->next;
--
pete This thread has been closed and replies have been disabled. Please start a new discussion. Similar topics
by: Rich S. |
last post by:
Hello
Just like everyone else, I am excited about how easily one can create Windows applications with the .NET platform, but for shareware, I have some serious reservations
1. Your code can be...
|
by: Peter |
last post by:
Hi:
I am bored and was wondering:
Is it
a html page?
or
|
by: sathya |
last post by:
Q. Write a program to print all input lines that are longer than 80
characters.
Code taken from
http://users.powernet.co.uk/eton/kandr2/krx117.html
...
|
by: maadhuu |
last post by:
#include<stdio.h>
#include<conio.h>
#include<string.h>
main()
{
char * a= "bcd";
clrscr();
strcpy(a,"hello");
a = "fgh";
a = 't';
|
by: siaj |
last post by:
Hello,
I am trying to put a very simple animation on a page. I want two images to
show alternately in a defined area. I tried to have an image control and a
timer control on a page. I am setting...
|
by: Pradeep |
last post by:
Hi,
i have got a couple of doubts, which r:
1) Is there any way to use my existing vb code (or Vb's Dll) in asp.net
2) Where is the IntelliSense information stored ?
3) Actually i m saving data...
|
by: =?Utf-8?B?U2FjaGluIFNha2k=?= |
last post by:
I have asp application, from which I am redirecting user to .aspx page. I
want to use same sessions in .aspx application. When User clicks on Browsers
back button i.e. comes back from .aspx page to...
|
by: eBob.com |
last post by:
I have a print application modeled on a program which I found via this
newsgroup. (I still have comments in German in it!) The model uses
ExtendedPrintPreviewDialog but I don't seem to have that...
|
by: pallabi sarangi |
last post by:
my requirement is in a default page, for login,there r 3 fields as userid,password n state(which is in a dropdown form).By default,all the texttexts of india should be displayed.so,when a user l...
|
by: Sonnysonu |
last post by:
This is the data of csv file
1 2 3
1 2 3
1 2 3
1 2 3
2 3
2 3
3
the lengths should be different i have to store the data by column-wise with in the specific length.
suppose the i have to...
|
by: Hystou |
last post by:
Most computers default to English, but sometimes we require a different language, especially when relocating. Forgot to request a specific language before your computer shipped? No problem! You can...
|
by: Oralloy |
last post by:
Hello folks,
I am unable to find appropriate documentation on the type promotion of bit-fields when using the generalised comparison operator "<=>".
The problem is that using the GNU compilers,...
|
by: jinu1996 |
last post by:
In today's digital age, having a compelling online presence is paramount for businesses aiming to thrive in a competitive landscape. At the heart of this digital strategy lies an intricately woven...
|
by: tracyyun |
last post by:
Dear forum friends,
With the development of smart home technology, a variety of wireless communication protocols have appeared on the market, such as Zigbee, Z-Wave, Wi-Fi, Bluetooth, etc. Each...
|
by: isladogs |
last post by:
The next Access Europe User Group meeting will be on Wednesday 1 May 2024 starting at 18:00 UK time (6PM UTC+1) and finishing by 19:30 (7.30PM).
In this session, we are pleased to welcome a new...
|
by: TSSRALBI |
last post by:
Hello
I'm a network technician in training and I need your help.
I am currently learning how to create and manage the different types of VPNs and I have a question about LAN-to-LAN VPNs.
The...
|
by: adsilva |
last post by:
A Windows Forms form does not have the event Unload, like VB6. What one acts like?
|
by: 6302768590 |
last post by:
Hai team
i want code for transfer the data from one system to another through IP address by using C# our system has to for every 5mins then we have to update the data what the data is updated ...
| |