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?

Thank You for your help.

Luca

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

void purge_linked_list(struct rec *first_node)
{
        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;

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
good, reading your prose) and I have made a real flag out of your flag
variable (if bit 0 is 1 of flag then kill the node).

It's certainly not bad.

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
is NULL), you'll adjust the list's head pointer, rather than
prev->next.

In other words, whenever you delete a node, you always have one
pointer to adjust, but sometimes it's the head pointer and
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.

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

...

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)

...

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.

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


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

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.

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 ?

Andrea Laforgia schrieb:

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)

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

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

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

[...]
: > 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.

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.

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


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

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.

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

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

I could not read your message but I read Steve's one, who said that a
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.
-----------------------------------------------------