Path: csiph.com!x330-a1.tempe.blueboxinc.net!usenet.pasdenom.info!aioe.org!.POSTED!not-for-mail From: Todd Carnes Newsgroups: comp.lang.c Subject: Re: Linked-list problem - compiles but segfaults Date: Wed, 6 Jul 2011 03:20:22 +0000 (UTC) Organization: Aioe.org NNTP Server Lines: 81 Message-ID: References: <0ae24ce7-2bd8-4493-989b-0df3bd0ff263@g12g2000yqd.googlegroups.com> <19cec9d6-64fd-4d77-8ed3-c0f751523c8b@g16g2000yqg.googlegroups.com> NNTP-Posting-Host: uqlV+6kNo2Z0TnMsKGN6tA.user.speranza.aioe.org Mime-Version: 1.0 Content-Type: text/plain; charset=UTF-8 Content-Transfer-Encoding: 8bit X-Complaints-To: abuse@aioe.org User-Agent: Pan/0.133 (House of Butterflies) X-Notice: Filtered by postfilter v. 0.8.2 Xref: x330-a1.tempe.blueboxinc.net comp.lang.c:7695 On Tue, 05 Jul 2011 14:51:34 -0700, Paul N wrote: > On Jul 5, 1:53 am, Andy Elvey wrote: >> 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