diff -r bf5866e47b15 -r ee421d6b95ef src/kv_list.c
--- a/src/kv_list.c	Fri Sep 19 16:05:41 2025 +0200
+++ b/src/kv_list.c	Sat Sep 20 12:19:49 2025 +0200
@@ -270,21 +270,33 @@
 
 static void *cx_kvl_map_put(CxMap *map, CxHashKey key, void *value) {
     cx_kv_list *kv_list = ((struct cx_kv_list_map_s*)map)->list;
-    // insert the data into the list first (assume that insertion destroys the sorted property)
+    // if the hash has not yet been computed, do it now
+    if (key.hash == 0) {
+        cx_hash_murmur(&key);
+    }
+
+    // reserve memory in the map first
+    void **map_data = kv_list->map_methods->put(map, key, NULL);
+    if (map_data == NULL) return NULL; // LCOV_EXCL_LINE
+
+    // insert the data into the list (which most likely destroys the sorted property)
     kv_list->list.base.collection.sorted = false;
     void *node_data = kv_list->list_methods->insert_element(
         &kv_list->list.base, kv_list->list.base.collection.size,
         kv_list->list.base.collection.store_pointer ? &value : value);
-    if (node_data == NULL) return NULL; // LCOV_EXCL_LINE
-    // if the hash has not yet been computed, do it now
-    if (key.hash == 0) {
-        cx_hash_murmur(&key);
-    }
+    if (node_data == NULL) { // LCOV_EXCL_START
+        // non-destructively remove the key again
+        kv_list->map_methods->remove(&kv_list->map->map_base.base, key, &map_data);
+        return NULL;
+    } // LCOV_EXCL_STOP
+
+    // write the node pointer to the map entry
+    *map_data = node_data;
+
     // copy the key to the node data
     CxHashKey *key_ptr = cx_kv_list_loc_key(kv_list, node_data);
     *key_ptr = key;
-    // then insert the key into the map, referring to the node data
-    return kv_list->map_methods->put(map, key, node_data);
+    return map_data;
 }
 
 void *cx_kvl_map_get(const CxMap *map, CxHashKey key) {
@@ -491,14 +503,19 @@
 int cx_kv_list_insert(CxList *list, size_t index, CxHashKey key, void *value) {
     cx_kv_list *kv_list = (cx_kv_list*)list;
 
+    // reserve memory in the map
+    void **map_data = kv_list->map_methods->put(&kv_list->map->map_base.base, key, NULL);
+    if (map_data == NULL) return 1; // LCOV_EXCL_LINE
+
     // insert the node
     void *node_data = kv_list->list_methods->insert_element(&kv_list->list.base, index,
         kv_list->list.base.collection.store_pointer ? &value : value);
-    if (node_data == NULL) return -1; // LCOV_EXCL_LINE
-
-    // add the key to the map
-    kv_list->map_methods->put(&kv_list->map->map_base.base, key, node_data);
-    // TODO: get rid of the node again, when adding the entry to the map failed
+    if (node_data == NULL) { // LCOV_EXCL_START
+        // non-destructively remove the key again
+        kv_list->map_methods->remove(&kv_list->map->map_base.base, key, &map_data);
+        return 1;
+    } // LCOV_EXCL_STOP
+    *map_data = node_data;
 
     // write the key to the node
     CxHashKey *loc_key = cx_kv_list_loc_key(kv_list, node_data);