Linked-list problem - compiles but segfaults

[Andy Elvey]

Hi all -
I've been poking around with C for a while, but I have big problems
with linked lists. This seems to be mainly around the "declaration,
initialisation, iterating" area. Anyway, I have the code below, which
compiles but gives a segfault (and I have no idea why), so hoping that
someone may be able to help.
( I have three puts statements at the end because I'm unsure how to
iterate along a list. )

/* This code is released to the public domain  */
#include <ctype.h>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <sys/stat.h>

/* Linked list implementation */
typedef struct _List List;

struct _List {
void *data;
List *next;
};

static List *list_malloc (void)
{
return (List *) malloc (sizeof (List));
}

List *list_prepend (List *list, void *data)
{
List *ret = list_malloc ();
ret->data = data;
ret->next = list;
return ret;
}

List *list_append (List *list, void *data)
{
List *ret;
if (list == NULL) return list_prepend (list, data);
ret = list;
for (; list->next; list = list->next);
list->next = list_malloc ();
list->next->data = data;
list->next->next = NULL;
return ret;
}

void list_free (List *list)
{
List *next;
while (list)
{
next = list->next;
free (list);
list = next;
}
}

/* End linked list implementation */

int main()
{
/* Declare a list */
List *mylist = NULL;
list_append(mylist, "foo");
puts(mylist->data);
list_append(mylist, (int*) 42);
puts(mylist->data);
list_append(mylist, "baz");
puts(mylist->data);
return 0;
}

Very many thanks if you can get this code working......
- Andy

 

[Morris Keesan]

On Mon, 04 Jul 2011 20:53:29 -0400, Andy Elvey

( I have three puts statements at the end because I'm unsure how to
iterate along a list. )

/* This code is released to the public domain  */
#include <ctype.h>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <sys/stat.h>

/* Linked list implementation */
typedef struct _List List;[/QUOTE]

Don't use leading underscores in your type names.  These identifiers
are reserved.  If you're copying the style of names that you've seen
in standard headers, those names begin with underscores specifically
because they're reserved for the implementation, and the implementation
of the standard header would avoid conflicting with your names, if you
weren't going out of your way like this to remove that protection.
[QUOTE]
struct _List {
	void *data;
	List *next;
};

static List *list_malloc (void)
{
return (List *) malloc (sizeof (List));[/QUOTE]
This cast is unnecessary.  Because malloc returns a (void *), it is
automatically converted to the right kind of pointer by the return
statement, without the need of the cast operator.  Also, either here
....
[QUOTE]
}

List *list_prepend (List *list, void *data)
{
	List *ret = list_malloc ();[/QUOTE]
.... or here, you need to check to make sure the malloc() hasn't returned
NULL.  This is almost certainly not the source of your current problem,
but will cause you trouble in larger programs in the future.  You must
always check to make sure malloc succeeded, before you try using a
pointer which was returned by malloc.
[QUOTE]
ret->data = data;
	ret->next = list;
	return ret;
}

List *list_append (List *list, void *data)
{
	List *ret;
	if (list == NULL) return list_prepend (list, data);
	ret = list;
	for (; list->next; list = list->next);[/QUOTE]
This for loop is okay, but odd looking.  In my opinion, it would be
more readable as
while (list->next != NULL) list = list->next;
[QUOTE]
list->next = list_malloc ();
	list->next->data = data;
	list->next->next = NULL;
	return ret;
}

void list_free (List *list)
{
	List *next;
	while (list)
	{
		next = list->next;
		free (list);
		list = next;
	}
}

/* End linked list implementation */[/QUOTE]

