Doubts:Steve Summit's page/Chapter 22

[suman kar]

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

 

[Michael Mair]

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

 

[suman kar]

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.

 

[Michael Mair]

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 | a[i+1] | ... | a[size-1] |

If we want to get rid of a we can memmove() (size-i-1)*sizeof a[0]
bytes starting at &a[i+1] to &a.
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

 

[Michael Mair]

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 | a[i+1] | ... | a[size-1] |

If we want to get rid of a we can memmove() (size-i-1)*sizeof a[0]
bytes starting at &a[i+1] to &a.
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;

 

[pete]

Ignorance, sheer ignorance on my part.I was really thinking
of something on the lines of :
int int;
which of course is not legal.


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

 

[thorpecp]

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

 

[Michael Mair]

Michael Mair wrote:




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

 

[suman kar]

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.

 

[Lawrence Kirby]

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.

 

[Michael Mair]

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

 

[Lawrence Kirby]

....


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

 

[Michael Mair]

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

 

[Tak-Shing Chan]

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

 

[pete]

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;