Re: g_list_prepend() vs g_list_append()

[James Henstridge <james daa com au>]

Mark Mielke wrote:

> On Sat, Sep 07, 2002 at 07:20:01PM -0500, Chema Celorio wrote:
>  
>
> > GList is a very good linked list implementation. You are just having a
> > problem with the names, don't let the names fool you. If you want to do
> > efficient append then do:
> > ...
> > for (i = 0; i < 100; i++)
> >   l = g_list_prepend (l, i);
> > l = g_list_reverse (l);
> > ...
> > That is what everybody does. With the very heavy use of glist out there
> > don't expect the implementation to change. 
> >    
>
> The implementation wouldn't change. Your example above passed the first
> list element to g_list_prepend(), which is all quite normal.
>
> If "everybody does" g_list_prepend()/g_list_reverse(), would there be any
> resistance to the additional of a GCList or similar, that was a GList,
> except that it used g_clist_*() as methods, and was circular?
>
> Seems like solving the problem, rather than requiring everybody to use
> a workaround, might be prudent.
>
> g_list_reverse() may be fairly fast, but replacing:
>
>
>     g_list_append(), ...;
>
> With:
>
>     g_list_reverse();
>     g_list_prepend(), ...;
>     g_list_reverse();
>
> Does not fall under the category of 'efficient'.
>  
A cyclic linked list/ring data type was discussed during the glib/gtk 
2.0 development cycle, but after the API freeze:
   http://mail.gnome.org/archives/gtk-devel-list/2001-August/msg00417.html

Maybe it would be worth looking at this again for 2.2 or 2.4?

By the way, if you want to efficiently append to a GList, you should 
maintain a tail pointer.  When you want to append, g_list_append() to 
the tail, and update the tail pointer.  There are a number of examples 
of this in the gtk API.

James.

--
Email: james daa com au              | Linux.conf.au   http://linux.conf.au/
WWW:   http://www.daa.com.au/~james/ | Jan 22-25   Perth, Western Australia.