Except for the small issues I've mentioned, your linked list
implementation looks okay.
[QUOTE]
int main()
{
/* Declare a list */
List *mylist = NULL;
list_append(mylist, "foo");[/QUOTE]

Okay.  Right here, mylist is still null, because you haven't modified it.
list_append returns the newly-allocated list, but because you don't use
the return value of list_append, the allocation is lost.  So
[QUOTE]
puts(mylist->data);[/QUOTE]

is the same as "puts(NULL->data);".  I hope you can now see where your
segfault is coming from.  If you didn't have the "mylist->data" expression
here causing a crash, then the next call to list_append() would create a
new list, instead of appending a new node to an existing list, because
you're passing a null pointer to list_append for the second time.

Here is another problem:[QUOTE]
list_append(mylist, (int*) 42);[/QUOTE]
You try to convert the number 42 to an (int *), and in list_append it will
get converted to a (void *).  Whether this is meaningful is implementation-
defined.  Most likely, you'll get a pointer whose bit pattern matches the
number 42, i.e. something that appears to be pointing to the whatever is
at the address "42", whatever that address means.  Depending on your
implementation, attempting to convert the number 42 to an (int *) may
be causing the segfault, since if your platform requires ints to be on
4-byte boundaries, 42 is not a valid (int *), even if it were within
the range of user-addressable memory.
If you want to store the number 42 in the linked list as you've
implemented it, the way to do this would be something like
int fortytwo = 42; list_append(mylist, &fortytwo);
but then you would have to have some way of knowing that the data in that
particular list node is an integer, and not a string.

Note that since nothing in your code modifies mylist, all three of these
puts calls should display the same data.  In this case, that's a good
thing,
because if you were displaying each subsequent added data, this next
puts call would be equivalent to puts((char *)(void *)(int *)42), which is
meaningless, and which would probably cause a crash.[QUOTE]
puts(mylist->data);
list_append(mylist, "baz");
puts(mylist->data);
return 0;
}

Very many thanks if you can get this code working......
- Andy

As far as iterating along the list: if you knew that the data in all
members
of the list, you could do it this way:

for (List *p = mylist; p != NULL; p = p->next) puts(p->data);

 

[Andy Elvey]

(snip)
As far as iterating along the list: if you knew that the data in all  
members
of the list, you could do it this way:

for (List *p = mylist; p != NULL; p = p->next) puts(p->data);

Hi Morris -
Thanks very much for your reply! I'll have a good look at what
you've suggested, and will do what you've said. Many thanks - bye for
now -
- Andy

 

[Andy Elvey]

 I've been poking around with C for a while, but I have big problems
with linked lists. This seems to be mainly around the "declaration,
initialisation, iterating" area.  Anyway, I have the code below, which
compiles but gives a segfault (and I have no idea why), so hoping that
someone may be able to help.

Your functions list_prepend and list_append return the new list
head pointer.  list_prepend *always* changes the list head pointer.
list_append changes the list head pointer if it is originally NULL.
You need to actually *USE* those return values in main().  As coded,
mylist in main() is always NULL, and puts(mylist->data) is begging
for a segfault.

( I have three puts statements at the end because I'm unsure how to
iterate along a list. )

This kind of iteration is typically done by (list is the list head pointer):
        List *foo;

        for (foo = list; foo != NULL; foo = foo->next)
        {
                ... do something with foo->data ...;
        }

/* This code is released to the public domain  */
#include <ctype.h>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <sys/stat.h>[/QUOTE]
[QUOTE]
/* Linked list implementation */
typedef struct _List List;[/QUOTE]
[QUOTE]
struct _List {
       void *data;
       List *next;
};[/QUOTE]
[QUOTE]
static List *list_malloc (void)
{
  return (List *) malloc (sizeof (List));
}[/QUOTE]
[QUOTE]
List *list_prepend (List *list, void *data)
{
       List *ret = list_malloc ();
       ret->data = data;
       ret->next = list;
       return ret;
}[/QUOTE]
[QUOTE]
List *list_append (List *list, void *data)
{
       List *ret;
       if (list == NULL) return list_prepend (list, data);
       ret = list;
       for (; list->next; list = list->next);
       list->next = list_malloc ();
       list->next->data = data;
       list->next->next = NULL;
       return ret;
}[/QUOTE]
[QUOTE]
void list_free (List *list)
{
       List *next;
       while (list)
       {
               next = list->next;
               free (list);
               list = next;
       }
}[/QUOTE]
[QUOTE]
/* End linked list implementation */[/QUOTE]
[QUOTE]
int main()
{
/* Declare a list */
List *mylist = NULL;
list_append(mylist, "foo");
puts(mylist->data);[/QUOTE]

Casting 42 to an (int *), then using it in place of a char * in the
puts() below it, is also begging for a segmentation fault.  You may use
various data types for the data pointer, but you need to figure out
some way of identifying what type it is before trying to print it.
puts((int *) 42) is trouble.
[QUOTE]
list_append(mylist, (int*) 42);
puts(mylist->data);
list_append(mylist, "baz");
puts(mylist->data);
return 0;
}

Very many thanks if you can get this code working......

Please send me the email address of your instructor, so I can
send the corrected code directly to him.

