En informática , una lista enlazada es una colección lineal de elementos de datos cuyo orden no está determinado por su ubicación física en la memoria. En cambio, cada elemento apunta al siguiente. Es una estructura de datos que consiste en una colección de nodos que juntos representan una secuencia . En su forma más básica, cada nodo contiene datos y una referencia (en otras palabras, un enlace ) al siguiente nodo en la secuencia. Esta estructura permite la inserción o eliminación eficiente de elementos de cualquier posición en la secuencia durante la iteración. Las variantes más complejas agregan enlaces adicionales, lo que permite una inserción o eliminación más eficiente de nodos en posiciones arbitrarias. Una desventaja de las listas enlazadas es que el tiempo de acceso a los datos es lineal con respecto al número de nodos en la lista. Debido a que los nodos están enlazados en serie, acceder a cualquier nodo requiere que se acceda al nodo anterior de antemano (lo que introduce dificultades en la segmentación ). El acceso más rápido, como el acceso aleatorio, no es factible. Las matrices tienen una mejor localidad de caché en comparación con las listas enlazadas.
Las listas enlazadas se encuentran entre las estructuras de datos más simples y comunes. Se pueden usar para implementar varios otros tipos de datos abstractos comunes , incluidas listas , pilas , colas , matrices asociativas y expresiones S , aunque no es raro implementar esas estructuras de datos directamente sin usar una lista enlazada como base.
La principal ventaja de una lista enlazada con respecto a una matriz convencional es que los elementos de la lista se pueden insertar o eliminar fácilmente sin tener que reasignar o reorganizar toda la estructura, ya que los elementos de datos no necesitan almacenarse de forma contigua en la memoria o en el disco, mientras que la reestructuración de una matriz en tiempo de ejecución es una operación mucho más costosa. Las listas enlazadas permiten la inserción y eliminación de nodos en cualquier punto de la lista y permiten hacerlo con un número constante de operaciones, ya que mantienen el vínculo anterior a la adición o eliminación del vínculo en la memoria durante el recorrido de la lista.
Por otra parte, dado que las listas enlazadas simples por sí mismas no permiten un acceso aleatorio a los datos ni ninguna forma de indexación eficiente, muchas operaciones básicas (como obtener el último nodo de la lista, encontrar un nodo que contenga un dato dado o localizar el lugar donde debe insertarse un nuevo nodo) pueden requerir iterar a través de la mayoría o de todos los elementos de la lista.
Las listas enlazadas fueron desarrolladas en 1955-1956 por Allen Newell , Cliff Shaw y Herbert A. Simon en la Corporación RAND y la Universidad Carnegie Mellon como la estructura de datos principal para su Lenguaje de Procesamiento de Información (IPL). Los autores utilizaron IPL para desarrollar varios programas de inteligencia artificial tempranos, incluyendo la Máquina de Teoría Lógica, el Solucionador de Problemas Generales y un programa de ajedrez para computadora. Los informes sobre su trabajo aparecieron en IRE Transactions on Information Theory en 1956, y varias actas de conferencias de 1957 a 1959, incluyendo Proceedings of the Western Joint Computer Conference en 1957 y 1958, y Information Processing (Proceedings of the first UNESCO International Conference on Information Processing) en 1959. El diagrama ahora clásico que consiste en bloques que representan nodos de lista con flechas que apuntan a nodos de lista sucesivos aparece en "Programming the Logic Theory Machine" de Newell y Shaw en Proc. WJCC, febrero de 1957. Newell y Simon fueron reconocidos con el premio Turing de la ACM en 1975 por haber "realizado contribuciones básicas a la inteligencia artificial, la psicología de la cognición humana y el procesamiento de listas". El problema de la traducción automática para el procesamiento del lenguaje natural llevó a Victor Yngve, del Instituto Tecnológico de Massachusetts (MIT), a utilizar listas enlazadas como estructuras de datos en su lenguaje de programación COMIT para la investigación informática en el campo de la lingüística . Un informe sobre este lenguaje titulado "Un lenguaje de programación para la traducción mecánica" apareció en Mechanical Translation en 1958. [ cita requerida ]
Otra aparición temprana de listas enlazadas fue la de Hans Peter Luhn , quien escribió un memorando interno de IBM en enero de 1953 que sugería el uso de listas enlazadas en tablas hash encadenadas. [1]
LISP , acrónimo de list processing, fue creado por John McCarthy en 1958 mientras estaba en el MIT y en 1960 publicó su diseño en un artículo en Communications of the ACM , titulado "Funciones recursivas de expresiones simbólicas y su cálculo por máquina, parte I". Una de las principales estructuras de datos de LISP es la lista enlazada.
A principios de los años 60, la utilidad de las listas enlazadas y de los lenguajes que utilizan estas estructuras como representación primaria de datos ya estaba bien establecida. Bert Green, del Laboratorio Lincoln del MIT, publicó un artículo de revisión titulado "Lenguajes informáticos para la manipulación de símbolos" en IRE Transactions on Human Factors in Electronics en marzo de 1961, en el que resumía las ventajas del enfoque de las listas enlazadas. Un artículo de revisión posterior, "Una comparación de los lenguajes informáticos de procesamiento de listas" de Bobrow y Raphael, apareció en Communications of the ACM en abril de 1964.
Varios sistemas operativos desarrollados por Technical Systems Consultants (originalmente de West Lafayette, Indiana, y más tarde de Chapel Hill, Carolina del Norte) utilizaban listas enlazadas simples como estructuras de archivos. Una entrada de directorio apuntaba al primer sector de un archivo y las porciones siguientes del archivo se localizaban mediante punteros. Entre los sistemas que utilizaban esta técnica se encontraban Flex (para la CPU Motorola 6800 ), mini-Flex (la misma CPU) y Flex9 (para la CPU Motorola 6809). Una variante desarrollada por TSC para Smoke Signal Broadcasting en California y comercializada por esta empresa utilizaba listas doblemente enlazadas de la misma manera.
El sistema operativo TSS/360, desarrollado por IBM para las máquinas System 360/370, utilizaba una lista doblemente enlazada para el catálogo de su sistema de archivos. La estructura de directorios era similar a la de Unix, donde un directorio podía contener archivos y otros directorios y extenderse hasta cualquier profundidad.
Cada registro de una lista enlazada se denomina a menudo «elemento» o « nodo ».
El campo de cada nodo que contiene la dirección del siguiente nodo se suele denominar "próximo enlace" o "próximo puntero". Los campos restantes se conocen como campos "datos", "información", "valor", "carga" o "carga útil".
La 'cabeza' de una lista es su primer nodo. La 'cola' de una lista puede hacer referencia al resto de la lista después de la cabeza, o al último nodo de la lista. En Lisp y algunos lenguajes derivados, el siguiente nodo puede llamarse ' cdr ' (pronunciado /'kʊd.əɹ/ ) de la lista, mientras que la carga útil del nodo de la cabeza puede llamarse 'car'.
Las listas enlazadas simples contienen nodos que tienen un campo "valor" y un campo "siguiente", que apunta al siguiente nodo en la fila de nodos. Las operaciones que se pueden realizar en listas enlazadas simples incluyen inserción, eliminación y recorrido.
El siguiente código en lenguaje C demuestra cómo agregar un nuevo nodo con el "valor" al final de una lista enlazada simple:
// Cada nodo de una lista enlazada es una estructura. El nodo principal es el primer nodo de la lista.Nodo * addNodeToTail ( Nodo * cabeza , int valor ) { // declara el puntero de nodo y lo inicializa para apuntar al nuevo nodo (es decir, tendrá la dirección de memoria del nuevo nodo) que se agrega al final de la lista. Nodo * temp = malloc ( sizeof * temp ); /// 'malloc' en la biblioteca estándar. temp -> value = value ; // Agrega datos al campo de valor del nuevo nodo. temp -> next = NULL ; // inicializa enlaces inválidos a nulos. si ( cabeza == NULL ) { cabeza = temp ; // Si la lista enlazada está vacía (es decir, el puntero del nodo principal es un puntero nulo), entonces haga que el puntero del nodo principal apunte al nuevo nodo. } demás { Nodo * p = cabeza ; // Asigna el puntero del nodo principal al puntero del nodo 'p'. mientras ( p -> siguiente != NULL ) { p = p -> next ; // Recorre la lista hasta que p sea el último nodo. El último nodo siempre apunta a NULL. } p -> next = temp ; // Hacer que el último nodo anterior apunte al nuevo nodo. } retorna cabeza ; // Devuelve el puntero del nodo principal. }En una "lista doblemente enlazada", cada nodo contiene, además del enlace del nodo siguiente, un segundo campo de enlace que apunta al nodo "anterior" de la secuencia. Los dos enlaces pueden llamarse "forward('s') y "backwards", o "next" y "prev"('previous').
Una técnica conocida como enlace XOR permite implementar una lista doblemente enlazada utilizando un único campo de enlace en cada nodo. Sin embargo, esta técnica requiere la capacidad de realizar operaciones de bits en direcciones y, por lo tanto, puede no estar disponible en algunos lenguajes de alto nivel.
Muchos sistemas operativos modernos utilizan listas doblemente enlazadas para mantener referencias a procesos activos, subprocesos y otros objetos dinámicos. [2] Una estrategia común de los rootkits para evadir la detección es desvincularse de estas listas. [3]
En una "lista enlazada múltiple", cada nodo contiene dos o más campos de enlace, cada uno de los cuales se utiliza para conectar el mismo conjunto de datos organizados en un orden diferente (por ejemplo, por nombre, por departamento, por fecha de nacimiento, etc.). Si bien una lista doblemente enlazada puede considerarse un caso especial de lista enlazada múltiple, el hecho de que los dos o más órdenes sean opuestos entre sí conduce a algoritmos más simples y eficientes, por lo que generalmente se tratan como un caso separado.
En el último nodo de una lista enlazada, el campo de enlace suele contener una referencia nula ; se utiliza un valor especial para indicar la falta de nodos adicionales. Una convención menos común es hacer que apunte al primer nodo de la lista; en ese caso, se dice que la lista es "circular" o "enlazada circularmente"; de lo contrario, se dice que es "abierta" o "lineal". Es una lista en la que el puntero del último nodo apunta al primer nodo (es decir, el puntero del "próximo enlace" del último nodo tiene la dirección de memoria del primer nodo).
En el caso de una lista circular doblemente enlazada, el primer nodo también apunta al último nodo de la lista.
En algunas implementaciones, se puede agregar un nodo "centinela" o "ficticio" adicional antes del primer registro de datos o después del último. Esta convención simplifica y acelera algunos algoritmos de manejo de listas, al garantizar que todos los vínculos se puedan desreferenciar de manera segura y que cada lista (incluso una que no contenga elementos de datos) siempre tenga un "primer" y un "último" nodo.
Una lista vacía es una lista que no contiene registros de datos. Esto suele ser lo mismo que decir que no tiene ningún nodo. Si se utilizan nodos centinela, normalmente se dice que la lista está vacía cuando solo tiene nodos centinela.
Los campos de enlace no necesitan ser parte física de los nodos. Si los registros de datos se almacenan en una matriz y se hace referencia a ellos mediante sus índices, el campo de enlace puede almacenarse en una matriz separada con los mismos índices que los registros de datos.
Dado que una referencia al primer nodo da acceso a toda la lista, esa referencia suele denominarse "dirección", "puntero" o "identificador" de la lista. Los algoritmos que manipulan listas enlazadas suelen obtener dichos identificadores para las listas de entrada y devolver los identificadores para las listas resultantes. De hecho, en el contexto de dichos algoritmos, la palabra "lista" suele significar "identificador de lista". Sin embargo, en algunas situaciones puede resultar conveniente hacer referencia a una lista mediante un identificador que consta de dos enlaces, que apuntan a su primer y último nodo.
Las alternativas enumeradas anteriormente se pueden combinar arbitrariamente en casi todas las formas, por lo que se pueden tener listas circulares doblemente enlazadas sin centinelas, listas circulares simplemente enlazadas con centinelas, etc.
Como ocurre con la mayoría de las opciones en programación y diseño informático, ningún método es adecuado para todas las circunstancias. Una estructura de datos de lista enlazada puede funcionar bien en un caso, pero causar problemas en otro. A continuación, se incluye una lista de algunas de las desventajas más comunes que implican las estructuras de lista enlazada.
Una matriz dinámica es una estructura de datos que asigna todos los elementos de forma contigua en la memoria y lleva un recuento del número actual de elementos. Si se excede el espacio reservado para la matriz dinámica, esta se reasigna y (posiblemente) se copia, lo que es una operación costosa.
Las listas enlazadas tienen varias ventajas sobre las matrices dinámicas. La inserción o eliminación de un elemento en un punto específico de una lista, suponiendo que ya hemos indexado un puntero al nodo (antes del que se va a eliminar, o antes del punto de inserción), es una operación de tiempo constante (de lo contrario, sin esta referencia es O(n)), mientras que la inserción en una matriz dinámica en ubicaciones aleatorias requerirá mover la mitad de los elementos en promedio, y todos los elementos en el peor de los casos. Si bien uno puede "eliminar" un elemento de una matriz en tiempo constante marcando de alguna manera su ranura como "vacante", esto causa fragmentación que impide el rendimiento de la iteración.
Además, se pueden insertar arbitrariamente muchos elementos en una lista enlazada, limitados únicamente por la memoria total disponible; mientras que una matriz dinámica eventualmente llenará su estructura de datos de matriz subyacente y tendrá que reasignarse, una operación costosa, que puede no ser posible incluso si la memoria está fragmentada, aunque el costo de la reasignación se puede promediar sobre las inserciones, y el costo de una inserción debido a la reasignación todavía se amortizaría O(1). Esto ayuda a agregar elementos al final de la matriz, pero la inserción en (o eliminación de) posiciones intermedias aún conlleva costos prohibitivos debido al movimiento de datos para mantener la contigüidad. Una matriz de la que se eliminan muchos elementos también puede tener que cambiar de tamaño para evitar desperdiciar demasiado espacio.
Por otro lado, las matrices dinámicas (así como las estructuras de datos de matrices de tamaño fijo) permiten un acceso aleatorio en tiempo constante , mientras que las listas enlazadas solo permiten un acceso secuencial a los elementos. De hecho, las listas enlazadas simples se pueden recorrer fácilmente en una sola dirección. Esto hace que las listas enlazadas no sean adecuadas para aplicaciones en las que es útil buscar un elemento por su índice rápidamente, como heapsort . El acceso secuencial en matrices y matrices dinámicas también es más rápido que en listas enlazadas en muchas máquinas, porque tienen una localidad de referencia óptima y, por lo tanto, hacen un buen uso del almacenamiento en caché de datos.
Otra desventaja de las listas enlazadas es el almacenamiento adicional necesario para las referencias, lo que a menudo las hace poco prácticas para listas de elementos de datos pequeños, como caracteres o valores booleanos , porque la sobrecarga de almacenamiento para los enlaces puede exceder en un factor de dos o más el tamaño de los datos. Por el contrario, una matriz dinámica solo requiere el espacio para los datos en sí (y una cantidad muy pequeña de datos de control). [nota 1] También puede ser lento, y con un asignador ingenuo, un desperdicio, asignar memoria por separado para cada nuevo elemento, un problema que generalmente se resuelve utilizando grupos de memoria .
Algunas soluciones híbridas intentan combinar las ventajas de las dos representaciones. Las listas enlazadas desenrolladas almacenan varios elementos en cada nodo de la lista, lo que aumenta el rendimiento de la memoria caché y reduce la sobrecarga de memoria para las referencias. La codificación CDR también hace ambas cosas, reemplazando las referencias con los datos reales a los que se hace referencia, que se extienden más allá del final del registro de referencia.
Un buen ejemplo que resalta las ventajas y desventajas de usar arreglos dinámicos en vez de listas enlazadas es implementar un programa que resuelva el problema de Josefo . El problema de Josefo es un método de elección que funciona haciendo que un grupo de personas se coloquen en un círculo. Comenzando con una persona predeterminada, uno puede contar alrededor del círculo n veces. Una vez que se llega a la n -ésima persona, uno debe eliminarla del círculo y hacer que los miembros cierren el círculo. El proceso se repite hasta que solo quede una persona. Esa persona gana la elección. Esto muestra las fortalezas y debilidades de una lista enlazada en comparación con un arreglo dinámico, porque si las personas se ven como nodos conectados en una lista enlazada circular, entonces muestra cuán fácilmente la lista enlazada puede eliminar nodos (ya que solo tiene que reorganizar los enlaces a los diferentes nodos). Sin embargo, la lista enlazada será pobre para encontrar la siguiente persona a eliminar y necesitará buscar a través de la lista hasta que encuentre a esa persona. Por otro lado, una matriz dinámica no será eficaz para eliminar nodos (o elementos), ya que no puede eliminar un nodo sin desplazar individualmente todos los elementos hacia arriba en la lista en un nivel. Sin embargo, es excepcionalmente fácil encontrar la n- ésima persona en el círculo haciendo referencia directa a ella por su posición en la matriz.
El problema de clasificación de listas se refiere a la conversión eficiente de una representación de lista enlazada en una matriz. Aunque es trivial para una computadora convencional, resolver este problema mediante un algoritmo paralelo es complicado y ha sido objeto de mucha investigación.
Un árbol equilibrado tiene patrones de acceso a la memoria y una sobrecarga de espacio similares a los de una lista enlazada, al tiempo que permite una indexación mucho más eficiente, ya que requiere un tiempo de O(log n) en lugar de O(n) para un acceso aleatorio. Sin embargo, las operaciones de inserción y eliminación son más costosas debido a la sobrecarga de las manipulaciones del árbol para mantener el equilibrio. Existen esquemas para que los árboles se mantengan automáticamente en un estado equilibrado: árboles AVL o árboles rojo-negros .
Si bien las listas doblemente enlazadas y circulares tienen ventajas sobre las listas lineales simplemente enlazadas, las listas lineales ofrecen algunas ventajas que las hacen preferibles en algunas situaciones.
Una lista lineal enlazada de forma simple es una estructura de datos recursiva , ya que contiene un puntero a un objeto más pequeño del mismo tipo. Por ese motivo, muchas operaciones en listas lineales enlazadas de forma simple (como fusionar dos listas o enumerar los elementos en orden inverso) suelen tener algoritmos recursivos muy simples, mucho más simples que cualquier solución que utilice comandos iterativos . Si bien esas soluciones recursivas se pueden adaptar para listas enlazadas de forma doble y circular, los procedimientos generalmente necesitan argumentos adicionales y casos base más complicados.
Las listas lineales enlazadas simples también permiten compartir la cola , es decir, usar una porción final común de una sublista como la porción terminal de dos listas diferentes. En particular, si se agrega un nuevo nodo al comienzo de una lista, la lista anterior permanece disponible como la cola de la nueva, un ejemplo simple de una estructura de datos persistente . Nuevamente, esto no es cierto con las otras variantes: un nodo nunca puede pertenecer a dos listas circulares o doblemente enlazadas diferentes.
En particular, los nodos centinela final pueden compartirse entre listas no circulares enlazadas individualmente. Se puede utilizar el mismo nodo centinela final para cada una de esas listas. En Lisp , por ejemplo, cada lista propia termina con un enlace a un nodo especial, denotado por nilo ().
Las ventajas de las variantes sofisticadas suelen limitarse a la complejidad de los algoritmos, no a su eficiencia. Una lista circular, en particular, puede ser emulada normalmente por una lista lineal junto con dos variables que apuntan al primer y último nodo, sin ningún coste adicional.
Las listas doblemente enlazadas requieren más espacio por nodo (a menos que se utilice el método XOR ), y sus operaciones elementales son más costosas; pero a menudo son más fáciles de manipular porque permiten un acceso secuencial rápido y fácil a la lista en ambas direcciones. En una lista doblemente enlazada, se puede insertar o eliminar un nodo en un número constante de operaciones dada solo la dirección de ese nodo. Para hacer lo mismo en una lista simplemente enlazada, se debe tener la dirección del puntero a ese nodo, que es el identificador de toda la lista (en el caso del primer nodo) o el campo de enlace en el nodo anterior . Algunos algoritmos requieren acceso en ambas direcciones. Por otro lado, las listas doblemente enlazadas no permiten compartir colas y no se pueden usar como estructuras de datos persistentes .
Una lista enlazada circularmente puede ser una opción natural para representar matrices que son naturalmente circulares, por ejemplo, las esquinas de un polígono , un grupo de buffers que se usan y liberan en orden FIFO ("primero en entrar, primero en salir") o un conjunto de procesos que deberían compartirse en el tiempo en orden round-robin . En estas aplicaciones, un puntero a cualquier nodo sirve como identificador de toda la lista.
En una lista circular, un puntero al último nodo permite acceder fácilmente también al primer nodo, siguiendo un enlace. Por lo tanto, en aplicaciones que requieren acceso a ambos extremos de la lista (por ejemplo, en la implementación de una cola), una estructura circular permite manejar la estructura mediante un solo puntero, en lugar de dos.
Una lista circular se puede dividir en dos listas circulares, en tiempo constante, dando las direcciones del último nodo de cada pieza. La operación consiste en intercambiar los contenidos de los campos de enlace de esos dos nodos. Al aplicar la misma operación a dos nodos cualesquiera de dos listas distintas, se unen las dos listas en una sola. Esta propiedad simplifica enormemente algunos algoritmos y estructuras de datos, como los de aristas cuadradas y de aristas de caras.
La representación más simple de una lista circular vacía (cuando tal cosa tiene sentido) es un puntero nulo, que indica que la lista no tiene nodos. Sin esta opción, muchos algoritmos tienen que probar este caso especial y manejarlo por separado. Por el contrario, el uso de null para denotar una lista lineal vacía es más natural y a menudo crea menos casos especiales.
Para algunas aplicaciones, puede resultar útil utilizar listas enlazadas simples que pueden variar entre circulares y lineales, o incluso circulares con un segmento inicial lineal. Los algoritmos para buscar o trabajar con ellas deben tomar precauciones para evitar entrar accidentalmente en un bucle infinito. Un método conocido es tener un segundo puntero que recorra la lista a la mitad o al doble de velocidad, y si ambos punteros se encuentran en el mismo nodo, sabrá que ha encontrado un ciclo.
El nodo centinela puede simplificar ciertas operaciones de lista, al garantizar que los nodos siguientes o anteriores existan para cada elemento, y que incluso las listas vacías tengan al menos un nodo. También se puede usar un nodo centinela al final de la lista, con un campo de datos apropiado, para eliminar algunas pruebas de fin de lista. Por ejemplo, al escanear la lista en busca de un nodo con un valor dado x , configurar el campo de datos del centinela en x hace innecesario realizar pruebas de fin de lista dentro del bucle. Otro ejemplo es la fusión de dos listas ordenadas: si sus centinelas tienen campos de datos configurados en +∞, la elección del siguiente nodo de salida no necesita un manejo especial para listas vacías.
Sin embargo, los nodos centinela utilizan espacio adicional (especialmente en aplicaciones que utilizan muchas listas cortas) y pueden complicar otras operaciones (como la creación de una nueva lista vacía).
Sin embargo, si la lista circular se utiliza simplemente para simular una lista lineal, se puede evitar parte de esta complejidad añadiendo un único nodo centinela a cada lista, entre el último y el primer nodo de datos. Con esta convención, una lista vacía consta únicamente del nodo centinela, que apunta a sí mismo mediante el enlace del siguiente nodo. El identificador de la lista debería ser entonces un puntero al último nodo de datos, antes del centinela, si la lista no está vacía; o al centinela mismo, si la lista está vacía.
El mismo truco se puede utilizar para simplificar el manejo de una lista lineal doblemente enlazada, convirtiéndola en una lista circular doblemente enlazada con un único nodo centinela. Sin embargo, en este caso, el identificador debe ser un único puntero al propio nodo ficticio. [8]
Al manipular listas enlazadas en el lugar, se debe tener cuidado de no usar valores que haya invalidado en tareas anteriores. Esto hace que los algoritmos para insertar o eliminar nodos de listas enlazadas sean algo sutiles. Esta sección proporciona pseudocódigo para agregar o eliminar nodos de listas enlazadas simples, dobles y circulares en el lugar. A lo largo del texto, utilizaremos null para hacer referencia a un marcador de fin de lista o centinela , que se puede implementar de varias maneras.
Nuestra estructura de datos de nodos tendrá dos campos. También mantenemos una variable firstNode que siempre apunta al primer nodo de la lista o es nula si la lista está vacía.
Nodo de registro{ datos; // Los datos que se almacenan en el nodo Nodo siguiente // Una referencia [2] al siguiente nodo, nula para el último nodo} Lista de registros{ Nodo firstNode // apunta al primer nodo de la lista; nulo para lista vacía}El recorrido de una lista enlazada simple es sencillo: se comienza en el primer nodo y se sigue cada enlace siguiente hasta llegar al final:
nodo := list.firstNode mientras nodo no sea nulo (hacer algo con nodo.data) nodo := nodo.siguiente
El código siguiente inserta un nodo después de un nodo existente en una lista enlazada simple. El diagrama muestra cómo funciona. No se puede insertar un nodo antes de uno existente directamente; en su lugar, se debe hacer un seguimiento del nodo anterior e insertar un nodo después de él.
función insertAfter( Nodo nodo , Nodo nuevoNodo) // inserta nuevoNodo después del nodo nuevoNodo.siguiente := nodo.siguiente nodo.siguiente := nuevoNodo
Para insertar al principio de la lista se necesita una función aparte. Para ello es necesario actualizar firstNode .
función insertBeginning( Lista lista , Nodo nuevoNodo) // inserta el nodo antes del primer nodo actual nuevoNodo.siguiente := lista.primerNodo lista.primerNodo := nuevoNodo
De manera similar, tenemos funciones para eliminar el nodo que se encuentra después de un nodo determinado y para eliminar un nodo del principio de la lista. El diagrama muestra lo primero. Para encontrar y eliminar un nodo en particular, uno debe volver a realizar un seguimiento del elemento anterior.
función removeAfter( Nodo nodo ) // eliminar el nodo después de este nodo obsoleto := nodo.siguiente nodo.siguiente := nodo.siguiente.siguiente destruir nodo obsoleto
función removeBeginning( Lista lista ) // eliminar el primer nodo nodoObsoleto := lista.primerNodo list.firstNode := list.firstNode.next // apunta más allá del nodo eliminado destruir nodo obsoleto
Tenga en cuenta que se removeBeginning()establece al eliminar el último nodo de la lista.list.firstNodenull
Dado que no podemos iterar hacia atrás, no es posible realizar operaciones insertBeforeo eficientes removeBefore. Para insertar una lista antes de un nodo específico es necesario recorrer la lista, lo que tendría un tiempo de ejecución de O(n) en el peor de los casos.
Añadir una lista enlazada a otra puede ser ineficiente a menos que se mantenga una referencia a la cola como parte de la estructura de la lista, porque debemos recorrer toda la primera lista para encontrar la cola y luego añadir la segunda lista a esta. Por lo tanto, si dos listas enlazadas linealmente tienen cada una una longitud , la adición de listas tiene una complejidad temporal asintótica de . En la familia de lenguajes Lisp, la adición de listas la proporciona el procedimiento.append
Muchos de los casos especiales de operaciones de listas enlazadas se pueden eliminar incluyendo un elemento ficticio al principio de la lista. Esto garantiza que no haya casos especiales para el comienzo de la lista y hace que tanto insertBeginning()y sean removeBeginning()innecesarios, es decir, cada elemento o nodo está junto a otro nodo (incluso el primer nodo está junto al nodo ficticio). En este caso, los primeros datos útiles de la lista se encontrarán en .list.firstNode.next
En una lista enlazada circularmente, todos los nodos están enlazados en un círculo continuo, sin utilizar valores nulos. En el caso de listas con un frente y un reverso (como una cola), se almacena una referencia al último nodo de la lista. El siguiente nodo después del último nodo es el primer nodo. Se pueden agregar elementos al final de la lista y eliminarlos del frente en tiempo constante.
Las listas enlazadas circularmente pueden estar enlazadas simple o doblemente.
Ambos tipos de listas enlazadas circularmente se benefician de la capacidad de recorrer la lista completa comenzando en cualquier nodo dado. Esto a menudo nos permite evitar almacenar firstNode y lastNode , aunque si la lista puede estar vacía necesitamos una representación especial para la lista vacía, como una variable lastNode que apunta a algún nodo en la lista o es nula si está vacía; usamos un lastNode de este tipo aquí. Esta representación simplifica significativamente la adición y eliminación de nodos con una lista no vacía, pero las listas vacías son un caso especial.
Suponiendo que someNode es un nodo en una lista enlazada simple circular no vacía, este código itera a través de esa lista comenzando con someNode :
función iterar(someNode) si someNode ≠ null nodo := algúnNodo hacer hacer algo con node.value nodo := nodo.siguiente mientras nodo ≠ algúnNodo
Tenga en cuenta que la prueba " mientras que nodo ≠ algúnNodo" debe estar al final del bucle. Si la prueba se moviera al principio del bucle, el procedimiento fallaría siempre que la lista tuviera solo un nodo.
Esta función inserta un nodo "newNode" en una lista enlazada circular después de un nodo "node" determinado. Si "node" es nulo, se supone que la lista está vacía.
función insertAfter( Nodo nodo , Nodo nuevoNodo) si nodo = null // se supone que la lista está vacía nuevoNodo.siguiente := nuevoNodo demás nuevoNodo.siguiente := nodo.siguiente nodo.siguiente := nuevoNodo Actualice la variable lastNode si es necesario
Supongamos que "L" es una variable que apunta al último nodo de una lista enlazada circular (o null si la lista está vacía). Para añadir "newNode" al final de la lista, se puede hacer lo siguiente:
insertarDespués(L, nuevoNodo)L := nuevoNodo
Para insertar "newNode" al principio de la lista, se puede hacer
insertAfter(L, nuevoNodo) si L = nulo L := nuevoNodo
Esta función inserta un valor "newVal" antes de un nodo dado "node" en tiempo O(1). Creamos un nuevo nodo entre "node" y el siguiente nodo, y luego colocamos el valor de "node" en ese nuevo nodo, y colocamos "newVal" en "node". Por lo tanto, una lista enlazada circularmente con un solo enlace con una variable firstNode puede insertarse tanto al principio como al final en tiempo O(1).
función insertBefore( Nodo nodo , newVal) si nodo = null // se supone que la lista está vacía nuevoNodo := nuevo Nodo(datos:=nuevoVal, siguiente:=nuevoNodo) de lo contrario nuevoNodo := nuevo Nodo(datos:=nodo.datos, siguiente:=nodo.siguiente) nodo.data := newVal nodo.siguiente := nuevoNodo Actualice la variable firstNode si es necesario
Esta función elimina un nodo no nulo de una lista de tamaño mayor que 1 en tiempo O(1). Copia datos del siguiente nodo en el nodo anterior y luego establece el puntero siguiente del nodo para que salte el siguiente nodo.
función remove( Nodo nodo ) si nodo ≠ nulo y tamaño de la lista > 1 Datos eliminados := nodo.data nodo.datos := nodo.siguiente.datos nodo.siguiente = nodo.siguiente.siguiente devolver datos eliminados
Los lenguajes que no admiten ningún tipo de referencia pueden crear enlaces reemplazando punteros con índices de matriz. El enfoque consiste en mantener una matriz de registros , donde cada registro tiene campos enteros que indican el índice del siguiente nodo (y posiblemente el anterior) en la matriz. No es necesario utilizar todos los nodos de la matriz. Si tampoco se admiten registros, a menudo se pueden utilizar matrices paralelas en su lugar.
Como ejemplo, considere el siguiente registro de lista enlazada que utiliza matrices en lugar de punteros:
registro Entrada { entero siguiente; // índice de la siguiente entrada en la matriz entero anterior; // entrada anterior (si tiene doble enlace) cadena nombre; saldo real ;}Se puede construir una lista enlazada creando una matriz de estas estructuras y una variable entera para almacenar el índice del primer elemento.
Lista de enteros Entrada principal Registros[1000]
Los vínculos entre elementos se forman colocando el índice de la matriz de la celda siguiente (o anterior) en el campo Siguiente o Anterior dentro de un elemento determinado. Por ejemplo:
En el ejemplo anterior, ListHeadse establecería en 2, la ubicación de la primera entrada en la lista. Observe que las entradas 3 y 5 a 7 no forman parte de la lista. Estas celdas están disponibles para cualquier adición a la lista. Al crear una ListFreevariable entera, se podría crear una lista libre para realizar un seguimiento de las celdas que están disponibles. Si todas las entradas están en uso, se debería aumentar el tamaño de la matriz o se deberían eliminar algunos elementos antes de poder almacenar nuevas entradas en la lista.
El siguiente código recorrería la lista y mostraría los nombres y el saldo de la cuenta:
i := listHead while i ≥ 0 // recorrer la lista print i, Records[i].name, Records[i].balance // imprimir entrada i := Registros[i].siguiente
Ante una elección, las ventajas de este enfoque incluyen:
Sin embargo, este enfoque tiene una desventaja principal: crea y administra un espacio de memoria privado para sus nodos. Esto genera los siguientes problemas:
Por estos motivos, este enfoque se utiliza principalmente en lenguajes que no admiten la asignación dinámica de memoria. Estas desventajas también se mitigan si se conoce el tamaño máximo de la lista en el momento de crear la matriz.
Muchos lenguajes de programación como Lisp y Scheme tienen listas enlazadas simples integradas. En muchos lenguajes funcionales , estas listas se construyen a partir de nodos, cada uno llamado cons o cons cell . El cons tiene dos campos: el car , una referencia a los datos de ese nodo, y el cdr , una referencia al siguiente nodo. Aunque las cons cells se pueden utilizar para construir otras estructuras de datos, este es su propósito principal.
En los lenguajes que admiten tipos de datos abstractos o plantillas, existen ADT o plantillas de listas enlazadas para crear listas enlazadas. En otros lenguajes, las listas enlazadas se crean normalmente utilizando referencias junto con registros .
Al construir una lista enlazada, uno se enfrenta a la elección de si almacenar los datos de la lista directamente en los nodos de la lista enlazada, llamado almacenamiento interno , o simplemente almacenar una referencia a los datos, llamado almacenamiento externo . El almacenamiento interno tiene la ventaja de hacer que el acceso a los datos sea más eficiente, requiere menos almacenamiento en general, tiene una mejor localidad de referencia y simplifica la gestión de memoria para la lista (sus datos se asignan y desasignan al mismo tiempo que los nodos de la lista).
Por otra parte, el almacenamiento externo tiene la ventaja de ser más genérico, ya que se puede utilizar la misma estructura de datos y el mismo código de máquina para una lista enlazada sin importar el tamaño de los datos. También facilita la colocación de los mismos datos en varias listas enlazadas. Aunque con el almacenamiento interno los mismos datos se pueden colocar en varias listas incluyendo varias referencias siguientes en la estructura de datos del nodo, sería necesario crear rutinas independientes para añadir o eliminar celdas en función de cada campo. Es posible crear listas enlazadas adicionales de elementos que utilizan el almacenamiento interno utilizando el almacenamiento externo y haciendo que las celdas de las listas enlazadas adicionales almacenen referencias a los nodos de la lista enlazada que contienen los datos.
En general, si se necesita incluir un conjunto de estructuras de datos en listas enlazadas, el almacenamiento externo es la mejor opción. Si se necesita incluir un conjunto de estructuras de datos en una sola lista enlazada, el almacenamiento interno es ligeramente mejor, a menos que esté disponible un paquete de lista enlazada genérica que utilice almacenamiento externo. Del mismo modo, si se deben incluir en una sola lista enlazada diferentes conjuntos de datos que se pueden almacenar en la misma estructura de datos, el almacenamiento interno sería adecuado.
Otro enfoque que se puede utilizar con algunos lenguajes implica tener diferentes estructuras de datos, pero todas tienen los campos iniciales, incluidas las referencias next (y prev si se trata de una lista doblemente enlazada) en la misma ubicación. Después de definir estructuras separadas para cada tipo de datos, se puede definir una estructura genérica que contenga la cantidad mínima de datos compartidos por todas las demás estructuras y que estén contenidos en la parte superior (inicio) de las estructuras. Luego se pueden crear rutinas genéricas que utilicen la estructura mínima para realizar operaciones de tipo lista enlazada, pero luego rutinas separadas pueden manejar los datos específicos. Este enfoque se utiliza a menudo en rutinas de análisis de mensajes, donde se reciben varios tipos de mensajes, pero todos comienzan con el mismo conjunto de campos, que generalmente incluyen un campo para el tipo de mensaje. Las rutinas genéricas se utilizan para agregar nuevos mensajes a una cola cuando se reciben y eliminarlos de la cola para procesar el mensaje. Luego, el campo de tipo de mensaje se utiliza para llamar a la rutina correcta para procesar el tipo específico de mensaje.
Supongamos que desea crear una lista enlazada de familias y sus miembros. Si utiliza el almacenamiento interno, la estructura podría ser similar a la siguiente:
registrar miembro { // miembro de una familia miembro siguiente; cadena nombre; entero edad;}record family { // la familia misma family next; string lastName; string address; member members // cabeza de la lista de miembros de esta familia}Para imprimir una lista completa de familias y sus miembros utilizando el almacenamiento interno, podríamos escribir:
aFamily := Familias // comienza en el encabezado de la lista de familias mientras que aFamily ≠ null // recorre la lista de familias Imprimir información sobre la familia aMember := aFamily.members // obtiene el encabezado de la lista de miembros de esta familia mientras aMember ≠ null // recorre la lista de miembros Imprimir información sobre el miembro unMiembro := unMiembro.siguiente unaFamilia := unaFamilia.siguiente
Usando almacenamiento externo, crearíamos las siguientes estructuras:
nodo de registro { // estructura de enlace genérica nodo siguiente; puntero datos // puntero genérico para datos en el nodo} miembro de registro { // estructura para el miembro de la familia cadena firstName; entero edad} familia de registros { // estructura para la familia cadena apellido; cadena dirección; miembros del nodo // encabezado de la lista de miembros de esta familia}Para imprimir una lista completa de familias y sus miembros usando almacenamiento externo, podríamos escribir:
famNode := Families // comienza en el encabezado de la lista de familias mientras famNode ≠ null // recorre la lista de familias aFamily := (familia) famNode.data // extrae la familia del nodo Imprimir información sobre la familia memNode := aFamily.members // obtener la lista de miembros de la familia mientras memNode ≠ null // recorrer la lista de miembros aMember := (member)memNode.data // extraer miembro del nodo Imprimir información sobre el miembro memNode := memNode.siguiente famNode := famNode.siguiente
Tenga en cuenta que, al utilizar un almacenamiento externo, se necesita un paso adicional para extraer el registro del nodo y convertirlo en el tipo de datos adecuado. Esto se debe a que tanto la lista de familias como la lista de miembros dentro de la familia se almacenan en dos listas enlazadas que utilizan la misma estructura de datos ( nodo ) y este lenguaje no tiene tipos paramétricos.
Siempre que se conozca en tiempo de compilación la cantidad de familias a las que puede pertenecer un miembro, el almacenamiento interno funciona bien. Sin embargo, si fuera necesario incluir a un miembro en una cantidad arbitraria de familias, y la cantidad específica se conociera solo en tiempo de ejecución, sería necesario un almacenamiento externo.
Encontrar un elemento específico en una lista enlazada, incluso si está ordenada, normalmente requiere un tiempo O( n ) ( búsqueda lineal ). Esta es una de las principales desventajas de las listas enlazadas con respecto a otras estructuras de datos. Además de las variantes comentadas anteriormente, a continuación se presentan dos formas sencillas de mejorar el tiempo de búsqueda.
En una lista desordenada, una heurística simple para disminuir el tiempo de búsqueda promedio es la heurística de mover al frente , que simplemente mueve un elemento al principio de la lista una vez que se lo encuentra. Este esquema, útil para crear cachés simples, garantiza que los elementos utilizados más recientemente también sean los más rápidos de encontrar nuevamente.
Otro enfoque común es " indexar " una lista enlazada utilizando una estructura de datos externa más eficiente. Por ejemplo, se puede construir un árbol rojo-negro o una tabla hash cuyos elementos sean referencias a los nodos de la lista enlazada. Se pueden construir múltiples índices de este tipo en una sola lista. La desventaja es que estos índices pueden necesitar ser actualizados cada vez que se agrega o elimina un nodo (o al menos, antes de que ese índice se vuelva a utilizar).
Una lista de acceso aleatorio es una lista con soporte para acceso aleatorio rápido para leer o modificar cualquier elemento en la lista. [9] Una posible implementación es una lista de acceso aleatorio binaria sesgada que utiliza el sistema de numeración binario sesgado , que involucra una lista de árboles con propiedades especiales; esto permite operaciones de cabeza/contras de tiempo constante en el peor de los casos y acceso aleatorio en tiempo logarítmico en el peor de los casos a un elemento por índice. [9] Las listas de acceso aleatorio se pueden implementar como estructuras de datos persistentes . [9]
Las listas de acceso aleatorio pueden considerarse como listas enlazadas inmutables, ya que también admiten las mismas operaciones de cabeza y cola O(1). [9]
Una extensión simple de las listas de acceso aleatorio es la min-lista, que proporciona una operación adicional que produce el elemento mínimo en toda la lista en tiempo constante (sin [ aclaración necesaria ] complejidades de mutación). [9]
Tanto las pilas como las colas a menudo se implementan utilizando listas enlazadas y simplemente restringen el tipo de operaciones que se admiten.
La lista de saltos es una lista enlazada ampliada con capas de punteros para saltar rápidamente sobre una gran cantidad de elementos y luego descender a la siguiente capa. Este proceso continúa hasta la capa inferior, que es la lista real.
Un árbol binario puede considerarse como un tipo de lista enlazada en la que los elementos son, a su vez, listas enlazadas de la misma naturaleza. El resultado es que cada nodo puede incluir una referencia al primer nodo de una o dos listas enlazadas más, que, junto con su contenido, forman los subárboles que se encuentran debajo de ese nodo.
Una lista enlazada desenrollada es una lista enlazada en la que cada nodo contiene una matriz de valores de datos. Esto mejora el rendimiento de la memoria caché , ya que hay más elementos de la lista contiguos en la memoria, y reduce la sobrecarga de memoria, ya que es necesario almacenar menos metadatos para cada elemento de la lista.
Una tabla hash puede utilizar listas enlazadas para almacenar las cadenas de elementos que tienen la misma posición en la tabla hash.
Un montón comparte algunas de las propiedades de ordenación de una lista enlazada, pero casi siempre se implementa mediante una matriz. En lugar de referencias de un nodo a otro, los índices de datos anteriores y siguientes se calculan utilizando el índice de los datos actuales.
Una lista autoorganizada reorganiza sus nodos basándose en alguna heurística que reduce los tiempos de búsqueda para la recuperación de datos al mantener los nodos a los que se accede comúnmente al principio de la lista.
{{cite book}}: |work=ignorado ( ayuda )