data-structures - simples - operaciones con listas enlazadas
¿Utiliza listas enlazadas, listas doblemente enlazadas, etc. en la programación comercial? (12)
Ciertamente. Muchas implementaciones de "Lista" en idiomas modernos son en realidad listas enlazadas, a veces en combinación con matrices o tablas hash para acceso directo (por índice en lugar de iteración).
Las listas vinculadas (especialmente las listas doblemente vinculadas) se usan muy comúnmente en las estructuras de datos del "mundo real".
Me atrevería a decir que cada lenguaje común tiene una implementación preconstruida de lista enlazada, ya sea como una primitiva del lenguaje, biblioteca de plantillas nativas (por ejemplo, C ++), biblioteca nativa (por ejemplo, Java) o alguna implementación de terceros (probablemente de código abierto).
Dicho esto, varias veces en el pasado escribí una implementación de lista vinculada desde cero al crear código de infraestructura para estructuras de datos complejas. A veces es una buena idea tener un control total sobre la implementación, y algunas veces necesita agregar un "giro" a la implementación clásica para que satisfaga sus requisitos específicos. No está bien o mal cuando se trata de codificar su propia implementación, siempre que comprenda las alternativas y las compensaciones. En la mayoría de los casos, y ciertamente en lenguajes muy modernos como C #, lo evitaría.
Otro punto es cuando debe usar listas frente a matriz / vectores o tablas hash. A partir de su pregunta, entiendo que está al tanto de las concesiones aquí, así que no profundizaré en eso, pero básicamente, si su uso principal es atravesar listas por orden y el tamaño de la lista puede variar significativamente, una lista puede ser una opción viable. Otra consideración es el tipo de inserción. Si un caso de uso común es "insertar en el medio", entonces las listas tienen una ventaja significativa sobre las matrices / vectores. Puedo continuar, pero esta información está en los clásicos libros de CS :)
Aclaración: mi respuesta es independiente del idioma y no se relaciona específicamente con los genéricos que, a mi entender, tienen una implementación de lista vinculada.
¿Las estructuras de datos como enlaces enumeran algo que es puramente académico para la programación real o realmente los usa? ¿Son cosas que están cubiertas por medicamentos genéricos para que no tenga que construirlas (suponiendo que su lenguaje tenga genéricos)? No estoy debatiendo la importancia de comprender lo que son, solo el uso de ellos fuera de la academia. Lo pregunto desde una perspectiva de base de datos web de back-end. Estoy seguro de que alguien en algún lugar construye estos. Estoy preguntando desde mi contexto.
Gracias.
EDITAR: ¿Son genéricos para que no tengas que crear listas vinculadas y cosas por el estilo?
Dependiendo del uso, una lista vinculada podría ser la mejor opción. Las eliminaciones del principio de la lista son mucho más rápidas con una lista vinculada que una lista de arreglos.
En un programa Java que mantengo el perfil, pude aumentar el rendimiento al pasar de una lista de arreglos a una lista enlazada para una lista que tenía muchas eliminaciones al principio.
En una aplicación C / C ++ que desarrollé en mi última compañía utilizamos listas doblemente vinculadas todo el tiempo. Eran esenciales para lo que estábamos haciendo, que eran gráficos en 3D en tiempo real.
He estado desarrollando aplicaciones de línea de negocios (.NET) durante años y solo puedo pensar en una instancia en la que utilicé la lista de enlaces y, aun así, no tuve que crear el objeto.
Esta ha sido solo mi experiencia.
No me puedo imaginar muchos programas que no se ocupen de las listas. En el momento en que necesite ocuparse de más de 1 elemento de algo, se necesitan listas en todas las formas y formas, ya que necesita un lugar donde almacenar estas cosas. Esa lista puede ser una lista unida / doblemente enlazada, una matriz, un conjunto, una tabla hash si necesita indexar sus cosas en función de una clave, una cola de prioridad si necesita ordenarla, etc.
Normalmente almacenaría estas listas en un sistema de base de datos, pero en algún lugar debe buscarlas desde el archivo db, almacenarlas en su aplicación y manipularlas, incluso si es tan simple recuperar una pequeña lista de cosas que rellena en un archivo drop-up. abajo del combobox.
En estos días, en idiomas como C #, Python, Java y muchos más, generalmente se abstrae de tener que implementar sus propias listas. Estos idiomas vienen con una gran cantidad de abstracciones de contenedores en los que puede almacenar cosas. Ya sea a través de bibliotecas estándar o integradas en el lenguaje.
Aún tiene la ventaja de aprender estos temas, por ejemplo, si está trabajando con C #, le gustaría saber cómo funciona una ArrayList, y si elige ArrayList u otra cosa, dependiendo de su necesidad de agregar / insertar / búsqueda / índice aleatorio tal lista.
Nunca usé listas hechas a mano, excepto para tareas en la universidad.
Sí, hay una aplicación del mundo real que usa la lista vinculada, a veces tengo que mantener una gran aplicación que hace que tenga mucho uso de listas vinculadas.
Y sí, las listas enlazadas se incluyen en casi cualquier biblioteca de clases desde C ++ / STL a .NET.
Y desearía que usara matrices en su lugar.
En el mundo real, las listas vinculadas son LENTAS debido a cosas como la paginación y el tamaño de caché de la CPU (las listas vinculadas tienden a difundir datos y eso hace que sea más probable que necesite acceder a datos de diferentes áreas de la memoria y que sea mucho más lento en la actualidad computadoras que utilizan matrices que almacenan todos los datos en una secuencia).
Google "localidad de referencia" para más información.
Sí, todo tipo de estructuras de datos son muy útiles en el desarrollo diario de software. En la mayoría de los idiomas que conozco (C / C ++ / Python / Objective-C) hay marcos que implementan esas estructuras de datos para que no tenga que reinventar la rueda.
Y sí, las estructuras de datos no son solo para académicos, son muy útiles y no podrías escribir software sin ellas (depende de lo que hagas).
Usas estructuras de datos en colas de mensajes, mapas de datos, tablas hash, manteniendo ordenados los datos, acceso rápido / extracción / inserción y demás depende de lo que se necesite hacer.
Si, lo hago. Todo depende de la situación. Si no voy a almacenar una gran cantidad de datos en ellos, o si la aplicación específica necesita una estructura FIFO, los usaré sin pensarlo dos veces porque son rápidos de implementar.
Sin embargo, en las aplicaciones para otros desarrolladores que conozco, hay ocasiones en que una lista vinculada encajaría perfectamente, excepto que una localidad pobre causa muchas fallas en la memoria caché.
Una lista de enlaces únicos es la única forma de tener una lista inmutable de memoria eficiente que se puede componer para "mutar". Mira cómo Erlang lo hace. Puede ser un poco más lento que una lista con respaldo de matriz, pero tiene propiedades muy útiles en implementaciones multiproceso y puramente funcionales.
Yo diría que depende del uso, en algunos casos son más rápidos que los contenedores de acceso aleatorio típicos.
También creo que son utilizadas por algunas bibliotecas como un tipo de colección subyacente, por lo que lo que puede parecer una lista no vinculada podría ser una debajo.
Dependerá del idioma y los marcos que esté utilizando. La mayoría de los lenguajes y marcos modernos no te harán reinventar estas ruedas. En cambio, proporcionarán elementos como List<T> o HashTable.
EDITAR:
Probablemente usemos listas enlazadas todo el tiempo, pero no nos damos cuenta. No tenemos que escribir implementaciones de listas vinculadas por nuestra cuenta, porque los marcos que utilizamos ya las han escrito para nosotros.
También puede estar confundido acerca de "genéricos". Puede estar refiriéndose a las clases de lista genérica como List<T> . Esto es exactamente lo mismo que la Lista de clases no genérica, pero donde el elemento siempre es de tipo T Probablemente se implemente como una lista vinculada, pero no nos tiene que importar eso.
Tampoco tenemos que preocuparnos por la asignación de memoria física, o cómo funcionan las interrupciones, o cómo crear un sistema de archivos. Tenemos sistemas operativos para hacer eso por nosotros. Pero tal vez se nos enseñe esa información en la escuela de la misma manera.