Hi Gordon - thanks for your help, much appreciated!
Um.... I don't have an instructor, I'm doing this on my own. I got the
code from here -
http://adamhooper.com/code?path=mcgill-se/COMP206/ass2/products.c
Anyway.... I'd really appreciate it if you were able to either email
or post the corrected code. I've been stuck on linked-lists for ages,
and there are so many (confusing) implementations that make them more
confusing than they should be....
Thanks again -
- Andy

 

[Andy Elvey]

Hi all -
  I've been poking around with C for a while, but I have big problems
with linked lists. This seems to be mainly around the "declaration,
initialisation, iterating" area.  Anyway, I have the code below, which
compiles but gives a segfault (and I have no idea why), so hoping that
someone may be able to help.
( I have three puts statements at the end because I'm unsure how to
iterate along a list. )

/* This code is released to the public domain  */
#include <ctype.h>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <sys/stat.h>[/QUOTE]
[QUOTE]
/* Linked list implementation */
typedef struct _List List;[/QUOTE]
[QUOTE]
struct _List {
        void *data;
        List *next;
};[/QUOTE]
[QUOTE]
static List *list_malloc (void)
{
   return (List *) malloc (sizeof (List));
}[/QUOTE]
[QUOTE]
List *list_prepend (List *list, void *data)
{
        List *ret = list_malloc ();
        ret->data = data;
        ret->next = list;
        return ret;
}[/QUOTE]
[QUOTE]
List *list_append (List *list, void *data)
{
        List *ret;
        if (list == NULL) return list_prepend (list, data);
        ret = list;
        for (; list->next; list = list->next);
        list->next = list_malloc ();
        list->next->data = data;
        list->next->next = NULL;
        return ret;
}[/QUOTE]
[QUOTE]
void list_free (List *list)
{
        List *next;
        while (list)
        {
                next = list->next;
                free (list);
                list = next;
        }
}[/QUOTE]
[QUOTE]
/* End linked list implementation */[/QUOTE]
[QUOTE]
int main()
{
/* Declare a list */
List *mylist = NULL;
list_append(mylist, "foo");
puts(mylist->data);
list_append(mylist, (int*) 42);
puts(mylist->data);
list_append(mylist, "baz");
puts(mylist->data);
return 0;
}

Very many thanks if you can get this code working......
- Andy

/* BEGIN new.c */

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

/* Linked list implementation */
typedef struct LIST {
    struct LIST *next;
    void *data;

} List;

List *
list_append(List **head,
            List *tail,
            const void *data,
            size_t size)
{
    List *node;

    node = malloc(sizeof *node);
    if (node != NULL) {
        node -> next = NULL;
        node -> data = malloc(size);
        if (node -> data != NULL) {
            memcpy(node -> data, data, size);
            if (*head != NULL) {
                tail -> next = node;  
            } else {
                *head = node;
            }
        } else {
            free(node);
            node = NULL;
        }
    }
    return node;

}

void
list_free(List *node, void (*free_data)(void *))
{
    List *next_node;

    while (node != NULL) {
        next_node = node -> next;
        free_data(node -> data);
        free(node);
        node = next_node;
    }

}

int
list_fputs(List *node, FILE *stream)
{
    int rc = 0;

    while (node != NULL
        && (rc = fputs(node -> data, stream)) != EOF
        && (rc =  putc(        '\n', stream)) != EOF)
    {
        node = node -> next;
    }
    return rc;

}

/* End linked list implementation */

int
main(void)
{
    /* Declare a list */
    List *mylist = NULL;
    List *tail = NULL;
    char *w[] = {"foo", "bar", "bazooka"};
    char **p = w;

    do {
        tail = list_append(&mylist, tail, *p, 1 + strlen(*p));
    } while(tail != NULL && ++p != w + sizeof w / sizeof *w);
    puts("/* BEGIN new.c output */\n");
    list_fputs(mylist, stdout);
    list_free(mylist, free);
    puts("\n/* END new.c output */");
    return 0;

}

/* END new.c */

Many thanks for that, Pete! That code is the best that I've seen for
a linked list!
It's good to see some code that's easy to understand.
Thanks again - bye for now -
- Andy

 

[Keith Thompson]

Look at the documentation of your compiler and how to turn warnings
on. You should get a compiler warning on the last line and your
program will crash there; no need even to read the code for
list_append.

