Groups | Search | Server Info | Keyboard shortcuts | Login | Register [http] [https] [nntp] [nntps]

Groups > comp.lang.c > #7695

Re: Linked-list problem - compiles but segfaults

Show all headers | View raw

On Tue, 05 Jul 2011 14:51:34 -0700, Paul N wrote:

> On Jul 5, 1:53 am, Andy Elvey <neptune.poseidon...@gmail.com> 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

Back to comp.lang.c | Previous | Next — Previous in thread | Next in thread | Find similar | Unroll thread

Thread

Linked-list problem - compiles but segfaults Andy Elvey <neptune.poseidon789@gmail.com> - 2011-07-04 17:53 -0700
  Re: Linked-list problem - compiles but segfaults "Morris Keesan" <mkeesan@post.harvard.edu> - 2011-07-04 22:18 -0400
    Re: Linked-list problem - compiles but segfaults Andy Elvey <neptune.poseidon789@gmail.com> - 2011-07-04 19:31 -0700
  Re: Linked-list problem - compiles but segfaults gordonb.bxelr@burditt.org (Gordon Burditt) - 2011-07-04 21:39 -0500
    Re: Linked-list problem - compiles but segfaults Andy Elvey <neptune.poseidon789@gmail.com> - 2011-07-04 20:00 -0700
      Re: Linked-list problem - compiles but segfaults gordonb.tu82f@burditt.org (Gordon Burditt) - 2011-07-05 00:11 -0500
  Re: Linked-list problem - compiles but segfaults pete <pfiland@mindspring.com> - 2011-07-05 00:13 -0400
    Re: Linked-list problem - compiles but segfaults Andy Elvey <neptune.poseidon789@gmail.com> - 2011-07-04 21:20 -0700
      Re: Linked-list problem - compiles but segfaults pete <pfiland@mindspring.com> - 2011-07-05 01:04 -0400
  Re: Linked-list problem - compiles but segfaults "christian.bau" <christian.bau@cbau.wanadoo.co.uk> - 2011-07-05 08:42 -0700
    Re: Linked-list problem - compiles but segfaults Keith Thompson <kst-u@mib.org> - 2011-07-05 09:04 -0700
  Re: Linked-list problem - compiles but segfaults Paul N <gw7rib@aol.com> - 2011-07-05 14:51 -0700
    Re: Linked-list problem - compiles but segfaults Todd Carnes <toddcarnes@gmail.com> - 2011-07-06 03:20 +0000
      Re: Linked-list problem - compiles but segfaults Shao Miller <sha0.miller@gmail.com> - 2011-07-05 23:37 -0400
        Re: Linked-list problem - compiles but segfaults Shao Miller <sha0.miller@gmail.com> - 2011-07-05 23:41 -0400
          Re: Linked-list problem - compiles but segfaults Shao Miller <sha0.miller@gmail.com> - 2011-07-05 23:44 -0400
          Re: Linked-list problem - compiles but segfaults Shao Miller <sha0.miller@gmail.com> - 2011-07-05 23:54 -0400
        Re: Linked-list problem - compiles but segfaults "Morris Keesan" <mkeesan@post.harvard.edu> - 2011-07-06 07:51 -0400
          Re: Linked-list problem - compiles but segfaults Shao Miller <sha0.miller@gmail.com> - 2011-07-06 09:50 -0400

csiph-web