Singly Linked List in C
arnuld
advice for improvement or you want me to implement some more operations in
order to improve my understanding of linked lists:
/* This C implementation of singly linked list implements 3 operations: add, remove and insert elements at some specific position in
* the list.
*
* VERISON 0.0
*
*/
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
struct my_struct* add_to_list( struct my_struct *const, const int);
struct my_struct* remove_from_list( struct my_struct *const, const int );
struct my_struct* insert_after_element(struct my_struct *const, const int, const int);
void print_list( const struct my_struct* );
struct my_struct
{
int num;
struct my_struct* next;
};
int main(void)
{
struct my_struct* root_node = malloc( 1 * sizeof(*root_node));
const int i = 1;
const int j = 2;
if( NULL == root_node )
{
fprintf(stderr, "IN %s, %s: malloc() failed\n", __FILE__, "main");
return EXIT_FAILURE;
}
else
{
root_node->next = 0;
root_node->next = NULL;
}
add_to_list(root_node, i);
add_to_list(root_node, j);
print_list(root_node);
printf("going to remove element with value = %d\n", i);
remove_from_list(root_node, i);
print_list(root_node);
printf("going to insert element after root_node\n");
insert_after_element(root_node, root_node->num, i);
print_list(root_node);
return 0;
}
struct my_struct* add_to_list(struct my_struct *const base_node, const int i )
{
struct my_struct* s = base_node;
struct my_struct* c = NULL;
struct my_struct* p = malloc( 1 * sizeof(*p));
if( NULL == p )
{
fprintf(stderr, "IN %s, %s: malloc() failed\n", __FILE__, "add_to_list");
return NULL;
}
p->num = i;
p->next = NULL;
for( ; s != NULL ; s = s->next ) c = s;
c->next = p;
return c->next;
}
struct my_struct* remove_from_list( struct my_struct *const base_node, const int r )
{
struct my_struct* s = base_node;
struct my_struct* c = NULL;
for( ; (NULL != s) && (s->num != r); s = s->next ) c = s;
if( s )
{
c->next = s->next;
free(s);
return c;
}
return NULL;
}
struct my_struct* insert_after_element(struct my_struct *const base_node, const int after, const int i)
{
struct my_struct* s = base_node;
struct my_struct* n = NULL;
struct my_struct* p = NULL;
for( ; (NULL != s) && (s->num != after ); s = s->next );
if( NULL == s )
{
printf("No element with number match: %d\n", i);
}
else
{
p = malloc( 1 * sizeof(*p));
if( NULL == p )
{
fprintf(stderr, "IN: %s, %s: malloc() failed\n", __FILE__, "insert_after_element");
return NULL;
}
p->num = i;
n = s->next;
s->next = p;
p->next = n;
}
return p;
}
void print_list( const struct my_struct* p )
{
for( ; NULL != p; p = p->next )
{
printf("Num = %d\n", p->num);
}
printf("\n\n");
}
================== OUTPUT =========================
[arnuld@dune programs]$ gcc -ansi -pedantic -Wall -Wextra singly-LL.c
[arnuld@dune programs]$ ./a.out
Num = 0
Num = 1
Num = 2
going to remove element with value = 1
Num = 0
Num = 2
going to insert element after root_node
Num = 0
Num = 1
Num = 2
[arnuld@dune programs]$
--
www.lispmachine.wordpress.com
my email is @ the above blog.
mark.b...@googlemail.com
> I am learning about linked lists. This works fine without any trouble. Any
> advice for improvement or you want me to implement some more operations in
> order to improve my understanding of linked lists:
I'll make a few comments, which are just my opinion, off-the-cuff and
certainly not definitive.
> /* This C implementation of singly linked list implements 3 operations: add, remove and insert elements at some specific position in
> * the list.
> *
> * VERISON 0.0
> *
> */
>
> #include <stdio.h>
> #include <stdlib.h>
> #include <string.h>
>
> struct my_struct* add_to_list( struct my_struct *const, const int);
> struct my_struct* remove_from_list( struct my_struct *const, const int );
> struct my_struct* insert_after_element(struct my_struct *const, const int, const int);
You never use the return values from these routines, and I'm not sure
you ever would.
An integer indicating success or failure may be more useful than the
structure.
>
> void print_list( const struct my_struct* );
>
> struct my_struct
> {
> int num;
> struct my_struct* next;
>
> };
>
> int main(void)
> {
> struct my_struct* root_node = malloc( 1 * sizeof(*root_node));
Your main-line code doesn't really need to know about my_struct
structures, so why do this here?
My design for this sort of thing would have a function something
like :-
void *list_create();
to initialise a list. The returned value (remaining as a void *) would
be my first argument to the other list management functions, which
could assign it to a my_struct * internally.
> const int i = 1;
> const int j = 2;
>
> if( NULL == root_node )
> {
> fprintf(stderr, "IN %s, %s: malloc() failed\n", __FILE__, "main");
> return EXIT_FAILURE;
> }
> else
> {
> root_node->next = 0;
> root_node->next = NULL;
Naturally this belongs in the list initialisation function.
> }
>
> add_to_list(root_node, i);
> add_to_list(root_node, j);
>
> print_list(root_node);
>
> printf("going to remove element with value = %d\n", i);
> remove_from_list(root_node, i);
> print_list(root_node);
>
> printf("going to insert element after root_node\n");
> insert_after_element(root_node, root_node->num, i);
> print_list(root_node);
>
> return 0;
>
> }
>
> struct my_struct* add_to_list(struct my_struct *const base_node, const int i )
> {
> struct my_struct* s = base_node;
> struct my_struct* c = NULL;
> struct my_struct* p = malloc( 1 * sizeof(*p));
>
> if( NULL == p )
> {
> fprintf(stderr, "IN %s, %s: malloc() failed\n", __FILE__, "add_to_list");
> return NULL;
> }
>
> p->num = i;
> p->next = NULL;
>
> for( ; s != NULL ; s = s->next ) c = s;
>
> c->next = p;
>
> return c->next;
>
You don't really need c. Traverse the list until s->next == NULL and
use s.
Reorder these and you don't need n.
> }
>
> return p;
>
> }
>
> void print_list( const struct my_struct* p )
> {
> for( ; NULL != p; p = p->next )
> {
> printf("Num = %d\n", p->num);
> }
>
> printf("\n\n");
>
> }
Consider this alternative set of interfaces:-
void *create_list(); /* allocate and initialise root node */
int add_to_list( void *list, const int value );
int remove_from_list( void *list, const int value );
int insert_after_element( void *list, const int value, const int
value2 );
void print_list( void *list );
void delete_list( void *list ); /* free all nodes (including the root
node) */
Also consider how you could generalise this easily - for example, what
you could do if the nodes had the form :-
struct my_struct {
void *the_data;
struct my_struct *next;
}
Ben Bacarisse
> I am learning about linked lists. This works fine without any trouble. Any
> advice for improvement or you want me to implement some more operations in
> order to improve my understanding of linked lists:
Just to complicate the advice, I would keep the return value as a
pointer but I would use it to return the pointer to the list head.
That way you don't need to allocate the first element "by hand" as you
have been doing.
The add operation is then always:
list = add_to_list(list, ...);
and similarly with remove. This really simplifies the code.
If you are using what I consider a rather ugly trick of always having a
dummy first node, then I strongly advice you change that. I don't
think you are doing that because the print function prints it!
I'd make all the function names start with a common prefix
(i.e. list_add, list_remove and so on). It is a shame that this does
not produce natural meaning in English (the "list add" operation adds
a list not an item to a list in plain English) but all programmers
will know what you mean.
If the list had only one element, how would this line have any effect
at all? If the item being removed is the first, then what?
> print_list(root_node);
>
>
> printf("going to insert element after root_node\n");
> insert_after_element(root_node, root_node->num, i);
> print_list(root_node);
>
> return 0;
> }
>
>
>
>
> struct my_struct* add_to_list(struct my_struct *const base_node, const int i )
> {
> struct my_struct* s = base_node;
> struct my_struct* c = NULL;
> struct my_struct* p = malloc( 1 * sizeof(*p));
>
> if( NULL == p )
> {
> fprintf(stderr, "IN %s, %s: malloc() failed\n", __FILE__, "add_to_list");
> return NULL;
> }
>
> p->num = i;
> p->next = NULL;
>
> for( ; s != NULL ; s = s->next ) c = s;
>
> c->next = p;
>
>
> return c->next;
You can only add using this function if there is an element already in
the list. That can't be a clean interface!
> }
>
>
> struct my_struct* remove_from_list( struct my_struct *const base_node, const int r )
> {
> struct my_struct* s = base_node;
> struct my_struct* c = NULL;
>
> for( ; (NULL != s) && (s->num != r); s = s->next ) c = s;
>
> if( s )
> {
> c->next = s->next;
> free(s);
> return c;
This is not right. If the first element has s->num == r then c ==
NULL and you can't do c->next = anything.
> }
>
> return NULL;
> }
>
>
> struct my_struct* insert_after_element(struct my_struct *const base_node, const int after, const int i)
> {
> struct my_struct* s = base_node;
> struct my_struct* n = NULL;
> struct my_struct* p = NULL;
>
> for( ; (NULL != s) && (s->num != after ); s = s->next );
>
> if( NULL == s )
> {
> printf("No element with number match: %d\n", i);
> }
> else
> {
> p = malloc( 1 * sizeof(*p));
>
> if( NULL == p )
> {
> fprintf(stderr, "IN: %s, %s: malloc() failed\n", __FILE__, "insert_after_element");
> return NULL;
When you write code like this for the second time, go find the first
and make it into a function.
> }
>
> p->num = i;
>
> n = s->next;
> s->next = p;
> p->next = n;
> }
>
> return p;
If your interface to add_list is correct and easy to use, this
function can be written using it. In fact, I'd make that a
challenge. Re-work the add function until you can use it here to
simplify insert_after.
> }
>
> void print_list( const struct my_struct* p )
> {
> for( ; NULL != p; p = p->next )
> {
> printf("Num = %d\n", p->num);
> }
>
> printf("\n\n");
> }
--
Ben.
Barry Schwarz
wrote:
>I am learning about linked lists. This works fine without any trouble. Any
>advice for improvement or you want me to implement some more operations in
>order to improve my understanding of linked lists:
>
>
>/* This C implementation of singly linked list implements 3 operations: add, remove and insert elements at some specific position in
> * the list.
> *
> * VERISON 0.0
> *
> */
>
>#include <stdio.h>
>#include <stdlib.h>
>#include <string.h>
>
>
>struct my_struct* add_to_list( struct my_struct *const, const int);
>struct my_struct* remove_from_list( struct my_struct *const, const int );
>struct my_struct* insert_after_element(struct my_struct *const, const int, const int);
>
>void print_list( const struct my_struct* );
>
>
>struct my_struct
>{
> int num;
> struct my_struct* next;
>};
>
>
>
>int main(void)
>{
> struct my_struct* root_node = malloc( 1 * sizeof(*root_node));
The inner parentheses are superfluous.
> const int i = 1;
> const int j = 2;
>
> if( NULL == root_node )
> {
> fprintf(stderr, "IN %s, %s: malloc() failed\n", __FILE__, "main");
> return EXIT_FAILURE;
> }
> else
> {
> root_node->next = 0;
> root_node->next = NULL;
Do you really think there is the slightest difference between the two
previous statements?
> }
>
>
> add_to_list(root_node, i);
> add_to_list(root_node, j);
>
> print_list(root_node);
>
> printf("going to remove element with value = %d\n", i);
> remove_from_list(root_node, i);
> print_list(root_node);
>
>
> printf("going to insert element after root_node\n");
> insert_after_element(root_node, root_node->num, i);
At no point have you assigned a value to root_node->num. Attempting
to evaluate it here invokes undefined behavior.
> print_list(root_node);
>
> return 0;
>}
>
>
>
>
>struct my_struct* add_to_list(struct my_struct *const base_node, const int i )
>{
> struct my_struct* s = base_node;
> struct my_struct* c = NULL;
> struct my_struct* p = malloc( 1 * sizeof(*p));
>
> if( NULL == p )
Is there some significance to the different spacing you use around
parentheses?
> {
> fprintf(stderr, "IN %s, %s: malloc() failed\n", __FILE__, "add_to_list");
> return NULL;
> }
>
> p->num = i;
> p->next = NULL;
>
> for( ; s != NULL ; s = s->next ) c = s;
>
> c->next = p;
>
>
> return c->next;
>}
>
>
>struct my_struct* remove_from_list( struct my_struct *const base_node, const int r )
>{
> struct my_struct* s = base_node;
> struct my_struct* c = NULL;
>
> for( ; (NULL != s) && (s->num != r); s = s->next ) c = s;
>
> if( s )
> {
> c->next = s->next;
> free(s);
> return c;
> }
>
> return NULL;
>}
>
>
>struct my_struct* insert_after_element(struct my_struct *const base_node, const int after, const int i)
>{
> struct my_struct* s = base_node;
> struct my_struct* n = NULL;
> struct my_struct* p = NULL;
>
> for( ; (NULL != s) && (s->num != after ); s = s->next );
When s == base_node, this also invokes undefined behavior
--
Remove del for email
arnuld
>> arnuld <sun...@invalid.address> writes:
>> I am learning about linked lists. This works fine without any trouble. Any
>> advice for improvement or you want me to implement some more operations in
>> order to improve my understanding of linked lists:
> Just to complicate the advice, I would keep the return value as a
> pointer but I would use it to return the pointer to the list head.
> That way you don't need to allocate the first element "by hand" as you
> have been doing.
I think I did not understand what you mean ?
> The add operation is then always:
>
> list = add_to_list(list, ...);
>
> and similarly with remove. This really simplifies the code.
but then how do I know which element to add or remove, see:
struct my_struct* list_add(struct my_struct *const base_node, const int i )
{
struct my_struct* s = base_node;
struct my_struct* c = NULL;
struct my_struct* p = malloc( 1 * sizeof(*p));
if( NULL == p )
{
fprintf(stderr, "IN %s, %s: malloc() failed\n", __FILE__, "list_add");
return NULL;
}
p->num = i;
p->next = NULL;
for( ; s != NULL ; s = s->next );
s = p;
return s;
}
In this case there is only one variable i, which is being passed to
p->num, now if I make 2nd argument 3 dots (...) which means a variable
number of input, then how to pass that value to struct ?
Phil Carmody
I'm not too bothered how many variable i's there are - your code
doesn't work. There is no adding of anything to any list, for
example.
And even if it was tweaked to work, it looks like you're proposing
an O(n) algorithm for something that should be O(1). Which is
horrific.
Phil
--
Marijuana is indeed a dangerous drug.
It causes governments to wage war against their own people.
-- Dave Seaman (sci.math, 19 Mar 2009)
arnuld
> I'm not too bothered how many variable i's there are - your code
> doesn't work. There is no adding of anything to any list, for
> example.
Yes, it does not and I don't understand why. I am assigning a newly
malloc()ed pointer to the base node. Even I have a NULL check for malloc()
> And even if it was tweaked to work, it looks like you're proposing
> an O(n) algorithm for something that should be O(1). Which is
> horrific.
Adding an element to the end of a singly-linked list is always O(n).
arnuld
think I need to understand basics first:
WANTED: To add an element to the singly linked list.
HAPPENS: Nothing is added to the list.
/* This C implementation of singly linked list implements 3 operations: add, remove and insert elements at some specific position in
* the list.
*
* VERISON 0.1
*
*/
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
struct my_struct* list_add( struct my_struct *const, const int);
void list_print( const struct my_struct* );
void list_print_element(const struct my_struct *const );
struct my_struct
{
int num;
struct my_struct* next;
};
int main(void)
{
struct my_struct* root_node = NULL;
list_add(root_node, 1);
list_print(root_node);
return 0;
}
struct my_struct* list_add(struct my_struct *const base_node, const int i )
{
struct my_struct* s = base_node;
struct my_struct* c = s;
struct my_struct* p = malloc( 1 * sizeof(*p) );
if( NULL == p )
{
fprintf(stderr, "IN %s, %s: malloc() failed\n", __FILE__, "list_add");
return NULL;
}
p->num = i;
p->next = NULL;
if( NULL == s )
{
printf("Base Node was NULL, so adding current maloc()ed struct to base\n");
s = p;
}
else
{
printf("Base node is non-NULL, so adding it to the end of the list\n");
for( ; s != NULL ; s = s->next ) c = s;
c = p;
}
return base_node;
}
void list_print( const struct my_struct *const sp )
{
const struct my_struct* p = sp;
for( ; NULL != p; p = p->next )
{
list_print_element(p);
}
printf("\n------------------\n");
}
void list_print_element(const struct my_struct *const p )
{
if( p )
{
printf("Num = %d\n", p->num);
}
else
{
printf("Can not print NULL struct \n");
}
}
============== OUTPUT ===================
[arnuld@dune programs]$ gcc -ansi -pedantic -Wall -Wextra singly-LL.c
[arnuld@dune programs]$ ./a.out
Base Node was NULL, so adding current maloc()ed struct to base
------------------
[arnuld@dune programs]$
arnuld
>> On Tue, 28 Apr 2009 15:45:33 +0500, arnuld <sun...@invalid.address>
>>int main(void)
>>{
>> struct my_struct* root_node = malloc( 1 * sizeof(*root_node));
> The inner parentheses are superfluous.
Just added them for clarity.
>> if( NULL == p )
> Is there some significance to the different spacing you use around
> parentheses?
I always use it like that otherwise I can't read properly.
> When s == base_node, this also invokes undefined behavior
Corrected in version 0.1 of code I just posted
BartC
"arnuld" <sun...@invalid.address> wrote in message
news:pan.2009.05.04....@invalid.address...
> Here is the new version, which only adds an element to the linked list. I
> think I need to understand basics first:
>
> WANTED: To add an element to the singly linked list.
> HAPPENS: Nothing is added to the list.
I've put a version of your code here. The /* !!!!! */ comment marks where I
think the main problem was.
But I've also changed a few things that I found annoying or made it
unreadable, notably getting rid of the consts (I've never got my mind around
those), and using a typedef 'tnode' instead of those untidy structs
everywhere.
You can also make it a bit simpler if you are happy with the items being
added in reverse order. (And if you need them in order, there are better
ways than searching to the end of the list each time; imagine you have tens
of millions of nodes.)
Note: watch for line-wraps on the string constants, you may need to join
these up again.
/* This C implementation of singly linked list implements 3 operations: add,
remove and insert elements at some specific position in
* the list.
*
* VERSION 0.1a
*
*/
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
struct my_struct
{
int num;
struct my_struct* next;
};
typedef struct my_struct tnode;
tnode* list_add( tnode *, int);
void list_print(tnode* );
void list_print_element(tnode *);
int main(void)
{
tnode* root_node = NULL;
root_node = list_add(root_node, 1); /* !!!!! */
list_add(root_node, 16);
list_add(root_node, 176);
list_add(root_node, 1766);
list_print(root_node);
return 0;
}
/* Create a new node containing data i.
Add it to the linked list base_node, which
can be NULL for any empty list.
Return (possibly updated) base_node
*/
tnode* list_add(tnode *base_node, int i )
{
tnode* s;
tnode* p = malloc(sizeof(tnode));
if(p==NULL) return base_node; /* Do not return NULL here */
p->num = i;
p->next = NULL;
if(base_node==NULL)
{
printf("Base Node was NULL, so adding current malloc()ed struct to
base\n");
base_node = p;
}
else
{
printf("Base node is non-NULL, so adding it to the end of the
list\n");
s = base_node;
while (s->next) s=s->next;
s->next = p;
}
return base_node;
}
void list_print(tnode * sp)
{
tnode* p;
puts("Printout of linked list:");
for(p=sp ; p!=NULL; p = p->next )
{
list_print_element(p);
}
printf("\n------------------\n");
}
void list_print_element(tnode *p)
{
if( p )
{
printf("Num = %d\n", p->num);
}
else
{
printf("Can not print NULL struct \n");
}
}
--
Bart
pete
> Adding an element to the end of a singly-linked list is always O(n).
Not if your program keeps track of where the end of the list is.
--
pete
Ben Bacarisse
> Here is the new version, which only adds an element to the linked list. I
> think I need to understand basics first:
>
> WANTED: To add an element to the singly linked list.
> HAPPENS: Nothing is added to the list.
<snip>
> int main(void)
> {
> struct my_struct* root_node = NULL;
>
> list_add(root_node, 1);
> list_print(root_node);
This is enough to see the problem. list add can no change root_node.
It is NULL at the start and no matte what the function does it will be
NULL afterwards.
You must decide between one of three different designs:
(a) The list_add operation must always be used in an assignment. It
return the new list: root = list_add(root, ...);
(b) You must pass a pointer to the list pointer so that list_add can
change it: list_add(&root, ...);
(c) You pass a pointer to some overall list structure (not the same as
the node structure) and list_add manipulates that.
The idea of having an unused head element is a version of this design
but I don't like it. If the list is to be more sophisticated (say be
having a head and tail pointer, or extra information list the length)
then (c) is the way to go, but it is a more complicated design.
You really should not get any further until you are certain that you
can see why what you are doing can't work, and why all of the above are
ways to solve this fundamental problem.
For a simple list I suggest (a) but you will get sound advice from
sane and experienced people who will advocate (b) and/or (c). When
you choose, stick with it until you are done -- changing part way
though makes giving advice almost impossible!
> return 0;
> }
--
Ben.
Ben Bacarisse
>> On Wed, 29 Apr 2009 00:22:03 +0100, Ben Bacarisse wrote:
>>> arnuld <sun...@invalid.address> writes:
>
>>> I am learning about linked lists. This works fine without any trouble. Any
>>> advice for improvement or you want me to implement some more operations in
>>> order to improve my understanding of linked lists:
>
>> Just to complicate the advice, I would keep the return value as a
>> pointer but I would use it to return the pointer to the list head.
>> That way you don't need to allocate the first element "by hand" as you
>> have been doing.
>
> I think I did not understand what you mean ?
All I mean is that:
struct node *root == NULL;
...
root = list_add(root, 42);
is perfectly valid if list_add allocates a node and return a pointer
to the list. It is particularly easy if the item is added at the
front of the list and there is no reason not to do that as far as I
can see.
If you have to add items to the end of the list you should use another
strategy (see item (c) in my other post) unless you are prepared to
pay the cost of traversing the list just to add an item.
>> The add operation is then always:
>>
>> list = add_to_list(list, ...);
>>
>> and similarly with remove. This really simplifies the code.
>
> but then how do I know which element to add or remove, see:
>
> struct my_struct* list_add(struct my_struct *const base_node, const int i )
> {
> struct my_struct* s = base_node;
> struct my_struct* c = NULL;
> struct my_struct* p = malloc( 1 * sizeof(*p));
>
> if( NULL == p )
> {
> fprintf(stderr, "IN %s, %s: malloc() failed\n", __FILE__, "list_add");
> return NULL;
> }
>
> p->num = i;
> p->next = NULL;
>
> for( ; s != NULL ; s = s->next );
> s = p;
>
> return s;
> }
>
> In this case there is only one variable i, which is being passed to
> p->num, now if I make 2nd argument 3 dots (...) which means a variable
> number of input, then how to pass that value to struct ?
Sorry, the ... were to suggest other arguments in a call. ... is not
legal C in a function call! Sorry if this confused you.
Using the return value you'd write code like this:
struct list_node {
struct list_node *next;
int number;
};
struct list_node *make_node(struct list_node *tail, int i)
{
struct list_node *np = malloc(sizeof *np);
if (np) {
np->next = tail;
np->number = i;
}
return np;
}
struct list_node *list_add_head(struct list_node *list, int i)
{
return make_node(list, i);
}
struct list_node *list_add_tail(struct list_node *list, int i)
{
if (list) {
list->next = list_add_tail(list->next, i);
return list;
}
else return make_node(list, i);
}
(Not tested.) I've written both the front adding and the tail adding
version. You can make the tail version iterative if you don't like
recursion, but you really need a different design or a list you can
efficiently add to the end of.
--
Ben.
arnuld
>> arnuld <sun...@invalid.address> writes:
>> int main(void)
>> {
>> struct my_struct* root_node = NULL;
>>
>> list_add(root_node, 1);
>> list_print(root_node);
> This is enough to see the problem. list add can no change root_node.
> It is NULL at the start and no matte what the function does it will be
> NULL afterwards.
I know in C everything is passed by value. When you pass a pointer to
some function it is copy of that pointer but that copy still points to the
place where original pointer was pointing. So, I can use it to change
that. Right or wrong ?
> You must decide between one of three different designs:
>
> (a) The list_add operation must always be used in an assignment. It
> return the new list: root = list_add(root, ...);
Thats what exactly I saw in K&R2. Though I liked option (b) .
> (b) You must pass a pointer to the list pointer so that list_add can
> change it: list_add(&root, ...);
>
> (c) You pass a pointer to some overall list structure (not the same as
> the node structure) and list_add manipulates that.
> The idea of having an unused head element is a version of this design
> but I don't like it. If the list is to be more sophisticated (say be
> having a head and tail pointer, or extra information list the length)
> then (c) is the way to go, but it is a more complicated design.
> You really should not get any further until you are certain that you can
> see why what you are doing can't work, and why all of the above are ways
> to solve this fundamental problem.
Lets implement it using (b) (and I have removed some const-edness ) but it
still does not work:
/* This C implementation of singly linked list implements 3 operations: add, remove and insert elements at some specific position in
* the list.
*
* VERISON 0.2
*
*/
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
struct my_struct* list_add( struct my_struct **, const int);
void list_print( const struct my_struct* );
void list_print_element(const struct my_struct *const );
struct my_struct
{
int num;
struct my_struct* next;
};
int main(void)
{
struct my_struct* root_node = NULL;
list_add(&root_node, 1);
list_print(root_node);
return 0;
}
struct my_struct* list_add(struct my_struct ** base_node, const int i )
{
struct my_struct* s = *base_node;
struct my_struct* p = malloc( 1 * sizeof(*p) );
if( NULL == p )
{
fprintf(stderr, "IN %s, %s: malloc() failed\n", __FILE__, "list_add");
return NULL;
}
p->num = i;
p->next = NULL;
if( NULL == s )
{
printf("Base Node was NULL, so adding current maloc()ed struct to base\n");
s = p;
}
else
{
printf("Base node is non-NULL, so adding it to the end of the list\n");
for( ; s->next != NULL ; s = s->next);
s->next = p;
}
return *base_node;
}
void list_print( const struct my_struct *const sp )
{
const struct my_struct* p = sp;
for( ; NULL != p; p = p->next )
{
list_print_element(p);
}
printf("\n------------------\n");
}
void list_print_element(const struct my_struct *const p )
{
if( p )
{
printf("Num = %d\n", p->num);
}
else
{
printf("Can not print NULL struct \n");
}
}
--
BartC
news:pan.2009.05.04....@invalid.address...
> Lets implement it using (b) (and I have removed some const-edness ) but it
> still does not work:
> list_add(&root_node, 1);
I put in these print statements:
printf("Root node before: %x",root_node);
list_add(&root_node, 1);
printf("Root node after: %x",root_node);
root_node is 0 before, and still 0 after, so is not being changed.
list_add is now returning a value that is not being used, and it's not
changing root_node (for example by using *base_node=something).
--
Bart
Ben Bacarisse
>> Mon, 04 May 2009 12:59:01 +0100, Ben Bacarisse wrote:
>
>>> arnuld <sun...@invalid.address> writes:
>>> int main(void)
>>> {
>>> struct my_struct* root_node = NULL;
>>>
>>> list_add(root_node, 1);
>>> list_print(root_node);
>
>
>> This is enough to see the problem. list add can no change root_node.
>> It is NULL at the start and no matte what the function does it will be
>> NULL afterwards.
>
> I know in C everything is passed by value. When you pass a pointer to
> some function it is copy of that pointer but that copy still points to the
> place where original pointer was pointing. So, I can use it to change
> that. Right or wrong ?
Right. Do you see why your code above can't work though?
>> You must decide between one of three different designs:
>>
>> (a) The list_add operation must always be used in an assignment. It
>> return the new list: root = list_add(root, ...);
>>
>> (b) You must pass a pointer to the list pointer so that list_add can
>> change it: list_add(&root, ...);
>>
>> (c) You pass a pointer to some overall list structure (not the same as
>> the node structure) and list_add manipulates that.
<snip>
> Lets implement it using (b)
OK/
> (and I have removed some const-edness ) but it
> still does not work:
<snip>
> struct my_struct
> {
> int num;
> struct my_struct* next;
> };
<snip>
> struct my_struct* list_add(struct my_struct ** base_node, const int i )
> {
> struct my_struct* s = *base_node;
> struct my_struct* p = malloc( 1 * sizeof(*p) );
> if( NULL == p ) {
> fprintf(stderr, "IN %s, %s: malloc() failed\n", __FILE__, "list_add");
> return NULL;
> }
> p->num = i;
> p->next = NULL;
> if( NULL == s ) {
> printf("Base Node was NULL, so adding current maloc()ed struct to base\n");
> s = p;
> }
> else {
> printf("Base node is non-NULL, so adding it to the end of the list\n");
> for( ; s->next != NULL ; s = s->next);
> s->next = p;
> }
> return *base_node;
> }
I have changed the layout because I think it helps to see the whole
thing. There is no code that changes what base_node points to so
this code, also, will have no effect at all on the list pointer whose
address you pass to it. (The name is bad, BTW. base node is not a
node. It is not even a pointer to one.)
I.e. after a call like list_add(&root, 42); root will be exactly the
same as it was before.
I could just re-write this to work, but surely it would help you more
if you work though what it does to see why it is not correct?
--
Ben.
arnuld
> I put in these print statements:
>
> printf("Root node before: %x",root_node);
> list_add(&root_node, 1);
> printf("Root node after: %x",root_node);
>
> root_node is 0 before, and still 0 after, so is not being changed.
yes, it does not.
> list_add is now returning a value that is not being used,
yes, I plan to use it later. Actually, all of the functions I have ever
written for my company always return something (except of function who
just print the information), so I have made it my standard.
> and it's not changing root_node (for example by using
> *base_node=something).
I see that and I am out of any understanding why it is happening.
This Pointer-business is really shi**ing my brain.
arnuld
> Right. Do you see why your code above can't work though?
No, I don't see why.
> I could just re-write this to work, but surely it would help you more
> if you work though what it does to see why it is not correct?
yes, I wrote this code and found that out:
#include <stdio.h>
#include <stdlib.h>
void change_p1(int** p1, int* p2 );
int main(void)
{
int i = 1;
int j = 2;
int* p1 = &i;
int* p2 = &j;
printf("*p1 = %d\n", *p1);
change_p1(&p1, p2);
printf("*p1 = %d\n", *p1);
return 0;
}
void change_p1(int** p1, int* p2 )
{
*p1 = p2;
}
================= OUTPUT =========================
[arnuld@dune programs]$ gcc -ansi -pedantic -Wall -Wextra test.c
[arnuld@dune programs]$ ./a.out
*p1 = 1
*p1 = 2
[arnuld@dune programs]$
So, the problem was I was using a local pointer to change the value of the
passed argument. I don't see why it is wrong to do so though. Here is the
new working code:
/* This C implementation of singly linked list implements 3 operations: add, remove and insert elements at some specific position in
* the list.
*
* VERISON 0.3
*
*/
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
struct my_struct* list_add( struct my_struct **, const int);
void list_print( const struct my_struct* );
void list_print_element(const struct my_struct *const );
struct my_struct
{
int num;
struct my_struct* next;
};
int main(void)
{
struct my_struct* list_head = NULL;
printf("List default\n");
list_print(list_head);
printf("List after adding values\n");
list_add(&list_head, 1);
list_add(&list_head, 2);
list_print(list_head);
return 0;
}
struct my_struct* list_add(struct my_struct ** head, const int i )
{
struct my_struct* p = malloc( 1 * sizeof(*p) );
if( NULL == p )
{
fprintf(stderr, "IN %s, %s: malloc() failed\n", __FILE__, "list_add");
return NULL;
}
p->num = i;
p->next = NULL;
if( NULL == *head )
{
/* printf("Base Node was NULL, so adding current maloc()ed struct to base\n"); */
*head = p;
}
else
{
/* printf("Base node is non-NULL, so adding it to the end of the list\n"); */
for( ; (*head)->next != NULL ; *head = (*head)->next);
(*head)->next = p;
}
return *head;
}
void list_print( const struct my_struct *const sp )
{
const struct my_struct* p = sp;
for( ; NULL != p; p = p->next )
{
list_print_element(p);
}
printf("\n------------------\n");
}
void list_print_element(const struct my_struct *const p )
{
if( p )
{
printf("Num = %d\n", p->num);
}
else
{
printf("Can not print NULL struct \n");
}
}
========================== OUTPUT =================================
[arnuld@dune programs]$ gcc -ansi -pedantic -Wall -Wextra singly-LL.c
[arnuld@dune programs]$ ./a.out
List default
------------------
List after adding values
Num = 1
Num = 2
------------------
[arnuld@dune programs]$
Beej Jorgensen
to "int", which is _not_ something you should do, but it might help
illustrate why the code has no effect. (I chopped out most of the
function just to bring attention to the bits necessary for the
demonstration).
int list_add(int *base_node, const int i)
{
int s = *base_node;
int p = 3490; // your malloc used to be here
if( 0 == s )
{
s = p;
}
return *base_node;
}
Say you call this with:
int base = 0; // 0 in lieu of NULL
list_add(&base, 10);
What is there in list_add() that would cause the value of "base" in the
caller to change?
You're definitely on the right track from all the code I've seen posted.
-Beej
Beej Jorgensen
>So, the problem was I was using a local pointer to change the value of the
>passed argument. I don't see why it is wrong to do so though.
It was "wrong" because the local pointer was a copy of the passed-in
pointer, and modifying the local copy didn't change anything from the
perspective of the caller.
Let's mess up your toy program in the same way. First, your working
version:
void change_p1(int** p1, int* p2 ) // working
{
*p1 = p2;
}
(Play-by-play: p1 points to X, we dereference p1 to get X, and we assign
p2 into X, thus modifying it. Pretty straightforward.)
Now I'll break it to make it more comparable to the non-working list_add:
void change_p1(int** p1, int* p2 ) // BROKEN
{
int *foo = *p1;
foo = p2;
}
See that I never assigned anything to *p1, so nothing was changed from
the caller's perspective. Only the local value of "foo" changed, which
means nothing to the caller. (Play-by-play: p1 points to X, we use *p1
to get X, we make a copy of X in foo, and then we MODIFY THE COPY OF X
stored in foo. The original X pointed to by p1 is never modified, and
this is why it doesn't work.)
Now just for fun, let's make it work again, still using an intermediate
local variable:
void change_p1(int** p1, int* p2 ) // working again
{
int **frotz = p1;
*frotz = p2;
}
There's nothing stopping us from copying a pointer, so there I've copied
p1 into local variable frotz. p1 and frotz both point to the same thing
now (they're both pointing to the same int*). So I can dereference
either of them and modify what they both point to. (Play-by-play: p1
points to X, we copy p1 into frotz so frotz also points at X, we
dereference frotz to get X , and we assign p2 into it, thus modifying
X.) There are no copies of X in this example; there is only a copy of a
pointer to X.
To repeat myself, since frotz and p1 both point at the same thing, we
could dereference either of them to change what they both point at.
That is, I could have written "*p1 = p2" instead of "*frotz = p2" for
the exact same result, but then I would be right back at your working
example that I started with!
The important part is that we dereference p1 (or a copy of p1) and
assign into it. (If we don't we assign into whatever p1 points at,
we'll never modify it, of course!*) This is missing from the version
labeled "BROKEN", above.
-Beej, needs to sleep
* Please excuse my using the word "assign" to represent "all possible
ways of modifying a piece of data".
arnuld
>> arnuld <sunr...@invalid.address> writes:
> > I know in C everything is passed by value. When you pass a pointer to
> > some function it is copy of that pointer but that copy still points to the
> > place where original pointer was pointing. So, I can use it to change
> > that. Right or wrong ?
> Right. Do you see why your code above can't work though?
yes, because I was modifying the local pointer, not the one I go from
argument.
> I could just re-write this to work, but surely it would help you more
> if you work though what it does to see why it is not correct?
I have rewritten it but now it is not accomdating more than 2
elements. All of the elemets just vanish :(
/* This C implementation of singly linked list implements 3
operations: add, remove and insert elements at some specific position
in
* the list.
*
* VERISON 0.4
*
*/
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
/* How about always keeping track of tail of list (end of list I mean)
and then pass that to list_add(), that way, list_add() will always
be O(1), rather than O(n)
*/
struct my_struct* list_add( struct my_struct **, const int);
void list_print( const struct my_struct* );
void list_print_element(const struct my_struct *const );
struct my_struct
{
int num;
struct my_struct* next;
};
int main(void)
{
struct my_struct* list_head = NULL;
printf("List default\n");
list_print(list_head);
list_add(&list_head, 1);
list_add(&list_head, 2);
list_add(&list_head, 3);
list_print(list_head);
return 0;
}
struct my_struct* list_add(struct my_struct** head, const int i)
{
struct my_struct* ps = *head;
struct my_struct* p = malloc( 1 * sizeof(*p) );
if( NULL == p )
{
fprintf(stderr, "IN %s, %s: malloc() failed\n", __FILE__,
"list_add");
return NULL;
}
p->num = i;
p->next = NULL;
if( NULL == *head )
{
printf("Base Node was NULL, so adding current maloc()ed struct
to base: %d\n\n", p->num);
*head = p;
}
else
{
printf("Base node is non-NULL, so adding it to the end of the
list: %d\n", p->num);
for( ; NULL != (*head)->next; *head = (*head)->next ) ;
(*head)->next = p;
}
return ps;
}
void list_print( const struct my_struct *const sp )
{
const struct my_struct* p = sp;
for( ; NULL != p; p = p->next )
{
list_print_element(p);
}
printf("\n------------------\n");
}
void list_print_element(const struct my_struct *const p )
{
if( p )
{
printf("Num = %d\n", p->num);
}
else
{
printf("Can not print NULL struct \n");
}
}
============== OUTPUT ================
[arnuld@dune programs]$ gcc -ansi -pedantic -Wall -Wextra singly-LL.c
[arnuld@dune programs]$ ./a.out
List default
------------------
Base Node was NULL, so adding current maloc()ed struct to base: 1
Base node is non-NULL, so adding it to the end of the list: 2
Base node is non-NULL, so adding it to the end of the list: 3
Num = 2
Num = 3
------------------
[arnuld@dune programs]$
Ben Bacarisse
<snip>
> I have rewritten it but now it is not accomdating more than 2
> elements. All of the elemets just vanish :(
> struct my_struct* list_add(struct my_struct** head, const int i)
> {
> struct my_struct* ps = *head;
> struct my_struct* p = malloc( 1 * sizeof(*p) );
>
> if( NULL == p )
> {
> fprintf(stderr, "IN %s, %s: malloc() failed\n", __FILE__,
> "list_add");
> return NULL;
> }
>
> p->num = i;
> p->next = NULL;
>
>
> if( NULL == *head )
> {
> printf("Base Node was NULL, so adding current maloc()ed struct
> to base: %d\n\n", p->num);
> *head = p;
> }
> else
> {
> printf("Base node is non-NULL, so adding it to the end of the
> list: %d\n", p->num);
> for( ; NULL != (*head)->next; *head = (*head)->next ) ;
> (*head)->next = p;
The trouble is now you are modifying *head too much! It's fine to
change it above, but to add to the tail you need to find the last node
without changing *head. Just introduce a local pointer and use that
instead:
struct my_struct *tail;
for (tail = *head; NULL != tail->next; tail = tail->next);
tail->next = p;
> }
>
> return ps;
> }
--
Ben.
s0s...@gmail.com
> I'd make all the function names start with a common prefix
> (i.e. list_add, list_remove and so on). It is a shame that this does
> not produce natural meaning in English (the "list add" operation adds
> a list not an item to a list in plain English) but all programmers
> will know what you mean.
I'm not sure, but maybe people started doing this as a sort of OOP
analog?
In the absence of being able to say:
struct list
{
void add(int);
...
};
struct list* mylist = malloc(sizeof(struct list));
mylist->add(1);
we say:
struct list
{
...
};
void list_add(struct list*, int);
struct list* mylist = malloc(sizeof(struct list));
list_add(mylist, 1);
Sebastian
Barry Schwarz
wrote:
>> On Wed, 29 Apr 2009 05:23:30 -0700, Barry Schwarz wrote:
>>> On Tue, 28 Apr 2009 15:45:33 +0500, arnuld <sun...@invalid.address>
>
>>>int main(void)
>>>{
>>> struct my_struct* root_node = malloc( 1 * sizeof(*root_node));
>
>> The inner parentheses are superfluous.
>
>Just added them for clarity.
>
>
>
>
>>> if( NULL == p )
>> Is there some significance to the different spacing you use around
>> parentheses?
>
>I always use it like that otherwise I can't read properly.
Consistency would not have raised the issue. You code "( " only 40%
of the time and " )" only 35% of the time. For more than half you
code the parentheses without trailing/leading blanks.
arnuld
> Consistency would not have raised the issue. You code "( " only 40%
> of the time and " )" only 35% of the time. For more than half you
> code the parentheses without trailing/leading blanks.
I am sorry I was not clear, I use those single spaces in conditional cases
only (for, while, if, else etc.)
arnuld
> The trouble is now you are modifying *head too much! It's fine to
> change it above, but to add to the tail you need to find the last node
> without changing *head. Just introduce a local pointer and use that
> instead:
>
> struct my_struct *tail;
> for (tail = *head; NULL != tail->next; tail = tail->next);
> tail->next = p;
>
>> }
>>
>> return ps;
Okay ,it works but why ? the local pointer iterates the same way as *head
would iterate then why local pointer works but pointer from argument does
not. It may be stupid question but I really don't understand why using
pointer argument it never accommodates more than 2 elements.
arnuld
> The trouble is now you are modifying *head too much! It's fine to
> change it above, but to add to the tail you need to find the last node
> without changing *head. Just introduce a local pointer and use that
> instead:
>
> struct my_struct *tail;
> for (tail = *head; NULL != tail->next; tail = tail->next);
> tail->next = p;
>
>> }
>>
>> return ps;
okay, here is the working version finally, I understood everything that
has gone wrong so far :) . Any comments on newer version:
/* This C implementation of singly linked list implements 3 operations: add, remove and insert elements at some specific position in
* the list.
*
* VERISON 0.5
*
*/
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
/* How about always keeping track of tail of list (end of list I mean) and then pass that to list_add(), that way, list_add() will always
be O(1), rather than O(n)
*/
struct my_struct* list_add( struct my_struct **, const int);
void list_print( const struct my_struct* );
void list_print_element(const struct my_struct *const );
struct my_struct
{
int num;
struct my_struct* next;
};
int main(void)
{
struct my_struct* list_head = NULL;
printf("List default\n");
list_print(list_head);
list_add(&list_head, 1);
list_add(&list_head, 2);
list_add(&list_head, 3);
list_print(list_head);
return 0;
}
struct my_struct* list_add(struct my_struct** head, const int i)
{
struct my_struct *const ps = *head;
struct my_struct* p = malloc( 1 * sizeof(*p) );
if( NULL == p )
{
fprintf(stderr, "IN %s, %s: malloc() failed\n", __FILE__, "list_add");
return NULL;
}
p->num = i;
p->next = NULL;
if( NULL == *head )
{
/* printf("Base Node was NULL, so adding current maloc()ed struct to base: %d\n\n", p->num); */
return *head = p;
}
else
{/*
printf("list_head->num = %d\n", (*head)->num );
printf("Base node is non-NULL, so adding it to the end of the list: %d\n", p->num); */
for( ; NULL != (*head)->next; (*head) = (*head)->next ) ;
(*head)->next = p;
}
return *head = ps;
}
void list_print( const struct my_struct *const sp )
{
const struct my_struct* p = sp;
for( ; NULL != p; p = p->next )
{
list_print_element(p);
}
printf("\n------------------\n");
}
void list_print_element(const struct my_struct *const p )
{
if( p )
{
printf("Num = %d\n", p->num);
}
else
{
printf("Can not print NULL struct \n");
}
}
========================= OUTPUT =======================================
[arnuld@dune programs]$ gcc -ansi -pedantic -Wall -Wextra singly-LL.c
[arnuld@dune programs]$ ./a.out
List default
------------------
Num = 1
Num = 2
Num = 3
------------------
[arnuld@dune programs]$
arnuld
> The trouble is now you are modifying *head too much! It's fine to
> change it above, but to add to the tail you need to find the last node
> without changing *head. Just introduce a local pointer and use that
> instead:
> ..SNIP....
Hey Ben.. I understood the concept I think :) , thanks, I even implemented
the list_add() using assignment, the one you mention as (a) in some
earlier post, it works great:
/* This C implementation of singly linked list implements 3 operations: add, remove and insert elements at some specific position in
* the list.
*
* assignment VERISON 0.0
*
*/
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
/* How about always keeping track of tail of list (end of list I mean) and then pass that to list_add(), that way, list_add() will always
be O(1), rather than O(n)
*/
struct my_struct* list_add( struct my_struct *, const int);
void list_print( const struct my_struct* );
void list_print_element(const struct my_struct *const );
struct my_struct
{
int num;
struct my_struct* next;
};
int main(void)
{
struct my_struct* list_head = NULL;
printf("List default\n");
list_print(list_head);
list_head = list_add(list_head, 1);
list_head = list_add(list_head, 2);
list_head = list_add(list_head, 3);
list_print(list_head);
return 0;
}
struct my_struct* list_add(struct my_struct* head, const int i)
{
struct my_struct* s = head;
struct my_struct* p = malloc( 1 * sizeof(*p) );
if( NULL == p )
{
fprintf(stderr, "IN %s, %s: malloc() failed\n", __FILE__, "list_add");
return NULL;
}
p->num = i;
p->next = NULL;
if( NULL == s )
{
/* printf("Base Node was NULL, so adding current maloc()ed struct to base: %d\n\n", p->num); */
return head = p;
}
else
{/*
printf("list_head->num = %d\n", (*head)->num );
printf("Base node is non-NULL, so adding it to the end of the list: %d\n", p->num); */
for( ; NULL != head->next; head = head->next ) ;
head->next = p;
}
return s;
}
void list_print( const struct my_struct *const sp )
{
const struct my_struct* p = sp;
for( ; NULL != p; p = p->next )
{
list_print_element(p);
}
printf("\n------------------\n");
}
void list_print_element(const struct my_struct *const p )
{
if( p )
{
printf("Num = %d\n", p->num);
}
else
{
printf("Can not print NULL struct \n");
}
}
======================= OUTPUT =======================
[arnuld@dune programs]$ gcc -ansi -pedantic -Wall -Wextra singly-LL.c
[arnuld@dune programs]$ ./a.out
List default
------------------
Num = 1
Num = 2
Num = 3
------------------
[arnuld@dune programs]$
arnuld
> ....SNIP....
> You must decide between one of three different designs:
> (a) The list_add operation must always be used in an assignment. It
> return the new list: root = list_add(root, ...);
Done..
> (b) You must pass a pointer to the list pointer so that list_add can
> change it: list_add(&root, ...);
Done...
> (c) You pass a pointer to some overall list structure (not the same as
> the node structure) and list_add manipulates that.
This one has remained and I want to implement this now. You mean I need
to pass a pointer to the whole linked list (opposite to pointer to the
first element of the linked list). am I right ? Can you please
elaborate a little more ?
> You really should not get any further until you are certain that you
> can see why what you are doing can't work, and why all of the above are
> ways to solve this fundamental problem.
With your help the code I have written and posted I think I have started
to understand the things
nick_keigh...@hotmail.com
> On Apr 28, 6:22 pm, Ben Bacarisse <ben.use...@bsb.me.uk> wrote:
> > I'd make all the function names start with a common prefix
> > (i.e. list_add, list_remove and so on). It is a shame that this does
> > not produce natural meaning in English (the "list add" operation adds
> > a list not an item to a list in plain English) but all programmers
> > will know what you mean.
>
> I'm not sure, but maybe people started doing this as a sort of OOP
> analog?
this usage long preceeded wide acceptance (or even knowledge) of OOP.
It was partly a way of dividing up a namespace.
<snip>
Ben Bacarisse
... and there are various reasons why a common prefix is better than a
suffix. For example, related function sort close together in an index
of documentation. But the most important may well have been the
limited number of significant characters available to early linkers.
This strongly favours a short common prefix. The classic (and
topical) example being fopen, fread, fwrite and so on.
--
Ben.
Ben Bacarisse
>> On Tue, 05 May 2009 21:41:42 -0700, Barry Schwarz wrote:
>
>> Consistency would not have raised the issue. You code "( " only 40%
>> of the time and " )" only 35% of the time. For more than half you
>> code the parentheses without trailing/leading blanks.
>
> I am sorry I was not clear, I use those single spaces in conditional cases
> only (for, while, if, else etc.)
You do use them in all ifs, fors and whiles (you can't use them in a
else) but certainly not "only" in those cases:
| struct my_struct* add_to_list( struct my_struct *const, const int);
| struct my_struct* remove_from_list( struct my_struct *const, const int );
| void print_list( const struct my_struct* );
| struct my_struct* root_node = malloc( 1 * sizeof(*root_node));
| struct my_struct* add_to_list(struct my_struct *const base_node, const int i )
| struct my_struct* p = malloc( 1 * sizeof(*p));
| struct my_struct* remove_from_list( struct my_struct *const base_node, const int r )
| p = malloc( 1 * sizeof(*p));
| void print_list( const struct my_struct* p )
--
Ben.
Ben Bacarisse
>> On Mon, 04 May 2009 12:59:01 +0100, Ben Bacarisse wrote:
>
>> ....SNIP....
>
>> You must decide between one of three different designs:
Note the phrase *one of these*!
>> (a) The list_add operation must always be used in an assignment. It
>> return the new list: root = list_add(root, ...);
>
> Done..
>
>
>> (b) You must pass a pointer to the list pointer so that list_add can
>> change it: list_add(&root, ...);
>
> Done...
Doing both may be a problem but it is certainly a bit wasteful. The
advantage of (b) is you can use the return value for something else
(success/failure maybe or the location of the inserted item) and the
advantage of (a) is that list operations are simpler to write (you can
write list_reverse(list_add(list_reverse(my_list), 42))) so you loose
some advantage in both cases.
>> (c) You pass a pointer to some overall list structure (not the same as
>> the node structure) and list_add manipulates that.
>
> This one has remained and I want to implement this now. You mean I need
> to pass a pointer to the whole linked list (opposite to pointer to the
> first element of the linked list). am I right ? Can you please
> elaborate a little more ?
By this I meant you have a new structure that holds more information.
For example:
struct list {
struct list_node *head;
struct list_node *tail;
size_t length;
};
so you can add to either end and get the length in constant time. You
can combine (c) with (a) or (b). In other words, you still have the
same choices about how you set and or pass this new structure so in a
way I was wrong to suggest you pick *one of these*!
--
Ben.
Ben Bacarisse
> Any comments on newer version:
<snip>
> struct my_struct* list_add(struct my_struct** head, const int i)
> {
> struct my_struct *const ps = *head;
> struct my_struct* p = malloc( 1 * sizeof(*p) );
>
> if( NULL == p )
> {
> fprintf(stderr, "IN %s, %s: malloc() failed\n", __FILE__, "list_add");
> return NULL;
> }
>
> p->num = i;
> p->next = NULL;
>
>
> if( NULL == *head )
> {
> /* printf("Base Node was NULL, so adding current maloc()ed struct to base: %d\n\n", p->num); */
> return *head = p;
>
> }
> else
> {/*
> printf("list_head->num = %d\n", (*head)->num );
> printf("Base node is non-NULL, so adding it to the end of the list: %d\n", p->num); */
> for( ; NULL != (*head)->next; (*head) = (*head)->next ) ;
> (*head)->next = p;
> }
>
> return *head = ps;
I would not use *head in the loop only to set it back at then end.
That is what local variables are for!
> }
--
Ben.
Ben Bacarisse
> arnuld <sun...@invalid.address> writes:
>
>> On Mon, 04 May 2009 12:59:01 +0100, Ben Bacarisse wrote:
<snip>
>>> You must decide between one of three different designs:
>
> Note the phrase *one of these*!
>
>>> (a) The list_add operation must always be used in an assignment. It
>>> return the new list: root = list_add(root, ...);
>>
>> Done..
>>
>>> (b) You must pass a pointer to the list pointer so that list_add can
>>> change it: list_add(&root, ...);
>>
>> Done...
Ah, having read the thread I think you mean you have done both
separately to try them out. Sorry for the noise.
--
Ben.
arnuld
> You do use them in all ifs, fors and whiles (you can't use them in a
> else) but certainly not "only" in those cases:
>
> | struct my_struct* add_to_list( struct my_struct *const, const int);
> | struct my_struct* remove_from_list( struct my_struct *const, const int );
> | void print_list( const struct my_struct* );
> | struct my_struct* root_node = malloc( 1 * sizeof(*root_node));
> | struct my_struct* add_to_list(struct my_struct *const base_node, const int i )
> | struct my_struct* p = malloc( 1 * sizeof(*p));
> | struct my_struct* remove_from_list( struct my_struct *const base_node, const int r )
> | p = malloc( 1 * sizeof(*p));
> | void print_list( const struct my_struct* p )
Err... okay, I will stick to one spacing for wherever braces are used.
arnuld
> Doing both may be a problem but it is certainly a bit wasteful. The
> advantage of (b) is you can use the return value for something else
> (success/failure maybe or the location of the inserted item) and the
> advantage of (a) is that list operations are simpler to write (you can
> write list_reverse(list_add(list_reverse(my_list), 42))) so you loose
> some advantage in both cases.
Yes, I am confused on this. (b) gives me the exact logic that is going on
but it looks messy as compared to (a). (a) looks much clean but then I am
not using the pointer for what they are originally designed (to modify the
original passed argument to a function).
I think I will stick with (b), I haven't tried (c) yet. I have even
written a list_remove_element() function using (b) and it works cool 8) .
Down here is the code. I am using a one new pointer for the tail of the
list.
> By this I meant you have a new structure that holds more information.
> For example:
>
> struct list {
> struct list_node *head;
> struct list_node *tail;
> size_t length;
> };
Hey.. I guess you forgot including "struct list_node* next".
> so you can add to either end and get the length in constant time. You
> can combine (c) with (a) or (b). In other words, you still have the
> same choices about how you set and or pass this new structure so in a
> way I was wrong to suggest you pick *one of these*!
I want to try (c) anyway, so this will be the new struct:
struct list {
struct list_node *head;
struct list_node *tail;
size_t length;
struct list_node *next;
};
So, I have to keep on updating all these 4 members whenever I add/remove
elements from the linked list. Is it technically efficient or better in
the way we design C programs as compared to using only one member (*next)
and then when we want length or add or remove elements, we just iterate
over the list (of say 1000 elements) ?
Ben Bacarisse
>> On Wed, 06 May 2009 13:48:52 +0100, Ben Bacarisse wrote:
>
>> Doing both may be a problem but it is certainly a bit wasteful. The
>> advantage of (b) is you can use the return value for something else
>> (success/failure maybe or the location of the inserted item) and the
>> advantage of (a) is that list operations are simpler to write (you can
>> write list_reverse(list_add(list_reverse(my_list), 42))) so you loose
>> some advantage in both cases.
>
> Yes, I am confused on this. (b) gives me the exact logic that is going on
> but it looks messy as compared to (a). (a) looks much clean but then I am
> not using the pointer for what they are originally designed (to modify the
> original passed argument to a function).
But it sometimes is! In the (a) design:
struct list_node *list_add(struct list_node *l, int i);
three cases occur. (1) the list is empty and we don't change the
thing pointed to by l (l is NULL) and return the new node. (2) the
list has one item in it so we do change the node pointer to by l. (3)
this list is longer and we change some node reachable by l.
Note that pointer are no simply used to change things in the caller.
There are other reasons to use them.
> I think I will stick with (b), I haven't tried (c) yet. I have even
> written a list_remove_element() function using (b) and it works cool 8) .
> Down here is the code. I am using a one new pointer for the tail of the
> list.
>
>> By this I meant you have a new structure that holds more information.
>> For example:
>>
>> struct list {
>> struct list_node *head;
>> struct list_node *tail;
>> size_t length;
>> };
>
> Hey.. I guess you forgot including "struct list_node* next".
No. The list_node will have next in it. This structure is the one
that represents the "whole list". The list_node structure represents
the nodes in the list.
>> so you can add to either end and get the length in constant time. You
>> can combine (c) with (a) or (b). In other words, you still have the
>> same choices about how you set and or pass this new structure so in a
>> way I was wrong to suggest you pick *one of these*!
>
>
> I want to try (c) anyway, so this will be the new struct:
>
> struct list {
> struct list_node *head;
> struct list_node *tail;
> size_t length;
> struct list_node *next;
No!!!
> };
>
> So, I have to keep on updating all these 4 members whenever I add/remove
> elements from the linked list. Is it technically efficient or better in
> the way we design C programs as compared to using only one member (*next)
> and then when we want length or add or remove elements, we just iterate
> over the list (of say 1000 elements) ?
First, you need to see that there are two structures. One has stuff
about the whole list (its head, its tail, its length) and the other
will have the data and the next pointers. Once you get that, I think
your question will evaporate.
--
Ben.
Default User
> > On Wed, 06 May 2009 13:48:52 +0100, Ben Bacarisse wrote:
> > By this I meant you have a new structure that holds more
> > information. For example:
> >
> > struct list {
> > struct list_node *head;
> > struct list_node *tail;
> > size_t length;
> > };
>
> Hey.. I guess you forgot including "struct list_node* next".
No, he's using a separate structure to store characteristics of the
list. It's what I called a list manager in my text-adventure game code:
struct node
{
enum list_type type;
void *item;
struct node *next;
};
struct list_manager
{
int num;
int max;
struct node *head;
struct node *tail;
};
In my code, lists could have a maximum length, and you could have the
code for lists storing different data types. With a bit more code, you
could have a heterogeneous list, storing different types in the same
list.
> I want to try (c) anyway, so this will be the new struct:
>
> struct list {
> struct list_node *head;
> struct list_node *tail;
> size_t length;
> struct list_node *next;
> };
>
>
> So, I have to keep on updating all these 4 members whenever I
> add/remove elements from the linked list. Is it technically efficient
> or better in the way we design C programs as compared to using only
> one member (*next) and then when we want length or add or remove
> elements, we just iterate over the list (of say 1000 elements) ?
You don't want to do this. You're mixing concepts of a manager and a
node. If each node carries the length, you'd have to go through the
list and update all that information each time for every node. That
makes things worse.
Brian
--
Day 93 of the "no grouchy usenet posts" project
Barry Schwarz
wrote:
snip
>/* This C implementation of singly linked list implements 3 operations: add, remove and insert elements at some specific position in
> * the list.
I don't see an insert function.
At this point, head is a local variable (parameter). Assigning a
value to it just prior to returning accomplishes nothing. This has
the same effect as
return p;
> }
> else
> {/*
> printf("list_head->num = %d\n", (*head)->num );
head is a pointer. *head is a struct. You cannot use the -> operator
on a struct. It is either head->num or (*head).num. (Yes, I know
it's a comment.)
> printf("Base node is non-NULL, so adding it to the end of the list: %d\n", p->num); */
> for( ; NULL != head->next; head = head->next ) ;
> head->next = p;
> }
>
> return s;
>}
>
>
>
>void list_print( const struct my_struct *const sp )
>{
> const struct my_struct* p = sp;
Why did you make sp a constant pointer? Changing a scalar variable in
a function never changes the copy in the calling program. If sp is
not const, you wouldn't need p.
>
> for( ; NULL != p; p = p->next )
> {
> list_print_element(p);
> }
>
> printf("\n------------------\n");
>}
>
>
>void list_print_element(const struct my_struct *const p )
>{
> if( p )
> {
> printf("Num = %d\n", p->num);
> }
> else
> {
> printf("Can not print NULL struct \n");
> }
>}
>
>
>======================= OUTPUT =======================
>[arnuld@dune programs]$ gcc -ansi -pedantic -Wall -Wextra singly-LL.c
>[arnuld@dune programs]$ ./a.out
>List default
>
>------------------
>Num = 1
>Num = 2
>Num = 3
>
>------------------
>[arnuld@dune programs]$
--
Remove del for email
arnuld
>> arnuld wrote:
> I don't see an insert function.
well, I had it earlier, as I was reading Aho, Hopcraft and Ullman's book.
But then I saw we never (almost in most cases) insert some element at some
specific position in a linked list, so it did not look practical, hence I
dropped it.
>>void list_print( const struct my_struct *const sp ) {
>> const struct my_struct* p = sp;
> Why did you make sp a constant pointer? Changing a scalar variable in a
> function never changes the copy in the calling program. If sp is not
> const, you wouldn't need p.
I make them constants to make sure and clear that function is not supposed
to change the arguments, a habit I learned from clc itself.
arnuld
> First, you need to see that there are two structures. One has stuff
> about the whole list (its head, its tail, its length) and the other
> will have the data and the next pointers. Once you get that, I think
> your question will evaporate.
Okay, I have made 2 structures but now I get a Segfault in list_add() at
this line:
(*t)->head = *s;
Here is the code:
/* This C implementation of singly linked list implements 3 operations: add, remove and print elements in the list. Its is the modified
* version of my singly linked list suggested by Ben from comp.lang.c . I was using one struct to do all the operations but Ben added
* a 2nd struct to make things easier and efficient.
*
* I was always using the strategy of searching through the list to find the end and then addd the value there. That way list_add() was
* O(n). Now I am keeping track of tail and always use tail to add to the linked list, so the addition is always O(1), only at the cost
* of one assignment.
*
*
* VERISON 0.0
*
*/
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
struct my_struct
{
int num;
struct my_struct* next;
};
struct my_list
{
struct my_struct* head;
struct my_struct* tail;
};
struct my_struct* list_add( struct my_struct**, struct my_list**, const int);
void list_print( const struct my_struct* );
void list_print_element(const struct my_struct *const );
int main(void)
{
struct my_struct* ms = NULL;
struct my_list* mt = NULL;
list_add(&ms, &mt, 1);
return 0;
}
/* Will always return the list head */
struct my_struct* list_add(struct my_struct** s, struct my_list** t, const int i)
{
struct my_struct* p = malloc( 1 * sizeof(*p) );
if( NULL == p )
{
fprintf(stderr, "IN %s, %s: malloc() failed\n", __FILE__, "list_add");
return NULL;
}
p->num = i;
p->next = NULL;
if( NULL == *s && NULL == *t)
{
printf("Empty list, adding p->num: %d\n\n", p->num);
printf("*s = %p\n", (void*)*s);
*s = p;
printf("*s = %p\n", (void*)*s);
printf("*t = %p\n", (void*)*t);
(*t)->head = *s;
printf("my_list head is assigned\n");
(*t)->tail = *s;
printf("my_list tail is assigned\n");
return (*t)->head;
}
else if( NULL == *s || NULL == *t )
{
printf("Something is seriously wrong with the assignment of head and tail\n");
return NULL;
}
else
{
(*t)->tail->next = p;
return (*t)->head;
}
}
void list_print( const struct my_struct *const sp )
{
const struct my_struct* p = sp;
for( ; NULL != p; p = p->next )
{
list_print_element(p);
}
printf("\n------------------\n");
}
void list_print_element(const struct my_struct *const p )
{
if( p )
{
printf("Num = %d\n", p->num);
}
else
{
printf("Can not print NULL struct \n");
}
}
--
James Kuyper
>> On Wed, 06 May 2009 21:13:48 -0700, Barry Schwarz wrote:
>>> arnuld wrote:
>
>
>> I don't see an insert function.
>
> well, I had it earlier, as I was reading Aho, Hopcraft and Ullman's book.
> But then I saw we never (almost in most cases) insert some element at some
> specific position in a linked list, so it did not look practical, hence I
> dropped it.
It's trivial to implement insertion, and that's one of the key
advantages of lists over other data structures. If you seldom need to
insert or remove from the middle of a list, a list might not be the
appropriate data structure for your application.
...
>>> void list_print( const struct my_struct *const sp ) {
>>> const struct my_struct* p = sp;
>
>> Why did you make sp a constant pointer? Changing a scalar variable in a
>> function never changes the copy in the calling program. If sp is not
>> const, you wouldn't need p.
>
> I make them constants to make sure and clear that function is not supposed
> to change the arguments, a habit I learned from clc itself.
sp is the parameter, not the argument. You can't change the argument by
changing the parameter. Consider the following possible declarations:
1. const struct my_struct * const sp
2. const struct my_struct * sp
3. struct my_struct * const sp
4. struct my_struct * sp
Neither 1 nor 3 allow you to change sp. Neither 1 nor 2 allow you to
change the thing that sp points at. You reason you give is a reason for
favoring either 1 and 2, over 3 or 4, but that's not what he's asking
you about. He's asking you why you chose 1 rather than 2.
Ben Bacarisse
>> On Wed, 06 May 2009 16:50:23 +0100, Ben Bacarisse wrote:
>
>
>> First, you need to see that there are two structures. One has stuff
>> about the whole list (its head, its tail, its length) and the other
>> will have the data and the next pointers. Once you get that, I think
>> your question will evaporate.
>
>
> Okay, I have made 2 structures but now I get a Segfault in list_add() at
> this line:
>
> (*t)->head = *s;
>
> Here is the code:
<snip>
>
> struct my_struct
> {
> int num;
> struct my_struct* next;
> };
>
>
> struct my_list
> {
> struct my_struct* head;
> struct my_struct* tail;
> };
>
>
> struct my_struct* list_add( struct my_struct**, struct my_list**,
> const int);
The purpose of the new struct is to avoid having to pass pointer to
the second. All list operations just use a struct my_list *. If you
insist, they could use a struct my_list ** but I don't like that
design.
I would declare the list_add function like this:
struct my_list *list_add(struct my_struct*, int);
You either have to provide an "constructor":
struct my_list *list_new(void);
or you need to tell users to initialise the list structure themselves:
struct my_list list_of_ints = {NULL, NULL};
I would advice you do the first.
> void list_print( const struct my_struct* );
list_print would take a struct my_list *.
<snip>
> struct my_struct* list_add(struct my_struct** s, struct my_list** t, const int i)
> {
> struct my_struct* p = malloc( 1 * sizeof(*p) );
>
> if( NULL == p )
> {
> fprintf(stderr, "IN %s, %s: malloc() failed\n", __FILE__, "list_add");
> return NULL;
> }
>
> p->num = i;
> p->next = NULL;
>
>
> if( NULL == *s && NULL == *t)
> {
> printf("Empty list, adding p->num: %d\n\n", p->num);
> printf("*s = %p\n", (void*)*s);
> *s = p;
> printf("*s = %p\n", (void*)*s);
> printf("*t = %p\n", (void*)*t);
> (*t)->head = *s;
If *t is NULL (guaranteed by the if condition) then (*t0)->head is not
valid. I won't advice on what you do to correct this, since I don't
think you have the API sorted out first.
<snip>
--
Ben.
arnuld
> It's trivial to implement insertion, and that's one of the key
> advantages of lists over other data structures. If you seldom need to
> insert or remove from the middle of a list, a list might not be the
> appropriate data structure for your application.
Seldom ? .. Right now the software I am working on, never ever goes
anywhere except the first and last elements of the list. Its so sad that I
can't disclose the code here :( ,but here is whta it is doing:
1) list_add() always adds element to the end of the list.
2) list_remove() always removes the first element (or the whole list).
3) Its all happening at run time.
4) its has to be in C, not in any other language.
So you think using linked list in such a case is wrong idea ? which data
structure will be better then.
> sp is the parameter, not the argument. You can't change the argument by
> changing the parameter. Consider the following possible declarations:
Wait.., parameter is the object that you pass to the function() then what
is the argument ?
int i;
my_add(i);
"i" is the parameter, what is the argument ?
> 1. const struct my_struct * const sp
> 2. const struct my_struct * sp
> 3. struct my_struct * const sp
> 4. struct my_struct * sp
> Neither 1 nor 3 allow you to change sp. Neither 1 nor 2 allow you to
> change the thing that sp points at. You reason you give is a reason for
> favoring either 1 and 2, over 3 or 4, but that's not what he's asking
> you about. He's asking you why you chose 1 rather than 2.
Oh.. now I understood the question. I know its a local pointer and
changing it will not make any difference but I just wanted to be clear
that this function is not supposed to change anything at all. I thought it
was logical to do such a thing for a function which is supposed to
only print its parameters.
arnuld
>> arnuld <sun...@invalid.address> writes:
> The purpose of the new struct is to avoid having to pass pointer to
> the second. All list operations just use a struct my_list *. If you
> insist, they could use a struct my_list ** but I don't like that
> design.
>
> I would declare the list_add function like this:
>
> struct my_list *list_add(struct my_struct*, int);
Okay, I will use this but how am I suppose to return a my_list* when it is
neither global and nor passed to the function. From where I am supposed to
either get or set the head and tail of my_list ?
nick_keigh...@hotmail.com
> > On Thu, 07 May 2009 13:08:35 +0000, James Kuyper wrote:
> > It's trivial to implement insertion, and that's one of the key
> > advantages of lists over other data structures. If you seldom need to
> > insert or remove from the middle of a list, a list might not be the
> > appropriate data structure for your application.
not sure I agree..
> Seldom ? .. Right now the software I am working on, never ever goes
> anywhere except the first and last elements of the list. Its so sad that I
> can't disclose the code here :( ,but here is whta it is doing:
>
> 1) list_add() always adds element to the end of the list.
> 2) list_remove() always removes the first element (or the whole list).
> 3) Its all happening at run time.
> 4) its has to be in C, not in any other language.
sounds like a queue. A linked list sounds like a pretty good
underlying data
structure. I've implemented quite few of these.
> So you think using linked list in such a case is wrong idea ? which data
> structure will be better then.
>
> > sp is the parameter, not the argument. You can't change the argument by
> > changing the parameter. Consider the following possible declarations:
>
> Wait.., parameter is the object that you pass to the function() then what
> is the argument ?
he's being nit-picky
> int i;
> my_add(i);
>
> "i" is the parameter, what is the argument ?
>
> > 1. const struct my_struct * const sp
> > 2. const struct my_struct * sp
> > 3. struct my_struct * const sp
> > 4. struct my_struct * sp
> > Neither 1 nor 3 allow you to change sp. Neither 1 nor 2 allow you to
> > change the thing that sp points at. You reason you give is a reason for
> > favoring either 1 and 2, over 3 or 4, but that's not what he's asking
> > you about. He's asking you why you chose 1 rather than 2.
<snip>
<hyphen><hyphen><space>
Look, I am French, and even worst, I live in Paris.
I know something about fads really.
Jacob Navia
arnuld
> The purpose of the new struct is to avoid having to pass pointer to
> the second. All list operations just use a struct my_list *. If you
> insist, they could use a struct my_list ** but I don't like that
> design.
> .. SNIP....
> If *t is NULL (guaranteed by the if condition) then (*t0)->head is not
> valid. I won't advice on what you do to correct this, since I don't
> think you have the API sorted out first.
Here is the new code according to your design ans it works :) , any more
improvements that are needed ?
/* This C implementation of singly linked list implements 3 operations: add, remove and print elements in the list. Its is the modified
* version of my singly linked list suggested by Ben from comp.lang.c . I was using one struct to do all the operations but Ben added
* a 2nd struct to make things easier and efficient.
*
* I was always using the strategy of searching through the list to find the end and then addd the value there. That way list_add() was
* O(n). Now I am keeping track of tail and always use tail to add to the linked list, so the addition is always O(1), only at the cost
* of one assignment.
*
*
* VERISON 0.2
*
*/
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
struct my_struct
{
int num;
struct my_struct* next;
};
struct my_list
{
struct my_struct* head;
struct my_struct* tail;
};
struct my_struct* list_add_element( struct my_list*, const int);
struct my_list* list_new(void);
void list_print( const struct my_list* );
void list_print_element(const struct my_struct* );
int main(void)
{
struct my_struct* ms = NULL;
struct my_list* mt = NULL;
mt = list_new();
ms = mt->head = list_add_element(mt, 1);
ms = mt->head = list_add_element(mt, 2);
ms = mt->head = list_add_element(mt, 3);
ms = mt->head = list_add_element(mt, 4);
list_print(mt);
return 0;
}
/* Will always return the list head */
struct my_struct* list_add_element(struct my_list* s, const int i)
{
struct my_struct* p = malloc( 1 * sizeof(*p) );
if( NULL == p )
{
fprintf(stderr, "IN %s, %s: malloc() failed\n", __FILE__, "list_add");
return NULL;
}
p->num = i;
p->next = NULL;
if( NULL == s->head && NULL == s->tail )
{
/* printf("Empty list, adding p->num: %d\n\n", p->num); */
s->tail = p;
return p;
}
else if( NULL == s->head || NULL == s->tail )
{
fprintf(stderr, "There is something seriously wrong with your assignment of head/tail to the list\n");
return NULL;
}
else
{
/* printf("List not empty, adding element to tail\n"); */
s->tail->next = p;
s->tail = p;
}
return s->head;
}
/* ---------------------- small helper fucntions ---------------------------------- */
struct my_list* list_new(void)
{
struct my_list* p = malloc( 1 * sizeof(*p));
if( NULL == p )
{
fprintf(stderr, "LINE: %d, malloc() failed\n", __LINE__);
}
return p;
}
void list_print( const struct my_list* ps )
{
struct my_struct* p = ps->head;
BartC
"arnuld" <sun...@invalid.address> wrote in message
news:pan.2009.05.08....@invalid.address...
> void list_print( const struct my_list* ps )
> {
> struct my_struct* p = ps->head;
>
> for( ; NULL != p; p = p->next )
This is not wrong but... incredibly annoying!
What's p initialised to in this loop? You have to look (in real code)
potentially hundreds of lines further up to see the definition of p buried
amongst possibly dozens of other declarations.
Why not:
for (p = ps->head ; NULL != p; p = p->next )
This way you can also execute the loop more than once in the function! Or
you can copy and paste the code somewhere else. It's now self-contained. And
even better:
for(p = ps->head ; p!=NULL; p = p->next )
Since the naff-looking backwards compare was designed for use with ==. (And
in fact you can leave out the !=NULL although I think it's clearer like
this)
Oh, and I still don't get all these 'const's everywhere, /maybe/ there're
good reasons for them but I just see extra clutter:
>void list_print_element(const struct my_struct *const p )
How many params does this function take, 2, 3, not it's just one! Why does
it need two const attributes?
--
Bart
James Kuyper
>> On Thu, 07 May 2009 13:08:35 +0000, James Kuyper wrote:
>
>> It's trivial to implement insertion, and that's one of the key
>> advantages of lists over other data structures. If you seldom need to
>> insert or remove from the middle of a list, a list might not be the
>> appropriate data structure for your application.
>
>
> Seldom ? .. Right now the software I am working on, never ever goes
> anywhere except the first and last elements of the list. Its so sad that I
> can't disclose the code here :( ,but here is whta it is doing:
>
> 1) list_add() always adds element to the end of the list.
> 2) list_remove() always removes the first element (or the whole list).
> 3) Its all happening at run time.
> 4) its has to be in C, not in any other language.
>
>
> So you think using linked list in such a case is wrong idea ? which data
> structure will be better then.
A queue - see <http://en.wikipedia.org/wiki/Queue_(data_structure)>.
While a linked list is certainly one way to implement a queue, a
circular buffer (see links on that same page) could be a better
approach, if you can accept a fixed upper limit to the number of
elements in the queue. It avoids the space overhead of having each node
contain a pointer to the next element in the queue, and it avoids the
time overhead associated with allocating and deallocating each node.
>> sp is the parameter, not the argument. You can't change the argument by
>> changing the parameter. Consider the following possible declarations:
>
> Wait.., parameter is the object that you pass to the function() then what
> is the argument ?
An argument is an expression whose value is passed to the function. The
corresponding parameter is a variable, defined in the parameter list of
the function definition, that contains a copy of that value. Even if the
expression is a variable, the parameter is NOT the same as the argument,
it only contains a copy of the value of the argument.
The term "actual parameter" is sometimes used for "argument", and the
term "formal argument" is sometimes used for "parameter". The standard
explicitly acknowledges these usages in the "Definitions" section, but
it also quite rightly deprecates them. You need to be clear about the
distinction between the two concepts, and using phrases that conflate
them only gets in the way of learning that distinction.
> int i;
> my_add(i);
>
> "i" is the parameter, what is the argument ?
'i' is the argument of my_add(). If the definition of my_add() were to
start as follows:
void my_add(int n)
{
...
Then 'n' would be the corresponding parameter.
>> 1. const struct my_struct * const sp
>> 2. const struct my_struct * sp
>> 3. struct my_struct * const sp
>> 4. struct my_struct * sp
>
>> Neither 1 nor 3 allow you to change sp. Neither 1 nor 2 allow you to
>> change the thing that sp points at. You reason you give is a reason for
>> favoring either 1 and 2, over 3 or 4, but that's not what he's asking
>> you about. He's asking you why you chose 1 rather than 2.
>
> Oh.. now I understood the question. I know its a local pointer and
> changing it will not make any difference but I just wanted to be clear
> that this function is not supposed to change anything at all. I thought it
> was logical to do such a thing for a function which is supposed to
> only print its parameters.
Declaring a parameter to be const can make sense for exactly the same
reasons that declaring any other local variable const might make sense.
I would not consider it objectionable, but I would want to make sure
that you understand that making 'sp' const has nothing to do with
protecting the argument of the function from modification.
James Kuyper
>
> "arnuld" <sun...@invalid.address> wrote in message
> news:pan.2009.05.08....@invalid.address...
>> void list_print_element(const struct my_struct *const p )
>
> How many params does this function take, 2, 3, not it's just one! Why does
> it need two const attributes?
One to indicate that *p should not be modified; the second to indicate
that p itself should not be modified. I see no harm in it, so long as
there is no need to modify p, and if that's the case the problem will
pop up as soon as the code is compiled.
Ben Bacarisse
<snip>
> <hyphen><hyphen><space>
A curious and little-know fact: if you can type (or cut-and paste) the
sequence -- (that's hyphen hyphen no-break-space) into GG, the
no-break space turns into a space and is retained.
--
Ben.
Ben Bacarisse
Rats. My mistake. I meant to write:
struct my_list *list_add(struct my_list*, int);
The point was that you should have no need to expose the node
structure at all (the one you call, rather unhelpfully, my_struct).
--
Ben.
Ben Bacarisse
>> On Thu, 07 May 2009 17:07:21 +0100, Ben Bacarisse wrote:
>
>
>> The purpose of the new struct is to avoid having to pass pointer to
>> the second. All list operations just use a struct my_list *. If you
>> insist, they could use a struct my_list ** but I don't like that
>> design.
>
>> .. SNIP....
>
>> If *t is NULL (guaranteed by the if condition) then (*t0)->head is not
>> valid. I won't advice on what you do to correct this, since I don't
>> think you have the API sorted out first.
>
>
> Here is the new code according to your design ans it works :) , any more
> improvements that are needed ?
<snip>
> struct my_struct
> {
> int num;
> struct my_struct* next;
> };
>
>
> struct my_list
> {
> struct my_struct* head;
> struct my_struct* tail;
> };
>
>
> struct my_struct* list_add_element( struct my_list*, const int);
I can't see the value in returning a node pointer here. A pointer to
the list is more useful, in my opinion. It does indicate failure when
there is no memory for a node, but that is rare enough that I'd handle
that differently. A "production strength" list type might have an
error indicator in the list structure to signal when things have gone
wrong, but there are other ways as well.
> struct my_list* list_new(void);
>
> void list_print( const struct my_list* );
> void list_print_element(const struct my_struct* );
>
>
> int main(void)
> {
>
> struct my_struct* ms = NULL;
> struct my_list* mt = NULL;
>
> mt = list_new();
> ms = mt->head = list_add_element(mt, 1);
> ms = mt->head = list_add_element(mt, 2);
> ms = mt->head = list_add_element(mt, 3);
> ms = mt->head = list_add_element(mt, 4);
This way too messy. There is no need to have these mode pointers and
there should be no need to set mt->head all the time.
> list_print(mt);
>
> return 0;
> }
--
Ben.
arnuld
> I can't see the value in returning a node pointer here. A pointer to
> the list is more useful, in my opinion. It does indicate failure when
> there is no memory for a node, but that is rare enough that I'd handle
> that differently. A "production strength" list type might have an
> error indicator in the list structure to signal when things have gone
> wrong, but there are other ways as well.
> ...SNIP....
How is this one:
/* This C implementation of singly linked list implements 3 operations: add, remove and print elements in the list. Its is the modified
* version of my singly linked list suggested by Ben from comp.lang.c . I was using one struct to do all the operations but Ben added
* a 2nd struct to make things easier and efficient.
*
* I was always using the strategy of searching through the list to find the end and then addd the value there. That way list_add() was
* O(n). Now I am keeping track of tail and always use tail to add to the linked list, so the addition is always O(1), only at the cost
* of one assignment.
*
*
* VERISON 0.3
*
*/
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
struct my_struct
{
int num;
struct my_struct* next;
};
struct my_list
{
struct my_struct* head;
struct my_struct* tail;
};
struct my_list* list_add_element( struct my_list*, const int);
struct my_list* list_new(void);
void list_print( const struct my_list* );
void list_print_element(const struct my_struct* );
int main(void)
{
struct my_list* mt = NULL;
mt = list_new();
list_add_element(mt, 1);
list_add_element(mt, 2);
list_add_element(mt, 3);
list_add_element(mt, 4);
list_print(mt);
return 0;
}
/* Will always return the list head */
struct my_list* list_add_element(struct my_list* s, const int i)
{
struct my_struct* p = malloc( 1 * sizeof(*p) );
if( NULL == p )
{
fprintf(stderr, "IN %s, %s: malloc() failed\n", __FILE__, "list_add");
return NULL;
}
p->num = i;
p->next = NULL;
if( NULL == s->head && NULL == s->tail )
{
/* printf("Empty list, adding p->num: %d\n\n", p->num); */
s->head = s->tail = p;
return s;
}
else if( NULL == s->head || NULL == s->tail )
{
fprintf(stderr, "There is something seriously wrong with your assignment of head/tail to the list\n");
free(p);
return NULL;
}
else
{
/* printf("List not empty, adding element to tail\n"); */
s->tail->next = p;
s->tail = p;
}
return s;
}
/* ---------------------- small helper fucntions ---------------------------------- */
struct my_list* list_new(void)
{
struct my_list* p = malloc( 1 * sizeof(*p));
if( NULL == p )
{
fprintf(stderr, "LINE: %d, malloc() failed\n", __LINE__);
}
return p;
}
void list_print( const struct my_list *const ps )
{
struct my_struct* p = NULL;
for( p = ps->head; p; p = p->next )
{
list_print_element(p);
}
printf("------------------\n");
arnuld
>> arnuld wrote:
> A queue - see <http://en.wikipedia.org/wiki/Queue_(data_structure)>.
> While a linked list is certainly one way to implement a queue, a
> circular buffer (see links on that same page) could be a better
> approach, if you can accept a fixed upper limit to the number of
> elements in the queue. It avoids the space overhead of having each node
> contain a pointer to the next element in the queue, and it avoids the
> time overhead associated with allocating and deallocating each node.
Well, it can't happen as I have no idea how many elements in the list
will be, that could be 2 or 100 or 9,222.
BTW, even if the upper size is fixed (say 10,000), then if there only 100
elements then it wouldn't it cause the space overhead for extra 9900
elements (in case of circular buffer) ?
> Declaring a parameter to be const can make sense for exactly the same
> reasons that declaring any other local variable const might make sense.
> I would not consider it objectionable, but I would want to make sure
> that you understand that making 'sp' const has nothing to do with
> protecting the argument of the function from modification.
Now I understand, that 2nd const will be useful only in case I am passing
the address of the original pointer which is not the case here.
Ben Bacarisse
> How is this one:
It's good. Not quite correct, but very close.
<snip>
> struct my_list* list_add_element( struct my_list*, const int);
>
> struct my_list* list_new(void);
>
> void list_print( const struct my_list* );
> void list_print_element(const struct my_struct* );
>
>
> int main(void)
> {
> struct my_list* mt = NULL;
>
> mt = list_new();
> list_add_element(mt, 1);
> list_add_element(mt, 2);
> list_add_element(mt, 3);
> list_add_element(mt, 4);
>
> list_print(mt);
>
> return 0;
> }
>
>
> /* Will always return the list head */
This comment is now wrong.
> struct my_list* list_add_element(struct my_list* s, const int i)
> {
> struct my_struct* p = malloc( 1 * sizeof(*p) );
>
> if( NULL == p )
> {
> fprintf(stderr, "IN %s, %s: malloc() failed\n", __FILE__, "list_add");
> return NULL;
I'd return s here.
> }
>
> p->num = i;
> p->next = NULL;
>
>
> if( NULL == s->head && NULL == s->tail )
> {
> /* printf("Empty list, adding p->num: %d\n\n", p->num); */
> s->head = s->tail = p;
> return s;
> }
> else if( NULL == s->head || NULL == s->tail )
> {
> fprintf(stderr, "There is something seriously wrong with your assignment of head/tail to the list\n");
> free(p);
> return NULL;
> }
> else
> {
> /* printf("List not empty, adding element to tail\n"); */
> s->tail->next = p;
> s->tail = p;
> }
>
> return s;
> }
>
>
>
> /* ---------------------- small helper fucntions ---------------------------------- */
> struct my_list* list_new(void)
> {
> struct my_list* p = malloc( 1 * sizeof(*p));
>
> if( NULL == p )
> {
> fprintf(stderr, "LINE: %d, malloc() failed\n", __LINE__);
> }
You don't set head or tail here (or anywhere) so currently the code
works by accident. I'd set p->head = p->tail = NULL; here.
> return p;
> }
>
>
> void list_print( const struct my_list *const ps )
> {
> struct my_struct* p = NULL;
>
> for( p = ps->head; p; p = p->next )
> {
> list_print_element(p);
> }
>
> printf("------------------\n");
If you remove this last bit, this function could be very general. It
can be helpful to define a "do this to each element" function that
takes a function as an argument. If you write the loop carefully it
can be used to both free the list nodes and print the list. This will
only be worth it if you are writing quite a general list
implementation.
> }
>
>
> void list_print_element(const struct my_struct *const p )
> {
> if( p )
> {
> printf("Num = %d\n", p->num);
> }
> else
> {
> printf("Can not print NULL struct \n");
> }
> }
--
Ben.
James Kuyper
>> On Fri, 08 May 2009 10:51:05 +0000, James Kuyper wrote:
>>> arnuld wrote:
>
>> A queue - see <http://en.wikipedia.org/wiki/Queue_(data_structure)>.
>> While a linked list is certainly one way to implement a queue, a
>> circular buffer (see links on that same page) could be a better
>> approach, if you can accept a fixed upper limit to the number of
>> elements in the queue. It avoids the space overhead of having each node
>> contain a pointer to the next element in the queue, and it avoids the
>> time overhead associated with allocating and deallocating each node.
>
> Well, it can't happen as I have no idea how many elements in the list
> will be, that could be 2 or 100 or 9,222.
>
>
> BTW, even if the upper size is fixed (say 10,000), then if there only 100
> elements then it wouldn't it cause the space overhead for extra 9900
> elements (in case of circular buffer) ?
Sure, it's a trade-off. A fixed sized circular buffer has advantages an
disadvantages; a linked list has different advantages and disadvantages.
The only way to be sure which structure is more appropriate is to
compare those advantages and disadvantages. If you have a small node
size and a relatively stable queue length, a circular buffer can be the
best option. If you have a large node size and a highly variable queue
length, the linked list may be a better option. That's why I was very
careful, in my initial statement on the issue, to say "... a list MIGHT
not be the appropriate data structure..." (emphasis added).
>> Declaring a parameter to be const can make sense for exactly the same
>> reasons that declaring any other local variable const might make sense.
>> I would not consider it objectionable, but I would want to make sure
>> that you understand that making 'sp' const has nothing to do with
>> protecting the argument of the function from modification.
>
> Now I understand, that 2nd const will be useful only in case I am passing
> the address of the original pointer which is not the case here.
Right: you could pass the address of the pointer to the function, using
a parameter declared as "const struct my_struct * const * sp"; in that
case, the second const would serve to protect the original pointer from
change. The first const would protect the thing that the pointer points
at from change. In this case, there's room for a third 'const', after
the second '*'; that third const would protect sp from being changed.
arnuld
>> arnuld wrote:
>> void list_print( const struct my_list *const ps )
>> {
>> struct my_struct* p = NULL;
>>
>> for( p = ps->head; p; p = p->next )
>> {
>> list_print_element(p);
>> }
>>
>> printf("------------------\n");
> If you remove this last bit, this function could be very general. It
> can be helpful to define a "do this to each element" function that
> takes a function as an argument. If you write the loop carefully it
> can be used to both free the list nodes and print the list. This will
> only be worth it if you are writing quite a general list
> implementation.
Whats the benefit of passing the function as an argument. IIRC, I can only
pass a pointer to function as an argument (not the function). 2nd I want
it to only print the elements, free()ing the list is a different thing
because list can be printed some times at some places, hence I want to
keep the free() different.
BTW, you said I am close to correct solution, now is it correct after
doing the changes you mentioned in your reply ? (except the last
print and free() stuff) ?
nick_keigh...@hotmail.com
> > On Sat, 09 May 2009 15:13:48 +0100, Ben Bacarisse wrote:
> >> arnuld wrote:
> >> void list_print( const struct my_list *const ps )
> >> {
> >> struct my_struct* p = NULL;
>
> >> for( p = ps->head; p; p = p->next )
> >> {
> >> list_print_element(p);
> >> }
>
> >> printf("------------------\n");
>
> > If you remove this last bit, this function could be very general. It
> > can be helpful to define a "do this to each element" function that
> > takes a function as an argument. If you write the loop carefully it
> > can be used to both free the list nodes and print the list. This will
> > only be worth it if you are writing quite a general list
> > implementation.
>
> Whats the benefit of passing the function as an argument. IIRC, I can only
> pass a pointer to function as an argument (not the function).
I think he was indulging in shorthand. He meant "pass a function
pointer",
which is in fact the only way to pass a function in as a parameter
typedef void (*Fun) (struct my_struct*);
void apply_fun_to_list (const struct my_list *const ps, Fun f)
{
struct my_struct* p = NULL;
for (p = ps->head; p; p = p->next)
f(p);
}
apply_list (ps, list_print_element);
My version is untested and doesn't do the free()ing
(I'm not sure it's a good idea).
> 2nd I want
> it to only print the elements, free()ing the list is a different thing
> because list can be printed some times at some places, hence I want to
> keep the free() different.
I'm with you here
<snip>
arnuld
> It's good. Not quite correct, but very close.
I have implemented the list_remove_element() too, see if its okay:
/* This C implementation of singly linked list implements 3 operations: add, remove and print elements in the list. Its is the modified
* version of my singly linked list suggested by Ben from comp.lang.c . I was using one struct to do all the operations but Ben added
* a 2nd struct to make things easier and efficient.
*
* I was always using the strategy of searching through the list to find the end and then addd the value there. That way list_add() was
* O(n). Now I am keeping track of tail and always use tail to add to the linked list, so the addition is always O(1), only at the cost
* of one assignment.
*
*
* VERISON 0.4
*
*/
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
struct my_struct
{
int num;
struct my_struct* next;
};
struct my_list
{
struct my_struct* head;
struct my_struct* tail;
};
struct my_list* list_add_element( struct my_list*, const int);
struct my_list* list_remove_element( struct my_list*);
struct my_list* list_new(void);
void list_print( const struct my_list* );
void list_print_element(const struct my_struct* );
int main(void)
{
struct my_list* mt = NULL;
mt = list_new();
list_add_element(mt, 1);
list_add_element(mt, 2);
list_add_element(mt, 3);
list_add_element(mt, 4);
list_print(mt);
list_remove_element(mt);
list_print(mt);
list_remove_element(mt);
list_print(mt);
list_remove_element(mt);
list_print(mt);
list_remove_element(mt);
list_print(mt);
list_remove_element(mt);
list_print(mt);
list_remove_element(mt);
list_print(mt);
return 0;
}
/* This is a queue and it is FIFO, so we will always remove the first element */
struct my_list* list_remove_element( struct my_list* s )
{
struct my_struct* h = NULL;
struct my_struct* p = NULL;
if( NULL == s )
{
printf("List is empty\n");
return s;
}
else if( NULL == s->head && NULL == s->tail )
{
printf("Well, List is empty\n");
return s;
}
else if( NULL == s->head || NULL == s->tail )
{
printf("There is something seriously wrong with your list\n");
printf("One of the head/tail is empty while other is not \n");
return s;
}
h = s->head;
p = h->next;
free(h);
s->head = p;
if( NULL == s->head ) s->tail = s->head; /* The element tail was pointing to is free(), so we need an update */
return s;
}
/* Will always return the pointer to my_list */
struct my_list* list_add_element(struct my_list* s, const int i)
{
struct my_struct* p = malloc( 1 * sizeof(*p) );
if( NULL == p )
{
fprintf(stderr, "IN %s, %s: malloc() failed\n", __FILE__, "list_add");
return s;
}
p->num = i;
p->next = NULL;
if( NULL == s->head && NULL == s->tail )
{
/* printf("Empty list, adding p->num: %d\n\n", p->num); */
s->head = s->tail = p;
return s;
}
else if( NULL == s->head || NULL == s->tail )
{
fprintf(stderr, "There is something seriously wrong with your assignment of head/tail to the list\n");
free(p);
return NULL;
}
else
{
/* printf("List not empty, adding element to tail\n"); */
s->tail->next = p;
s->tail = p;
}
return s;
}
/* ---------------------- small helper fucntions ---------------------------------- */
struct my_list* list_new(void)
{
struct my_list* p = malloc( 1 * sizeof(*p));
if( NULL == p )
{
fprintf(stderr, "LINE: %d, malloc() failed\n", __LINE__);
}
p->head = p->tail = NULL;
return p;
}
void list_print( const struct my_list* ps )
{
struct my_struct* p = NULL;
for( p = ps->head; p; p = p->next )
{
list_print_element(p);
}
printf("------------------\n");
}
void list_print_element(const struct my_struct* p )
{
if( p )
{
printf("Num = %d\n", p->num);
}
else
{
printf("Can not print NULL struct \n");
}
}
========================= OUTPUT =====================================
[arnuld@dune programs]$ gcc -ansi -pedantic -Wall -Wextra queue.c
[arnuld@dune programs]$ ./a.out
Num = 1
Num = 2
Num = 3
Num = 4
------------------
Num = 2
Num = 3
Num = 4
------------------
Num = 3
Num = 4
------------------
Num = 4
------------------
------------------
Well, List is empty
------------------
Well, List is empty
------------------
[arnuld@dune programs]$
arnuld
>> On Sat, 09 May 2009 15:13:48 +0100, Ben Bacarisse wrote:
>> It's good. Not quite correct, but very close.
> I have implemented the list_remove_element() too, see if its okay:
I have implemented list_free() too, see if its fine:
/* This C implementation of singly linked list implements 3 operations: add, remove and print elements in the list. Its is the modified
* version of my singly linked list suggested by Ben from comp.lang.c . I was using one struct to do all the operations but Ben added
* a 2nd struct to make things easier and efficient.
*
* I was always using the strategy of searching through the list to find the end and then addd the value there. That way list_add() was
* O(n). Now I am keeping track of tail and always use tail to add to the linked list, so the addition is always O(1), only at the cost
* of one assignment.
*
*
* VERISON 0.5
*
*/
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
struct my_struct
{
int num;
struct my_struct* next;
};
struct my_list
{
struct my_struct* head;
struct my_struct* tail;
};
struct my_list* list_add_element( struct my_list*, const int);
struct my_list* list_remove_element( struct my_list*);
struct my_list* list_new(void);
void list_free( struct my_list* );
void list_print( const struct my_list* );
void list_print_element(const struct my_struct* );
int main(void)
{
struct my_list* mt = NULL;
mt = list_new();
list_add_element(mt, 1);
list_add_element(mt, 2);
list_add_element(mt, 3);
list_add_element(mt, 4);
list_print(mt);
list_remove_element(mt);
list_print(mt);
list_free(mt); /* always remember to free() the malloc()ed memory */
mt = NULL; /* after free() always set that pointer to NULL, C will run havon on you if you try to use a dangling pointer */
list_print(mt);
return 0;
}
return s;
}
return s;
}
void list_free( struct my_list* s )
{
while( s->head )
{
list_remove_element(s);
}
free(s);
}
struct my_list* list_new(void)
{
struct my_list* p = malloc( 1 * sizeof(*p));
if( NULL == p )
{
fprintf(stderr, "LINE: %d, malloc() failed\n", __LINE__);
}
p->head = p->tail = NULL;
return p;
}
void list_print( const struct my_list* ps )
{
struct my_struct* p = NULL;
if( ps )
{
for( p = ps->head; p; p = p->next )
{
list_print_element(p);
}
}
printf("------------------\n");
}
void list_print_element(const struct my_struct* p )
{
if( p )
{
printf("Num = %d\n", p->num);
}
else
{
printf("Can not print NULL struct \n");
}
}
======================= OUTPUT ==================================
[arnuld@dune programs]$ gcc -ansi -pedantic -Wall -Wextra queue.c
[arnuld@dune programs]$ ./a.out
Num = 1
Num = 2
Num = 3
Num = 4
------------------
Num = 2
Num = 3
Num = 4
------------------
Ben Bacarisse
>> On Tue, 12 May 2009 10:33:42 +0500, arnuld wrote:
>>> On Sat, 09 May 2009 15:13:48 +0100, Ben Bacarisse wrote:
>
>>> It's good. Not quite correct, but very close.
>
>> I have implemented the list_remove_element() too, see if its okay:
Looks fine to me.
> I have implemented list_free() too, see if its fine:
One small point:
> void list_free( struct my_list* s )
> {
> while( s->head )
> {
> list_remove_element(s);
> }
> free(s);
> }
I might separate the idea of freeing the list from de-allocating the
list structure. In other words:
struct my_list *list_free(struct my_list *s)
{
while(s->head)
list_remove_element(s);
return s;
}
is also valid and may make more sense depending on how you use it.
--
Ben.
arnuld
> I might separate the idea of freeing the list from de-allocating the
> list structure. In other words:
>
> struct my_list *list_free(struct my_list *s)
> {
> while(s->head)
> list_remove_element(s);
> return s;
> }
> is also valid and may make more sense depending on how you use it.
I think this is better design.