You'd get a warning on the puts() call only if the compiler performs
enough dataflow analysis to infer that mylist->data will be a
null pointer at that point. Typically that's done only when you
enable optimization (because the same analysis that allows certain
optimizations to be performed safely can also reveal such errors).

And there's no guarantee that it would crash. There have been plenty
of systems on which dereferencing a null pointer doesn't cause any
obvious problems; for example, it might simply read whatever is at
address 0, which might be a zero byte. (Of course on many systems
it will crash.)

 

[Paul N]

Hi all -
  I've been poking around with C for a while, but I have big problems
with linked lists.

Other people have helped with your specific problems, but I thought it
might help if I made a few general comments. There are two different
ways to go about linked lists, and you don't seem to be aware that
you've made a decision about which to use.

Let's start with this definition:

struct _List {
        void *data;
        List *next;
};

This is not, actually, a list. It is a node. It stores a pointer to
some data, and a pointer to the next node. Conceptually, a linked list
is a collection of such nodes, each pointing to the next with the last
one pointing to NULL.

You have two options. One is to create a struct that represents a
list. This would be slightly less efficient that what you've done, and
take a bit more writing in the first place, but would probably be
easier to use once you've got it. The other option, the one you are
going for at present, is to treat a pointer to the first node of a
list as being a pointer to the list itself. You need to be careful
using such an approach.

