Marc Nieper-Wißkirchen wrote:
> For example, given a list of fruits, insert "pear" after each "apple" and
> "peach" before each "apple". This can be easily done through
> gl_list_add_before/gl_list_add_after/gl_list_next_node without using
> invalidated nodes.

Now I see what you mean. Quasi companion functions to gl_list_next_node
and gl_list_previous_node: gl_list_first_node and gl_list_last_node,
respectively.

> What I want to propose is to allow the NULL value in
> gl_next_node/gl_previous_node. In this case, gl_next_node shall return the
> first node and gl_previous_node shall return the last node.

I don't think this encourages robust programs. If a program passes a NULL
pointer to gl_list_next_node or gl_list_previous_node, the program should
better crash.

> PS What can't be done (because gl_list_remove doesn't return a valid
> (next?) node) is list walking algorithms that both remove and insert nodes.
> For removal, one has to use an iterator.

Yes, some algorithms need a second, temporary list. Not all algorithms
can be written to use the original list, be efficient in O() terms, and
be implementation-independent.


2021-04-03  Bruno Haible  <bruno@clisp.org>

	*-list tests: Add more tests.
	* tests/test-array_list.c (check_equals_by_forward_iteration,
	check_equals_by_backward_iteration): New functions.
	(main): Invoke them.
	* tests/test-carray_list.c: Likewise.
	* tests/test-linked_list.c: Likewise.
	* tests/test-linkedhash_list.c: Likewise.
	* tests/test-avltree_list.c: Likewise.
	* tests/test-avltreehash_list.c: Likewise.
	* tests/test-rbtree_list.c: Likewise.
	* tests/test-rbtreehash_list.c: Likewise.

	list: Add operations first_node, last_node.
	Reported by Marc Nieper-Wißkirchen in
	<https://lists.gnu.org/archive/html/bug-gnulib/2021-04/msg00005.html>.
	* lib/gl_list.h (gl_list_first_node, gl_list_last_node): New functions.
	(struct gl_list_implementation): Add members first_node, last_node.
	* lib/gl_array_list.c (gl_array_first_node, gl_array_last_node): New
	functions.
	(gl_array_list_implementation): Add the new operations.
	* lib/gl_carray_list.c (gl_carray_first_node, gl_carray_last_node): New
	functions.
	(gl_carray_list_implementation): Add the new operations.
	* lib/gl_anylinked_list2.h (gl_linked_first_node, gl_linked_last_node):
	New functions.
	* lib/gl_linked_list.c (gl_linked_list_implementation): Add the new
	operations.
	* lib/gl_linkedhash_list.c (gl_linkedhash_list_implementation):
	Likewise.
	* lib/gl_anytree_list2.h (gl_tree_first_node, gl_tree_last_node): New
	functions.
	* lib/gl_avltree_list.c (gl_avltree_list_implementation): Add the new
	operations.
	* lib/gl_avltreehash_list.c (gl_avltreehash_list_implementation):
	Likewise.
	* lib/gl_rbtree_list.c (gl_rbtree_list_implementation): Likewise.
	* lib/gl_rbtreehash_list.c (gl_rbtreehash_list_implementation):
	Likewise.
	* lib/gl_sublist.c (gl_sublist_first_node, gl_sublist_last_node): New
	functions.
	(gl_sublist_list_implementation): Add the new operations.
	* lib/gl_list.hh (class gl_List): Add member functions first_node,
	last_node.
	* doc/containers.texi: Update table.