Deleting a node in a linked list
Author Message
Deleting a node in a linked list

Hi!
I have a linked list like this:

struct rec {
int data;
int flag;
struct rec *next;
};

Depending on the flag value (0 or 1), I need to delete
the nodes of the list.
I can't use a bidirectional list and possibly I have
to read the list just one time, so the complexity of
the problem should be O(n).
I was thinking to have a pointer
struct rec *prev;
which is initially equal to NULL, and every time I
read a new node (which is not the first), I update
it. If a node have the flag == 1, the prev->next
is updated with the current_ptr->next, and the
current_ptr is passed to the free() function.
Since I have to use it for a test at university,
I need help from you:

a) is this algorithm good?
b) there is another better algorithm?
c) which is the 'typical' delete_node algorithm
for a monodirectional list like mine?

Luca

Tue, 11 Dec 2001 03:00:00 GMT
Deleting a node in a linked list

Quote:
>Hi!
>I have a linked list like this:

>struct rec {
>  int data;
>  int flag;
>  struct rec *next;
>  };

>Depending on the flag value (0 or 1), I need to delete
>the nodes of the list.
>I can't use a bidirectional list and possibly I have
>to read the list just one time, so the complexity of
>the problem should be O(n).
>I was thinking to have a pointer
>struct rec *prev;
>which is initially equal to NULL, and every time I
>read a new node (which is not the first), I update
>it. If a node have the flag == 1, the prev->next
>is updated with the current_ptr->next, and the
>current_ptr is passed to the free() function.
>Since I have to use it for a test at university,
>I need help from you:

>a) is this algorithm good?

I've read your prose description (I love this term ;-) several times
but I still can't figure it out. Here is some code:

#define DELETE_NODE 1

{
struct rec *skimmer, *keeper;

skimmer=first_node->next;
keeper=first_node;
while(skimmer->next)
if (skimmer->flag&DELETE_NODE)
{
keeper->next=skimmer->next;
free(skimmer);
skimmer=keeper->next;
}
else
{
keeper=skimmer;
skimmer=skimmer->next;
}
keeper->next=NULL;
return;

Quote:
}

Quite short hu? ;-) But since this is for a test on school I've built
in a subtle little error (might even result in a crash under certain
circumstances) so the code isn't perfect and I wouldn't turn it in
without correcting that error.

Note that this code never deletes the first node (which I believe was
variable (if bit 0 is 1 of flag then kill the node).

Wed, 12 Dec 2001 03:00:00 GMT
Deleting a node in a linked list

Quote:

> I have a linked list... I need to delete [some] nodes of the list.
> I can't use a bidirectional list and possibly I have to read the
> list just one time, so the complexity of the problem should be O(n).
> I was thinking to have a pointer
>    struct rec *prev;
> which is initially equal to NULL, and every time I read a new node
> (which is not the first), I update it. If a node have the flag == 1,
> the prev->next is updated with the current_ptr->next, and the
> current_ptr is passed to the free() function.

> a) is this algorithm good?

Quote:
> b) there is another better algorithm?

There is a trick which allows you to handle the first node more
cleanly.  If I were your instructor, this is the trick I'd be
looking for (and I'd probably giving extra credit to students who
discovered it), so I won't give it to you outright, but I will
give you a few hints.

The part of your algorithm you described in detail handles nodes
which are not the first.  Presumably, your intention is that when
you have a node to delete which *is* the first node in the list
(discovered by some flag value, or better, by noticing that prev
prev->next.

In other words, whenever you delete a node, you always have one
sometimes it's the previous node's next pointer.  The obvious way
to handle this situation is with an explicit if statement, but
the trickier way involves that programming construct which you
use when you have to write code which manipulates some object,
only you're not sure (as you write the code, that is) which of
several disjoint objects you'll be manipulating.

Quote:
> c) which is the 'typical' delete_node algorithm
>    for a monodirectional list like mine?

