Linked list question
in [General Programming]
|
Prev: need recommendation on win32 api book or site
Next: Cheap wholesale 2010 World Cup jerseys by paypal and free shipping
From: Chad on 12 Jun 2010 20:18 Let's say I have function called delete() that takes a string 's' as its argument. This functions sole purpose is to delete a node from a singly linked list. The pseudo code would be like the following.... void delete(char *s) { int h; struct nlist *prev, *np; prev = NULL; h = hash(s); for (np = hashtable[h]; np != NULL; np = np->next) { if (strcmp(s, np->name) == 0) break; prev = np; } if (np != NULL) { if (prev == NULL) hashtable[h] == np->next; else prev->next = np->next; /*do some more stuff*/ } } The question is, would the function delete() rely on the length of the linked list? I don't think that it would since I'm not actually passing the actual length of the list itself as an argument in the delete() function. However, the function would still have to traverse the list np until it either finds a match or reaches NULL. So for, whatever reason(s)`, I think that means I would still have to know the length of the linked list. Chad
From: Richard Heathfield on 12 Jun 2010 20:43 Chad wrote: <snip> > if (np != NULL) { > if (prev == NULL) > hashtable[h] == np->next; > else > prev->next = np->next; Take care that you don't leak anything here. Presumably you handle any memory deallocation requirements in /*do some more stuff*/ > /*do some more stuff*/ > } > } > > The question is, would the function delete() rely on the length of the > linked list? I don't think that it would since I'm not actually > passing the actual length of the list itself as an argument in the > delete() function. However, the function would still have to traverse > the list np until it either finds a match or reaches NULL. So for, > whatever reason(s)`, I think that means I would still have to know the > length of the linked list. Well, delete() doesn't actually need to know the length of the list - it's bound to find out sooner or later (first time you don't have a matching string), but you don't need to tell it explicitly, no. -- Richard Heathfield <http://www.cpax.org.uk> Email: -http://www. +rjh@ "Usenet is a strange place" - dmr 29 July 1999 Sig line vacant - apply within
From: Daniel T. on 12 Jun 2010 22:16 Chad <cdalten(a)gmail.com> wrote: > Let's say I have function called delete() that takes a string 's' as > its argument. This functions sole purpose is to delete a node from a > singly linked list. The pseudo code would be like the following.... > > void delete(char *s) > { > int h; > struct nlist *prev, *np; > > prev = NULL; > h = hash(s); > for (np = hashtable[h]; np != NULL; np = np->next) { > if (strcmp(s, np->name) == 0) > break; > prev = np; > } > > if (np != NULL) { > if (prev == NULL) > hashtable[h] == np->next; > else > prev->next = np->next; > /*do some more stuff*/ > } > } > > The question is, would the function delete() rely on the length of the > linked list? The function has O(n) complexity if that's what you're asking. The time it takes to complete is a function of the length of the list. I would be inclined to break it up into two functions, one to find a node and another to delete a node. After all, there are probably going to be lots of occasions to find a node for purposes other than removing it.
From: Alf P. Steinbach on 12 Jun 2010 23:20 * Chad, on 13.06.2010 02:18: > Let's say I have function called delete() that takes a string 's' as > its argument. This functions sole purpose is to delete a node from a > singly linked list. The pseudo code would be like the following.... > > void delete(char *s) This looks like C. In C++ 'delete' is a keyword. So you might want to avoid it also in C. The formal argument would better be char const* s (modulo C syntax, which I'm not that familiar with) which would allow the function to be called with 'char const*' actual argument. > { > int h; > struct nlist *prev, *np; > > prev = NULL; > h = hash(s); > for (np = hashtable[h]; np != NULL; np = np->next) { > if (strcmp(s, np->name) == 0) > break; > prev = np; > } > > if (np != NULL) { > if (prev == NULL) > hashtable[h] == np->next; > else > prev->next = np->next; This decision can be avoided by having a dummy header node in the list. Anyway you might find it useful to have a function struct nlist* unlink( struct nlist** pp_next ) { struct nlist* p_node = *pp_next; *pp_next = p_node->next; return p_node; } with which the last four lines above can be rewritten as unlink( prev == NULL? &hashtable[h] : &prev->next ); You might also consider free( unlink( prev == NULL? &hashtable[h] : &prev->next ) ); In C++ the formal argument would be a reference. > /*do some more stuff*/ > } > } > > The question is, would the function delete() rely on the length of the > linked list? I don't think that it would since I'm not actually > passing the actual length of the list itself as an argument in the > delete() function. However, the function would still have to traverse > the list np until it either finds a match or reaches NULL. So for, > whatever reason(s)`, I think that means I would still have to know the > length of the linked list. If your code works without knowing the length, why do you think it needs to know the length? Cheers & hth., - Alf -- blog at <url: http://alfps.wordpress.com>
From: Richard Heathfield on 12 Jun 2010 23:39
Alf P. Steinbach wrote: > * Chad, on 13.06.2010 02:18: >> Let's say I have function called delete() that takes a string 's' as >> its argument. This functions sole purpose is to delete a node from a >> singly linked list. The pseudo code would be like the following.... >> >> void delete(char *s) > > This looks like C. In C++ 'delete' is a keyword. So you might want to > avoid it also in C. The only reason to avoid it in C is if you want the code to compile in C++ too. Since code that is written to be both C and C++ tends to be bad C and worse C++, it's rarely a great idea to make the attempt. Case in point: if he were using C++, why on earth would he be worrying about this in the first place? He would just use the STL. I tend to use C++ keywords at the drop of a hat in my C code, because they don't 'arf make a noise if I accidentally use the wrong compiler! > The formal argument would better be > > char const* s > > (modulo C syntax, which I'm not that familiar with) which would allow > the function to be called with 'char const*' actual argument. Yes, that's good syntax; so is const char *s, which some people find more readable. <snip> -- Richard Heathfield <http://www.cpax.org.uk> Email: -http://www. +rjh@ "Usenet is a strange place" - dmr 29 July 1999 Sig line vacant - apply within |