Dos formas de implementar una lista vinculada: ¿cuál es mejor?

Question

En general, conozco dos formas de diseñar una estructura de datos de lista enlazada genérica en C. Y me pregunto cuál es mejor. Antes de hacer la pregunta, voy a introducir ambos métodos en breve:

Un método consiste en construir funciones alrededor de una estructura como la siguiente:

struct list_element { 
    struct list_element *prev; 
    struct list_element *next; 
    void *data; 
}; 

Obviamente, el puntero apunta a los datos de la carga útil. La estructura del elemento de lista está fuera de la carga útil. Esto es, p. cómo glib ha diseñado su facilidad de lista de doble enlace: http://library.gnome.org/devel/glib/2.26/glib-Doubly-Linked-Lists.html

Otro método es la forma en que se hace en el kernel de Linux: http://isis.poly.edu/kulesh/stuff/src/klist/. No hay puntero de vacío en la carga útil en la estructura del elemento de lista. En cambio, la estructura de lista de elementos está incluido en la estructura de carga útil:

struct list_element { 
    struct list_element *prev; 
    struct list_element *next; 
}; 

struct person { 
    char name[20]; 
    unsigned int age; 
    struct list_element list_entry; 
}; 

Una macro especial se utiliza para obtener un puntero a la carga útil struct dado un puntero a la list_entry, su nombre en el canto estructura de carga útil y el tipo de la estructura de carga útil (la macro list_entry()).

Finalmente, aquí está la pregunta: ¿Cuál es la ventaja de este último de los dos métodos para construir una lista vinculada? Algunas veces escuché a la gente decir que el segundo es más "genérico" que el primero, pero ¿por qué? Incluso diría que el primer método es más genérico porque las estructuras de carga útil son independientes de la implementación de la lista, que no es el caso con el segundo método.
Una desventaja más del segundo método es que si desea colocar la carga en más de una lista, debe incluir un elemento struct list_element para cada lista en la estructura de carga.

Editar: Para resumir hasta ahora vi dos respuestas que eran importantes para mí:

• Con el primer método: la eliminación de una carga útil de la lista consiste en bucle a través de la lista completa hasta que el elemento de la lista que apunta a la carga útil se encuentra. No necesita hacer esto con el segundo método. (Respuesta de Patrick)
• Con el primer método, debe hacer dos malloc() s para cada elemento: uno para la carga útil y otro para la estructura del elemento de lista. Con el segundo método, un malloc() es suficiente. (Respuesta de Roddy)

Answer 1

El primer enfoque puede parecer menos intrusivo, pero en muchos casos no lo es (a menos que agregue estructuras de datos adicionales).

Imagine que tiene una lista de miles de personas y desea eliminar una de ellas de la lista. Si la persona no sabe dónde está en la lista, primero tendrá que escanear toda la lista para obtener el lugar exacto de la persona.

Puede resolver esto agregando un puntero de la persona a su estructura de lista correspondiente, pero esto anula la no intrusividad (¿existe esta palabra?) De la solución.

Otra alternativa es tener un mapa hash que asigne las direcciones de memoria de las personas a las direcciones de memoria de los nodos de la lista. Luego, encontrar el nodo en la lista es mucho más rápido (pero aún más lento que la forma intrusiva). Sin embargo, dado que esto llevará aún más memoria, sugiero que no haga esto.

Por lo tanto, la solución más fácil y simple es la segunda.

Answer 2

La primera es mejor porque puede tener nodos de lista sin datos.

Con la segunda opción, siempre usa el espacio (por ejemplo, los 20 caracteres para los nombres) independientemente del uso real.

Answer 3

Es caballos para cursos.

El primer método es menos eficiente ya que normalmente requiere dos malloc() sy free() s para cada elemento de lista, y un indirecto de puntero adicional para acceder a ellos, y por supuesto espacio de almacenamiento para el puntero.

Pero, permite que diferentes elementos de la lista tengan cargas útiles de diferentes tamaños, lo que es potencialmente más incómodo con el segundo enfoque.

Para el segundo enfoque, volvería a ordenar la estructura para que el elemento de la lista esté en el inicio; esto da cierta flexibilidad con diferentes tamaños de carga.

struct person { 
    struct list_element list_entry; 
    unsigned int age; 
    char name[20]; // now could be variable length. 
}; 

Answer 4

El segundo enfoque es una lista intrusiva. Debe modificar la estructura que desea almacenar en la lista. Obtienes un poco de rendimiento con este enfoque debido a la menor indirección. Si necesita una solución más flexible y no el último bit de rendimiento, debe usar el primer enfoque.

Answer 5

El segundo método es 'intrusivo'; requiere una modificación del tipo que se coloca en la lista. El tipo en la lista (o listas) debe saber que está en la lista. Tienes que poder modificar la estructura para ponerla en las listas.

El primer método no es intrusivo. No requiere modificaciones a la estructura. Puedes poner cualquier tipo en la lista. Incluso podría tener tipos heterogéneos en una sola lista, aunque eso estaría plagado de problemas. Sin embargo, incluso si el tipo de base no es modificable por usted, puede colocarlo en el primer tipo de lista. Contra eso, requiere más espacio.

Por lo tanto, si tiene control total sobre el tipo de datos que se incluirán en la lista (y puede modificarlos para admitir las listas que necesita), el segundo tipo tiene algunas ventajas sobre el primero. En el contexto del kernel de Linux, las condiciones previas se cumplen y tiene sentido. De lo contrario, el primer tipo es más flexible, pero tiene un poco más de sobrecarga.

Answer 6

Creo que es más un problema conceptual/de análisis. ¿Funciona la entidad con algo que tiene listas o tiene una lista de instancias?

En otras palabras, si lo que está administrando en los datos tiene una existencia independiente, lo primero tiene sentido ya que los puntos de datos serán manipulados independientemente. Si los datos son siempre y necesariamente parte de la lista, entonces el segundo enfoque puede ser más claro.

Como en la mayoría de las decisiones de diseño, los criterios más importantes deben ser los más claros y obvios.

Answer 7

Esto, creo que es una pregunta muy subjetiva porque no se da ningún criterio contra el cual comparar los dos.

Para listas simples, tiendo a usar una combinación de las dos.

struct list_node { 
    struct list_node * prev; 
    struct list_node * next; 
}; 

struct some_struct { 
    struct list_node node; 
    ... 
}; 

Aunque esto parece casi idéntico a su segundo, tenga en cuenta que el nodo de lista enlazada es el primer elemento de "some_struct". Esto significa que cuando avanza a la siguiente, o rebobina al nodo anterior en la lista, el puntero está al comienzo de la estructura. De lo contrario, me vería obligado a realizar algunos cálculos de puntero para llegar al inicio de "some_struct". Como es actualmente, simplemente puedo lanzar.

Sin embargo, dicho método tiene sus limitaciones. Por ejemplo, si quería una estructura con más de una lista vinculada, cada uno de los métodos enumerados adolece del defecto en que requiere una aritmética de puntero para llegar al inicio de al menos una de las estructuras. Para evitar esto, algunas implementaciones (como las del código BSD VFS) utilizan macros para crear los elementos de la lista enlazados. En estos, la lista vinculada siempre apunta al inicio de la estructura, pero la macro contiene código para aplicar automáticamente el desplazamiento del nodo dentro de la estructura si lo desea (para avanzar al siguiente o rebobinar el anterior).

Espero que esto ayude.

Editar: Se corrigió cierta terminología.