The "typical" algorithm is probably the one you've described.
The one I've hinted at is the sophisticated one, which is cleaner
in that it dispenses with the special-casing of the head node,
but which is also arguably less clean in that it's sophisticated
enough that it might be difficult or impossible for unskilled
maintenance programmers to understand.

Steve Summit

Wed, 12 Dec 2001 03:00:00 GMT
Deleting a node in a linked list

...

Quote:
>In other words, whenever you delete a node, you always have one
>sometimes it's the previous node's next pointer.  The obvious way
>to handle this situation is with an explicit if statement, but
>the trickier way involves that programming construct which you
>use when you have to write code which manipulates some object,
>only you're not sure (as you write the code, that is) which of
>several disjoint objects you'll be manipulating.

Or you could use a pointer to a pointer. The head pointer and the next
pointer have the same type so a pointer to a pointer can point to either
one e.g.

for (pptr = &head; (nodeptr = *pptr) != NULL; pptr = &nodeptr->next)

...

Quote:
>> c) which is the 'typical' delete_node algorithm
>>    for a monodirectional list like mine?

>The "typical" algorithm is probably the one you've described.
>The one I've hinted at is the sophisticated one, which is cleaner
>in that it dispenses with the special-casing of the head node,
>but which is also arguably less clean in that it's sophisticated
>enough that it might be difficult or impossible for unskilled
>maintenance programmers to understand.

I find I have to assume at least a basic skill level. People without
that are going to mess the code up however simple you make it.

--
-----------------------------------------

-----------------------------------------

Thu, 13 Dec 2001 03:00:00 GMT
Deleting a node in a linked list
I'd like to say Thank You to all who answered me.
I've got a few confirmations and good hints.

See you... (and sorry for my bad English!)

Sent via Deja.com http://www.deja.com/
Share what you know. Learn what you don't.

Fri, 14 Dec 2001 03:00:00 GMT
Deleting a node in a linked list

Quote:
>> I have a linked list... I need to delete [some] nodes of the list.
>> I can't use a bidirectional list and possibly I have to read the
>> list just one time, so the complexity of the problem should be O(n).
>> a) is this algorithm good?

>> b) there is another better algorithm?

>There is a trick which allows you to handle the first node more
>cleanly.

Hi Steve,
I thought to a possible solution.
Tell me if it can be right.

I'm used to give the first item of the list a special meaning ;
In italian I call it "nodo sentinella".

The list is organized as follows :

[nodo sentinella]->[1st node]->[2nd node]->...->NULL

So if I want to delete a node in the list (even if it is the first) I
write :

curr_ptr = NodoSentinella ;
while ( curr_ptr->next != NULL )
if ( curr_ptr->next->value == searched_value )
{
p = curr_ptr->next ;
curr_ptr->next = curr_ptr->next->next ;
free( p ) ;
break ;
}

Is this a right way to do things ?

Sat, 15 Dec 2001 03:00:00 GMT
Deleting a node in a linked list
Andrea Laforgia schrieb:

Quote:

> I'm used to give the first item of the list a special meaning ;
> In italian I call it "nodo sentinella".

This does sound like some sort of italian noodles :-)
(no insult intended, just some humour)

Stephan
(initiator of the campaign against grumpiness in c.l.c)

Sun, 16 Dec 2001 03:00:00 GMT
Deleting a node in a linked list

Quote:
>This does sound like some sort of italian noodles :-)
>(no insult intended, just some humour)

Don't worry I don't know what means ":-)" in English...

Tue, 18 Dec 2001 03:00:00 GMT
Deleting a node in a linked list

Quote:

>>> I have a linked list... I need to delete [some] nodes of the list.
>>> b) there is another better algorithm?

>> There is a trick which allows you to handle the first node more
>> cleanly.

> I'm used to give the first item of the list a special meaning ;
> In italian I call it "nodo sentinella".

Ah, that sounds suspiciously like what we might call a "sentinel
node" in English! :-)