[By way of an analogy - C doesn't really have a type for strings,
unlike many other languages. What is does have is pointers to
characters. When you deal with a "string", you actually have a pointer
to the first character - but a function that is expected that can find
the second character in the next location, the third in the one after
that, etc, until it hits a 0 showing the end of the string. But this
means that you can't, for instance, compare two strings using ==, you
need to call a function. In a similar manner, a pointer to a first
node of a list can be treated as a pointer to the list itself, as long
as that's what the relevant function is expecting.]

So with this approach, when calling a function like this one:

List *list_prepend (List *list, void *data)
{
        List *ret = list_malloc ();
        ret->data = data;
        ret->next = list;
        return ret;

}

you need to do something like:

list = list_prepend(list, data);

ie you need to "catch" the value coming out, and you also need to
"lose" the value of list going in. If you did:

list = list_prepend(list2, data);

then things are likely to go wrong if you ever use list2 again.

If you want to try using the first approach, you will need a struct
for a list which is different from a struct for a node. This may only
need to contain a member "head" pointing to the first node.

If you've seen code using both approaches and not spotted the
difference it's no wonder you're a little confused!

Hope this helps.
Paul.

 

[Todd Carnes]

Hi all -
  I've been poking around with C for a while, but I have big problems
with linked lists.

Other people have helped with your specific problems, but I thought it
might help if I made a few general comments. There are two different
ways to go about linked lists, and you don't seem to be aware that
you've made a decision about which to use.

Let's start with this definition:

struct _List {
        void *data;
        List *next;
};

This is not, actually, a list. It is a node. It stores a pointer to some
data, and a pointer to the next node. Conceptually, a linked list is a
collection of such nodes, each pointing to the next with the last one
pointing to NULL.

You have two options. One is to create a struct that represents a list.
This would be slightly less efficient that what you've done, and take a
bit more writing in the first place, but would probably be easier to use
once you've got it. The other option, the one you are going for at
present, is to treat a pointer to the first node of a list as being a
pointer to the list itself. You need to be careful using such an
approach.

[By way of an analogy - C doesn't really have a type for strings, unlike
many other languages. What is does have is pointers to characters. When
you deal with a "string", you actually have a pointer to the first
character - but a function that is expected that can find the second
character in the next location, the third in the one after that, etc,
until it hits a 0 showing the end of the string. But this means that you
can't, for instance, compare two strings using ==, you need to call a
function. In a similar manner, a pointer to a first node of a list can
be treated as a pointer to the list itself, as long as that's what the
relevant function is expecting.]

So with this approach, when calling a function like this one:

List *list_prepend (List *list, void *data) {
        List *ret = list_malloc ();
        ret->data = data;
        ret->next = list;
        return ret;

}

you need to do something like:

list = list_prepend(list, data);

ie you need to "catch" the value coming out, and you also need to "lose"
the value of list going in. If you did:

list = list_prepend(list2, data);

then things are likely to go wrong if you ever use list2 again.

If you want to try using the first approach, you will need a struct for
a list which is different from a struct for a node. This may only need
to contain a member "head" pointing to the first node.

If you've seen code using both approaches and not spotted the difference
it's no wonder you're a little confused!

Hope this helps.
Paul.

Thanks for the clear explanation. I don't know about the OP, but you
certainly helped to clear a few things about linked lists up for me. One
question, is it not possible to have the last node in the list point to
the first node (instead of NULL), so that traversing past the last node
will simply cause you to wrap back around to the start of the list?

Todd

 

[Shao Miller]

Thanks for the clear explanation. I don't know about the OP, but you
certainly helped to clear a few things about linked lists up for me. One
question, is it not possible to have the last node in the list point to
the first node (instead of NULL), so that traversing past the last node
will simply cause you to wrap back around to the start of the list?

That is common for some linked lists that I've seen, but it means
that walking the list can look like:

xxx * walker = ..., * head = ...;

while ((walker = head->next) != head) {
/* Work with 'walker' */
/* ...*/
}

Where head is distinct from other nodes and isn't "worked with" in
the same way as non-head nodes.

 

[Shao Miller]

last list?


That is common for some linked lists that I've seen, but it means
that walking the list can look like:

xxx * walker = ..., * head = ...;

while ((walker = head->next) != head) {

Uhh... Make that:

walker = head;
while ((walker = walker->next) != head) {

/* Work with 'walker' */
/* ...*/
}

Where head is distinct from other nodes and isn't "worked with" in
the same way as non-head nodes.

Sorry! That was an error.

 

[Shao Miller]

Sorry! That was an error.

(Not the quoted part, above, though. Fooey on Usenet-posting from a
tiny device!)

 

[Shao Miller]

Or a slightly longer line and a 'for' loop. Sheesh it's time for
sleep. (Excuses, excuses.)

for (walker = head->next; walker != head; walker = walker->next) {
/* Work with 'walker' */
/* ...*/
}

 

[Morris Keesan]

That is common for some linked lists that I've seen, but it means that
walking the list can look like:

xxx * walker = ..., * head = ...;

while ((walker = head->next) != head) {
/* Work with 'walker' */
/* ...*/
}

Where head is distinct from other nodes and isn't "worked with" in the
same way as non-head nodes.

Or, more commonly if you actually have a use for this kind of list
(called a "circular list"), you don't actually distinguish the head
of the list from any other node, and the list doesn't have a "first"
or "last" node. You would use this, for example, if you wanted to
have a fixed number of buffers for something, and re-use them when
necessary. Instead of a "head" pointer for this list, you would have
a "newest", or "oldest", or "current" pointer. If you have a "newest"
or "most_recent" pointer, then oldest == newest->next.

This is beyond the specifics of the C language. Find a book on data
structures. The one I used when learning this stuff many years ago was
"Data Structures + Algorithms = Programs", by Niklaus Wirth, which
expressed the concepts in Pascal.

 

[Shao Miller]

(Code changed, as elsethread.)

Where head is distinct from other nodes and isn't "worked with" in the
same way as non-head nodes.

Or, more commonly if you actually have a use for this kind of list
(called a "circular list"), you don't actually distinguish the head
of the list from any other node, and the list doesn't have a "first"
or "last" node. You would use this, for example, if you wanted to
have a fixed number of buffers for something, and re-use them when
necessary. Instead of a "head" pointer for this list, you would have
a "newest", or "oldest", or "current" pointer. If you have a "newest"
or "most_recent" pointer, then oldest == newest->next.

[...]

Are you sure that's more common? Are you suggesting that a fixed-count
list of nodes is a more common use case for a circular list than a
variable-count list of nodes, or was that example not intended to
suggest that?

The storage for the "newest" pointer strikes me as akin to a head node;
it's distinct from the nodes in the list, its lifetime (not to be
confused with the Standard term) is most likely at least the lifetime of
the list, and it points to within the list. No?

If the simplest node in a singly-linked list is:

struct node { struct node * next; };

then the object representation for a head node might exactly correspond
to the object representation for a "newest" pointer. Right? A "head"
node needn't suggest that a circular list has a "beginning" and an
"end," need it? It can just be a "point of interest," I think. Perhaps
"head" isn't the best term, though it's a means to "head into" the list.

(This "simplest" 'struct node' is an example of where a function working
with such a node knows the location of the relevant data, given the
location of the node, perhaps using 'offsetof' or derivatives such as
'container_of' or 'CONTAINING_RECORD'. As in: 'struct some_data { int
ia[10]; struct node node; };')