Listas - ¿Cómo enfocaríais el valor de retorno de las búsquedas?

[do-while]

¡Buenas!

He retomado un proyecto que empecé hace un tiempo sobre crear esctructuras de datos genéricas en C, y tengo alguna duda sobre qué tipo de dato debería devolver una búsqueda sobre una lista. La estructura contiene un puntero void* en el que se almacena el dato, y en un principio lo que estoy devolviendo en NULL si no encuentro el dato y void const* si lo encuentro para evitar modificar el dato (de momento estoy trabajando con listas ordenadas).

La cuestión es que este valor de retorno no da ningún tipo de información sobre la posicion que el elemento ocupa dentro de la lista, por lo que, por ejemplo, no se podría combinar una busqueda con la extracción de una sublista en caso de que haga falta seleccionar elementos dentro de un rango determinado. Si por el contrario utilizo un entero (lo más lógico sería un unsigned long) como valor de retorno, estaría limitando la cantidad de datos que se podrían almacenar al rango de valores de ese tipo de entero (un valor menos, teniendo en cuenta que tendría que escoger un valor de retorno, por ejemplo (unsigned long)(-1) para informar de que no ha habido ninguna coincidencia).

Otra alternativa sería buscar un elemento y devolver un puntero como comentaba antes, y en caso de que la búsqueda tuviese éxito utilizar una función que me devuelva la posición, pero seguiría existiendo la limitación sobre la cantidad máxima de datos que la lista podría contener.

Si alguna vez habéis trabajado con listas, ¿Cómo habéis enfocado el problema de la busqueda/posición de un elemento dentro de ésta?

[MAFUS]

¿Los elementos de la lista son todos iguales o puedes meter cualquier dato en ella?
La solución a la primera opción sería hacer una función que retornara dirección_elemento - dirección_raiz / tamaño_elemento.

Para la segunda gastarías un poco más de memoria y tiempo pues podrías generar un array dinámico con malloc y realloc de punteros a void* que sería tus elementos en la lista. Tus elementos sería otro tipo de dato que contendría un entero informando de su tamaño y un puntero a void* que apuntaría al dato en sí. Sí se complica un poco.
Para acelerar un poco las cosas podrías hacer bloques de 10 elementos (este número depende de lo rápido que crezca y decrezca tu lista). Cuándo fueras a introducir un datos más que el máximo de la lista haces un realloc y adquieres 10 posiciones más. A medida que vayas borrando vas dejando esas posiciones de la lsita a NULL, que te servirían para introducir más datos sin hacerla crecer; pero si has borrado más de 10 datos mueves los elementos a fin de compactarla y con realloc reduces la lista en 10 elementos.
Puedes encerrar dicha lista en un objeto donde podrías poner el tamaño real que tiene, el número de datos que tiene dentro. Así para moverte por ella podrías usar la típica notación de array y sabrías cuando parar. Cómo no puede haber un mayor número de posiciones de memoria que el que te marca un entero sin signo de la mayor palabra del procesador, y que nunca va a ser tan grande pues la compartes con el resto del sistema, pues lo tienes todo hecho.

[ivancea96]

Nunca he usado una lista queriendo saber la posición de los elementos. Para ello suelo escoger un array dinámico.

En cualquier caso, si quieres que la función de búsqueda retorne la posición, puedes hacer una estructura que almacene puntero al nodo y posición.

Si el conocer la posición es algo que usarás contadas veces, puedes hacer lo que comentas, de una función que diga la posición de un nodo en la lista.

Es tu lista, tú la usarás, y tú dirás cómo quieres que esté implementado. Lo más estándar que te puedo decir, es la implementación de la librería estándar, y ahí no te dice la posición. (Hay funciones que dan la posición dado un iterador, eso sí)

[do-while]

¡Gracias por vuestras respuestas!

MAFUS, gracias por la idea, pero prefiero evitar el uso de vectores, la idea de la lista es que la posición de cada elemento puede estar en cualquier posición de la memoria y así evito la restricción que tendría un vector de utilizar posiciones consecutivas. Una reasignación del vector podría fallar en caso de no poder asignar suficientes posiciones consecutivas, con la lista tradicional bastaría con que hubiese espacio suficiente para un nodo más.

invancea96 es lo que había pensado, olvidarme de las posiciones.

También estoy pensando en utilizar un árbol valanceado de punteros a los nodos para apoyar las búsquedas, inserciones y eliminaciones. ¿Merece la pena el intercambio memoria/tiempo de ejecución? Recuerdo que de momento estoy con listas ordenadas, los elementos repetidos son consecutivos y el árbol tiene sentido para las tres operaciones, cuando implemente las listas "normales" en principio no habrá ningun orden y el árbol dejará de tener sentido a no ser que sea un árbol de listas y en cada nodo almacene una lista de los nodos de la lista en los que se repite cada elemento, y aún así solo serviría para búsquedas y eliminaciones.

[ivancea96]

Puedes hacer todas las posibilidades :X
http://bigocheatsheet.com/#data-structures