Quote:
> The list is organized as follows :
> [nodo sentinella]->[1st node]->[2nd node]->...->NULL
> So if I want to delete a node in the list (even if it is the first) I
> write :
>[code omitted]
> Is this a right way to do things ?

It's certainly a right way to do things, yes.  In general,
sentinels like these can be very powerful.

Personally, I've never liked dummy nodes at the head or tail
of linked lists; they seem a bit... wasteful.  (But there are
plenty of authors who recommend them, so don't stop using them
just because I said so!)  I was thinking of a different trick,
namely using a pointer to a pointer to a list node.
I've written up an explanation of this technique in my class
notes; the explanation starts about halfway through the page
http://www.eskimo.com/~scs/cclass/int/sx8.html .

Steve Summit

Tue, 18 Dec 2001 03:00:00 GMT
Deleting a node in a linked list

[...]
: > I'm used to give the first item of the list a special meaning ;
: > In italian I call it "nodo sentinella".

: Ah, that sounds suspiciously like what we might call a "sentinel
: node" in English! :-)

My understanding is that a sentinel node, as its name implies,
actually guards something.  An example might be:

int data[] = { 2,5,3,4,6,1,-1 };
int i = 0;

while (data[i] > 0)
process(data[i]);

in which -1 is the sentinel.  It prevents the algorithm, which
doesn't know how long the data stream is, from going off the
end.  Similarly, the 0 at the end of strings, and the NULL at
the end of argv, are sentinels.  This is the first time I've
heard the term applied to the initial unused node (no, I don't
know what it's called :) of a linked list.

Tue, 18 Dec 2001 03:00:00 GMT
Deleting a node in a linked list

Quote:

>>This does sound like some sort of italian noodles :-)
>>(no insult intended, just some humour)

>Don't worry I don't know what means ":-)" in English...

Probably "sentinel node". However sentinels are usually data values that
mark the end of the data so that you don't have to test the bounds
explicitly. You could call the null character at the end of a string
a sentinel.

--
-----------------------------------------

-----------------------------------------

Tue, 18 Dec 2001 03:00:00 GMT
Deleting a node in a linked list

Quote:

> : > I'm used to give the first item of the list a special meaning ;
> : > In italian I call it "nodo sentinella".

> : Ah, that sounds suspiciously like what we might call a "sentinel
> : node" in English! :-)

> My understanding is that a sentinel node, as its name implies,
> actually guards something.  An example might be:
>   int data[] = { 2,5,3,4,6,1,-1 };
>   int i = 0; while (data[i] > 0)
>     process(data[i]);
> in which -1 is the sentinel.  It prevents the algorithm, which
> doesn't know how long the data stream is, from going off the
> end.  Similarly, the 0 at the end of strings, and the NULL at
> the end of argv, are sentinels.  This is the first time I've
> heard the term applied to the initial unused node...

Me, too.  But since it prevents the algorithm, which would rather
not treat the first node in the list specially, from "going off
the *beginning*", the usage did not seem wholly inappropriate.

Quote:
> (no, I don't know what it's called :) of a linked list.

I always call it a "dummy node" or a "head node".  (When the
first node in a list is a real node, I speak instead of the
"head pointer" that points to it.)

Steve Summit

Wed, 19 Dec 2001 03:00:00 GMT
Deleting a node in a linked list

Quote:
>> the end of argv, are sentinels.  This is the first time I've
>> heard the term applied to the initial unused node...

First of all, I apologize to you all if sometimes I cannot reply to
some message. This problem is due to my newsreader which doesn't show
me all replies to messages, but a small part of them (I don't know
why).

node like that is a little wasteful : I'm perfectly agree and not sure
that is an efficient way to solve the problem.
Andrea Laforgia
-----------------------------------------------------
There is nothing better for understanding a kangaroo
than seeing it jump.
-----------------------------------------------------

Thu, 20 Dec 2001 03:00:00 GMT

 Page 1 of 1 [ 13 post ]

Relevant Pages