Se me ocurrió una estructura de datos que combina algunas de las ventajas de las listas vinculadas con algunas de las ventajas de las matrices de tamaño fijo. Me parece muy obvio, por lo que espero que alguien lo haya pensado y ya lo haya nombrado. Alguien sabe como se llama esto:

Tome una pequeña matriz de tamaño fijo. Si el número de elementos que desea poner en su matriz es mayor que el tamaño de la matriz, agregue una nueva matriz y los punteros que desee entre lo antiguo y lo nuevo.

Así tienes:

Static array
—————————————————————————
|1|2|3|4|5|6|7|8|9|a|b|c|
—————————————————————————

Linked list
————  ————  ————  ————  ————
|1|*->|2|*->|3|*->|4|*->|5|*->NULL
————  ————  ————  ————  ————

My thing:
————————————  ————————————
|1|2|3|4|5|*->|6|7|8|9|a|*->NULL
————————————  ————————————

Editar: Como referencia, este algoritmo proporciona un rendimiento bastante pobre de adición / eliminación en el peor de los casos, y no mucho mejor en el caso promedio. La gran ventaja para mi escenario es el rendimiento mejorado de la memoria caché para las operaciones de lectura.

Editar recompensa: La respuesta de Antal S-Z fue tan completa y bien investigada que quise darles una recompensa por ello. Aparentemente, Stack Overflow no me permite aceptar una respuesta tan pronto como ofrezco una recompensa, por lo que tendré que esperar (admito que estoy abusando del sistema de recompensas de intención, aunque es en nombre de recompensar a alguien por un excelente responder). Por supuesto, si alguienhace logran proporcionar una mejor respuesta, más poder para ellos, ¡y sin duda pueden tener la recompensa!

Editar re nombres: No me interesa lo quetu llámalo, a menos que lo llames así porque así lo llamarían las autoridades sobre el tema. Si es un nombre que se te ocurrió, no me interesa. Lo que quiero es un nombre que pueda buscar en los libros de texto y con Google. (Además, aquí hay un consejo: la respuesta de Antal es lo que estaba buscando. Si su respuesta no es "lista vinculada desenrollada" sin unmuy buena razón, simplemente está mal).