Re: g_list_prepend() vs g_list_append()

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(), ...;


    g_list_prepend(), ...;

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:

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.


Email: james daa com au              |
WWW: | Jan 22-25 Perth, Western Australia.

[Date Prev][Date Next]   [Thread Prev][Thread Next]   [Thread Index] [Date Index] [Author Index]