tipos pseudocodigo listas ligadas introduccion estructura enlazadas datos colas algorithm language-agnostic data-structures

algorithm - pseudocodigo - listas ligadas



Nombre de la estructura de datos: matriz de combinación/lista enlazada (6)

He creado una estructura de datos que combina algunas de las ventajas de las listas enlazadas con algunas de las ventajas de los arreglos de tamaño fijo. Me parece muy obvio, por lo que espero que alguien lo haya pensado y lo haya nombrado ya. Alguien sabe como se llama esto:

Toma una pequeña matriz de tamaño fijo. Si el número de elementos que desea colocar en su matriz es mayor que el tamaño de la matriz, agregue una nueva matriz y los punteros que desee entre el antiguo y el 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 ———————————— ————————————

Edición : como referencia, este algoritmo proporciona un rendimiento de adición / eliminación peor en el peor de los casos, y no mucho mejor que el promedio de los casos. La gran ventaja para mi escenario es la mejora en el rendimiento del caché para las operaciones de lectura.

Editar recompensa : la respuesta de Antal SZ fue tan completa y tan bien investigada que quise brindarles una recompensa. Aparentemente, Stack Overflow no me permite aceptar una respuesta tan pronto como ofrezco una recompensa, así que tendré que esperar (es cierto que estoy abusando un poco del sistema de recompensas por intención, aunque es en nombre de recompensar a alguien por una excelente responder). Por supuesto, si alguien se las arregla para proporcionar una mejor respuesta, más poder para ellos, ¡y ciertamente pueden obtener la recompensa en su lugar!

Edite los nombres : no me interesa cómo lo llamaría, a menos que lo llamara así porque así lo llamarían las autoridades sobre el tema. Si es un nombre que se te ocurrió, no estoy interesado. Lo que quiero es un nombre que pueda buscar en 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 una "lista enlazada desenrollada" sin una buena razón, es simplemente errónea).

¿Cuáles son las ventajas de esta estructura de datos en términos de inserción y eliminación? Ej: ¿Qué pasa si quieres agregar un elemento entre 3 y 4? aún tiene que hacer un cambio, se necesita O (N) ¿Cómo encuentra el grupo correcto para elementAt?

Estoy de acuerdo con Jer, debes echar un vistazo a la lista de omisión . Trae las ventajas de la lista enlazada y matrices. La mayoría de las operaciones se realizan en O (log N)

Aunque no conozco su tarea, le sugiero que eche un vistazo a las listas de omisión.

En cuanto al nombre, estoy pensando que una lista de cubo sería probablemente la más apropiada

Puedes llamarlo LinkedArrays .

Además, me gustaría ver el pseudo-código para la operación removeIndex .

Se llama una lista enlazada desenrollada . Parece que hay un par de ventajas, una en velocidad y otra en el espacio. Primero, si el número de elementos en cada nodo tiene el tamaño adecuado ( por ejemplo , como máximo el tamaño de una línea de caché), obtendrá un rendimiento de caché notablemente mejor de la localidad de memoria mejorada. Segundo, como tiene enlaces O ( n / m ), donde n es el número de elementos en la lista enlazada desenrollada y m es el número de elementos que puede almacenar en cualquier nodo, también puede guardar una cantidad apreciable de espacio, que Es particularmente notable si cada elemento es pequeño. Al construir listas enlazadas sin enrollar, aparentemente las implementaciones intentarán dejar espacio en los nodos; Cuando intenta insertarlo en un nodo completo, mueve la mitad de los elementos hacia afuera. Por lo tanto, a lo sumo, un nodo estará menos de medio lleno. Y de acuerdo con lo que puedo encontrar (no he hecho ningún análisis por mí mismo), si inserta elementos al azar, los nodos tienden a estar casi tres cuartos llenos, o incluso más llenos si las operaciones tienden a estar al final de la lista.

Y como todos los demás (incluida la Wikipedia) están diciendo, es posible que desee revisar las listas de omisión . Las listas de omisiones son una estructura de datos probabilística ingeniosa utilizada para almacenar datos ordenados con O (log n ) tiempo de ejecución esperado para insertar, eliminar y encontrar. Se implementa mediante una "torre" de listas vinculadas, cada capa tiene menos elementos cuanto más arriba está. En la parte inferior, hay una lista enlazada normal, con todos los elementos. En cada capa sucesiva, hay menos elementos, por un factor de p (generalmente 1/2 o 1/4). La forma en que está construido es la siguiente. Cada vez que se agrega un elemento a la lista, se inserta en el lugar apropiado en la fila inferior (esto utiliza la operación de "búsqueda", que también se puede hacer rápido). Luego, con probabilidad p , se inserta en el lugar apropiado en la lista enlazada "arriba", creando esa lista si es necesario; si se colocó en una lista más alta, entonces volverá a aparecer arriba con probabilidad p . Para consultar algo en esta estructura de datos, siempre verifica el carril superior y ve si puede encontrarlo. Si el elemento que ve es demasiado grande, vaya al siguiente carril más bajo y comience a buscar nuevamente. Es una especie de búsqueda binaria. Wikipedia lo explica muy bien, y con bonitos diagramas. El uso de la memoria va a ser peor, por supuesto, y no vas a tener un mejor rendimiento del caché, pero en general será más rápido.

Referencias

Yo llamaría a esto una lista de cubo.

Codificación de CDR (si tiene la edad suficiente para recordar las máquinas Lisp).

También vea ropes que es una generalización de esta idea de lista / matriz para cadenas.