Singly Linked List in C

[Ben Bacarisse]

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;

 

[s0suk3]

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]

Just added them for clarity.





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]

Tue, 05 May 2009 22:05:20 +0100, Ben Bacarisse wrote:

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;

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;

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

 

[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

 

[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

 

[Guest]

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]

this usage long preceeded wide acceptance (or even knowledge) of OOP.
It was partly a way of dividing up a namespace.

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

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

Note the phrase *one of these*!

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.

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

Any comments on newer version:

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

Note the phrase *one of these*!

Ah, having read the thread I think you mean you have done both
separately to try them out. Sorry for the noise.

 

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

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.


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.

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.

 

[Default User]

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

 

[Barry Schwarz]

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.

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

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

 

[arnuld]

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.

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.