Re: CList glitch (some kind o off-topic response)



leon@udmnet.ru writes:

> BTW, if I *prepend*, not *append* to the list, will it reduce the time
> to O(n)? Is it possible?

Yes, prepending is much faster. GLib does not keep track of the tail
of lists, so appending an item will be an O(n) operation, making
appending n items an O(n^2) operation.

Prepending is O(1), so prepending n items will be O(n).

In my opinion it is a mistake that GLib doesn't keep track of tails.
I don't think it is possible to fix it, though, since lists are not
opaque and a lot of code depends on the structure of list items.



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