Re: Add gl_list_remove_last to list/xlist

[Bruno Haible]

Hi Marc,

> Okay; I agree that a separate stack or FIFO module can make more
> sense; in particular when it only has to deal with a single
> implementation of an underlying data structure. At the moment I do
> have other work to finish first, but maybe I will find some time in
> the near future for a stack module.

Good! When you come to it, please consider our "Contributing to Gnulib" tips:
<https://www.gnu.org/software/gnulib/manual/html_node/Contributing-to-Gnulib.html>.

> I don't see, however, to implement the function dealing with
> end of the list in O(1) behavior when the underlying data structure is
> a linked list.

The LINKED list implementation is a doubly-linked list, and the functions
get_at, set_at, or remove_at are implemented like this:
  If position < length/2 then
    walk from the start of the list (O(position))
  else
    walk from the end of the list (O(length-position)).

So, the original invocation
  gl_list_remove_at (list, gl_list_size (list) - 1)
already does the job in O(1).

Bruno