Singly Linked List in C

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

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.

....

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]

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:

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

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>

 

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

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 ?

 

[Guest]

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.


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 ?

<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;

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]

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?

 

[James Kuyper]

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.

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.

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]

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]

<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 Bacarisse]

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 ?

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 Bacarisse]

Here is the new code according to your design ans it works , any more
improvements that are needed ?

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.

 

[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");
}


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");
}
}

 

[arnuld]

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.

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.

 

[James Kuyper]

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

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]

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

 

[Guest]

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