Lista enlazada

Una lista enlazada es una secuencia de nodos que contienen dos campos: un valor entero y un enlace al próximo nodo. El último nodo está ligado a un terminante usado para significar el final de la lista.

En informática, una lista enlazada es una colección lineal de elementos de datos cuyo orden no viene dado 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 de la secuencia. Esta estructura permite la inserción o eliminación eficiente de elementos desde 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. Un inconveniente de las listas enlazadas es que el tiempo de acceso es lineal (y difícil de canalizar). Un 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 vinculadas.

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 vinculada como base.

El principal beneficio de una lista enlazada sobre una matriz convencional es que los elementos de la lista se pueden insertar o eliminar fácilmente sin reasignación o reorganización de toda la estructura porque los elementos de datos no necesitan almacenarse contiguamente en la memoria o en el disco, mientras se reestructura 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 manteniendo el enlace anterior al enlace que se agrega o elimina en la memoria durante el recorrido de la lista.

Por otro lado, dado que las listas enlazadas simples por sí mismas no permiten el 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 determinado datum, o ubicar el lugar donde se debe insertar un nuevo nodo, puede requerir iterar a través de la mayoría o todos los elementos de la lista.

Historia

Las listas vinculadas fueron desarrolladas entre 1955 y 1956 por Allen Newell, Cliff Shaw y Herbert A. Simon en RAND Corporation como la estructura de datos principal para su lenguaje de procesamiento de información. Los autores utilizaron IPL para desarrollar varios de los primeros programas de inteligencia artificial, incluida la Máquina de teoría lógica, el Solucionador general de problemas y un programa de ajedrez por computadora. Los informes sobre su trabajo aparecieron en IRE Transactions on Information Theory en 1956, y varias actas de conferencias de 1957 a 1959, incluidas las Actas de la Western Joint Computer Conference en 1957 y 1958, y Information Processing (Actas de la primera Conferencia Internacional de la UNESCO sobre Procesamiento de Información).) en 1959. El diagrama ahora clásico que consta de bloques que representan nodos de lista con flechas que apuntan a nodos de lista sucesivos aparece en "Programación de la máquina de teoría lógica" por Newell y Shaw en Proc. WJCC, febrero de 1957. Newell y Simon fueron reconocidos con el premio ACM Turing 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 traducción mecánica" apareció en Mechanical Translation en 1958.

Otra aparición temprana de las listas enlazadas fue la de Hans Peter Luhn, quien escribió un memorándum interno de IBM en enero de 1953 que sugería el uso de listas enlazadas en tablas hash encadenadas.

LISP, que significa procesador de listas, 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 "Recursive Functions of Symbolic Expressions and Su Cálculo por Máquina, Parte I". Una de las principales estructuras de datos de LISP es la lista enlazada.

A principios de la década de 1960, la utilidad tanto de las listas vinculadas como de los lenguajes que utilizan estas estructuras como su principal representación de datos 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, que resumió las ventajas del enfoque de lista enlazada. Un artículo de revisión posterior, "Una comparación de lenguajes informáticos de procesamiento de listas" de Bobrow y Raphael, apareció en Comunicaciones de la ACM en abril de 1964.

Varios sistemas operativos desarrollados por Technical Systems Consultants (originalmente de West Lafayette Indiana y luego de Chapel Hill, Carolina del Norte) usaban listas enlazadas individualmente como estructuras de archivos. Una entrada de directorio apuntaba al primer sector de un archivo, y las porciones subsiguientes del archivo se ubicaban mediante punteros transversales. Los sistemas que utilizan esta técnica incluyen Flex (para la CPU Motorola 6800), mini-Flex (la misma CPU) y Flex9 (para la CPU Motorola 6809). Una variante desarrollada por TSC para y comercializada por Smoke Signal Broadcasting en California, usaba listas doblemente enlazadas de la misma manera.

El sistema operativo TSS/360, desarrollado por IBM para las máquinas System 360/370, utilizó una lista de doble enlace para su catálogo de sistemas de archivos. La estructura de directorios era similar a Unix, donde un directorio podía contener archivos y otros directorios y extenderse a cualquier profundidad.

Conceptos básicos y nomenclatura

Cada registro de una lista enlazada a menudo se denomina 'elemento' o 'nodo'.

El campo de cada nodo que contiene la dirección del siguiente nodo suele denominarse 'siguiente enlace' o 'siguiente puntero'. Los campos restantes se conocen como "datos", "información", "valor", "carga" o "carga útil". 39; los campos.

La 'cabeza' de una lista es su primer nodo. La 'cola' de una lista puede referirse al resto de la lista después del encabezado o al último nodo de la lista. En Lisp y algunos lenguajes derivados, el siguiente nodo puede llamarse 'cdr' (pronunciado could-er) de la lista, mientras que la carga útil del nodo principal puede denominarse 'coche'.

Lista de enlaces individuales

Las listas enlazadas individualmente contienen nodos que tienen un 'valor' campo así como 'siguiente' campo, que apunta al siguiente nodo en la línea de nodos. Las operaciones que se pueden realizar en listas enlazadas individualmente incluyen inserción, eliminación y recorrido.

Una lista enlazada, cuyos nodos contienen dos campos: un valor entero y un enlace al próximo nodo

El siguiente código muestra cómo agregar un nuevo nodo con el "valor" al final de una lista enlazada individualmente:

nodos addNode()nodos cabeza, int valor) {} nodos tempestad, p; // declarar dos nodos temp y p tempestad = crear Node(); // asumir crear El nodo crea un nodo nuevo con valor = 0 y siguiente apuntando a NULL. tempestad-valor = valor; // añadir elemento a una parte de valor del nodo si ()cabeza == NULL) {} cabeza = tempestad; // cuando la lista enlazada está vacía } más {} p = cabeza; // asignar cabeza a p  mientras ()p-siguiente ! NULL) {} p = p-siguiente; // atravesar la lista hasta p es el último nodo. El último nodo siempre apunta a NULL. } p-siguiente = tempestad; // Apunte el último nodo anterior al nuevo nodo creado. } retorno cabeza;}

Lista doblemente enlazada

En una 'lista doblemente enlazada', cada nodo contiene, además del enlace del siguiente nodo, un segundo campo de enlace que apunta al 'anterior' nodo en la secuencia. Los dos enlaces pueden llamarse 'adelante('s') y 'atrás', o 'siguiente' y 'anterior'('anterior').

Una lista doblemente ligada cuyos nodos contienen tres campos: un valor entero, el enlace hacia el próximo nodo, y el enlace hacia atrás al nodo anterior

Una técnica conocida como enlace XOR permite implementar una lista doblemente enlazada utilizando un solo 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, es posible que no esté disponible en algunos lenguajes de alto nivel.

Muchos sistemas operativos modernos usan listas doblemente enlazadas para mantener referencias a procesos activos, subprocesos y otros objetos dinámicos. Una estrategia común de los rootkits para evadir la detección es desvincularse de estas listas.

Multiplicar lista enlazada

En una 'lista de enlaces múltiples', cada nodo contiene dos o más campos de enlace, y cada campo se usa para conectar el mismo conjunto de registros de datos en un orden diferente del mismo conjunto (por ejemplo, por nombre, por departamento, por fecha de nacimiento, etc.). Si bien las listas doblemente enlazadas pueden verse como casos especiales de listas de enlaces múltiples, 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.

Lista enlazada circular

En el último nodo de una lista, el campo de enlace a menudo contiene una referencia nula, se usa un valor especial para indicar la falta de más nodos. 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 'enlazado circularmente'; de lo contrario, se dice que está 'abierto' o 'lineal'. Es una lista donde el último puntero apunta al primer nodo.

Una lista de enlaces circulares

En el caso de una lista circular doblemente enlazada, el primer nodo también apunta al último nodo de la lista.

Nodos centinela

En algunas implementaciones, un 'centinela' o 'ficticio' El nodo se puede agregar 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 enlaces se puedan desreferenciar de manera segura y que cada lista (incluso una que no contenga elementos de datos) siempre tenga un "primero" y "último" nodo.

Listas vacías

Una lista vacía es una lista que no contiene registros de datos. Esto suele ser lo mismo que decir que tiene cero nodos. Si se utilizan ganglios centinela, generalmente se dice que la lista está vacía cuando solo tiene ganglios centinela.

Enlace hash

Los campos de enlace no necesitan ser físicamente parte de los nodos. Si los registros de datos se almacenan en una matriz y sus índices hacen referencia a ellos, el campo de enlace puede almacenarse en una matriz separada con los mismos índices que los registros de datos.

Manejadores de lista

Dado que una referencia al primer nodo da acceso a toda la lista, esa referencia a menudo se denomina 'dirección', 'puntero' o 'controlador' de la lista Los algoritmos que manipulan listas enlazadas normalmente obtienen dichos identificadores en las listas de entrada y devuelven los identificadores a las listas resultantes. De hecho, en el contexto de dichos algoritmos, la palabra "lista" a menudo significa "identificador de lista". En algunas situaciones, sin embargo, puede ser conveniente hacer referencia a una lista mediante un identificador que consta de dos enlaces, apuntando a su primer y último nodo.

Combinando alternativas

Las alternativas enumeradas anteriormente se pueden combinar arbitrariamente en casi todas las formas, por lo que se pueden tener listas circulares con enlaces dobles sin centinelas, listas circulares con enlaces simples con centinelas, etc.

Compensaciones

Al igual que con la mayoría de las opciones en programación y diseño de computadoras, ningún método se adapta bien a todas las circunstancias. Una estructura de datos de lista enlazada podría funcionar bien en un caso, pero causar problemas en otro. Esta es una lista de algunas de las compensaciones comunes que involucran estructuras de listas enlazadas.

Listas enlazadas frente a matrices dinámicas

Una matriz dinámica es una estructura de datos que asigna todos los elementos de forma contigua en la memoria y mantiene un recuento del número actual de elementos. Si se excede el espacio reservado para la matriz dinámica, se reasigna y (posiblemente) se copia, lo cual es una operación costosa.

Las listas vinculadas 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 este la 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 al marcar de alguna manera su ranura como 'vacante', esto provoca una fragmentación que impide el rendimiento de la iteración.

Además, se pueden insertar arbitrariamente muchos elementos en una lista enlazada, limitada ú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 tal vez ni siquiera sea posible 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 por reasignación aún se amortizaría O(1). Esto ayuda a agregar elementos al final de la matriz, pero insertar (o eliminar) posiciones intermedias aún conlleva costos prohibitivos debido a que los datos se mueven para mantener la contigüidad. Es posible que también se deba cambiar el tamaño de una matriz de la que se eliminan muchos elementos para evitar desperdiciar demasiado espacio.

Por otro lado, las matrices dinámicas (así como las estructuras de datos de matriz de tamaño fijo) permiten el acceso aleatorio en tiempo constante, mientras que las listas vinculadas solo permiten el acceso secuencial a los elementos. Las listas enlazadas individualmente, de hecho, se pueden recorrer fácilmente en una sola dirección. Esto hace que las listas vinculadas no sean adecuadas para aplicaciones en las que es útil buscar rápidamente un elemento por su índice, como heapsort. El acceso secuencial en matrices y matrices dinámicas también es más rápido que en listas vinculadas 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 que se necesita para las referencias, lo que a menudo las hace poco prácticas para las listas de elementos de datos pequeños, como caracteres o valores booleanos, porque la sobrecarga de almacenamiento para los enlaces puede exceder por un factor de dos o más el tamaño de los datos. Por el contrario, una matriz dinámica requiere solo el espacio para los datos en sí (y una cantidad muy pequeña de datos de control). También puede ser lento, y con un asignador ingenuo, un desperdicio, asignar memoria por separado para cada elemento nuevo, un problema que generalmente se resuelve utilizando grupos de memoria.

Algunas soluciones híbridas intentan combinar las ventajas de las dos representaciones. Las listas vinculadas 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, al reemplazar las referencias con los datos reales a los que se hace referencia, lo que se extiende más allá del final del registro de referencia.

Un buen ejemplo que destaca los pros y los contras del uso de matrices dinámicas frente a las listas vinculadas es implementar un programa que resuelva el problema de Josephus. El problema de Josefo es un método de elección que funciona haciendo que un grupo de personas se pare en un círculo. Comenzando en una persona predeterminada, uno puede contar alrededor del círculo n veces. Una vez que se llega a la nésima persona, se debe eliminar 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 las elecciones. Esto muestra las fortalezas y debilidades de una lista enlazada frente a una matriz dinámica, porque si las personas se ven como nodos conectados en una lista enlazada circular, muestra la facilidad con la que la lista enlazada puede eliminar nodos (ya que solo tiene que reorganizar los enlaces a los diferentes nodos). Sin embargo, la lista enlazada será deficiente para encontrar a la siguiente persona a eliminar y deberá buscar en la lista hasta que encuentre a esa persona. Una matriz dinámica, por otro lado, será deficiente para eliminar nodos (o elementos) ya que no puede eliminar un nodo sin desplazar individualmente todos los elementos de la lista uno por uno. Sin embargo, es excepcionalmente fácil encontrar a la nésima persona en el círculo al hacer referencia directa a ellos 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 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 sobrecarga de espacio similares a los de una lista enlazada, mientras que permite una indexación mucho más eficiente, tomando el tiempo 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 de árboles para mantener el equilibrio. Existen esquemas para que los árboles se mantengan automáticamente en un estado de equilibrio: árboles AVL o árboles rojo-negro.

Listas lineales enlazadas individualmente frente a otras listas

Mientras que las listas circulares y doblemente enlazadas tienen ventajas sobre las listas lineales enlazadas individualmente, las listas lineales ofrecen algunas ventajas que las hacen preferibles en algunas situaciones.

Una lista lineal enlazada individualmente es una estructura de datos recursiva, porque contiene un puntero a un objeto más pequeño del mismo tipo. Por esa razón, muchas operaciones en listas lineales enlazadas individualmente (como fusionar dos listas o enumerar los elementos en orden inverso) a menudo tienen algoritmos recursivos muy simples, mucho más simples que cualquier solución que use comandos iterativos. Si bien esas soluciones recursivas se pueden adaptar para listas doblemente vinculadas y circularmente vinculadas, los procedimientos generalmente necesitan argumentos adicionales y casos base más complicados.

Las listas lineales con enlaces simples también permiten compartir la cola, el uso de una parte final común de una sublista como la parte 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 finales se pueden compartir entre listas no circulares vinculadas individualmente. Se puede usar el mismo nodo centinela final para todas tales listas. En Lisp, por ejemplo, cada lista adecuada termina con un enlace a un nodo especial, denotado por nil o (), cuyo CAR y < Los enlaces code>CDR apuntan a sí mismos. Por lo tanto, un procedimiento Lisp puede tomar con seguridad el CAR o CDR de cualquier lista.

Las ventajas de las variantes sofisticadas a menudo se limitan a la complejidad de los algoritmos, no a su eficiencia. Una lista circular, en particular, por lo general puede ser emulada por una lista lineal junto con dos variables que apuntan al primer y último nodo, sin costo adicional.

Doble enlace frente a enlace simple

Las listas de enlaces dobles requieren más espacio por nodo (a menos que se use un enlace 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 con solo la dirección de ese nodo. Para hacer lo mismo en una lista enlazada individualmente, 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 la cola y no pueden usarse como estructuras de datos persistentes.

Enlazado circularmente frente a enlazado linealmente

Una lista enlazada circularmente puede ser una opción natural para representar matrices que son naturalmente circulares, p. las esquinas de un polígono, un conjunto de búferes que se utilizan y liberan en orden FIFO (primero en entrar, primero en salir), o un conjunto de procesos que se deben compartir en el tiempo en orden rotatorio. En estas aplicaciones, un puntero a cualquier nodo sirve como identificador de toda la lista.

Con una lista circular, un puntero al último nodo brinda fácil acceso 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 con 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 el contenido de los campos de enlace de esos dos nodos. Aplicar la misma operación a dos nodos cualesquiera en dos listas distintas une las dos listas en una. Esta propiedad simplifica enormemente algunos algoritmos y estructuras de datos, como quad-edge y face-edge.

La representación más simple para 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 nulo para denotar una lista lineal vacía es más natural y, a menudo, crea menos casos especiales.

Para algunas aplicaciones, puede ser útil usar listas enlazadas individualmente que pueden variar entre ser circulares y lineales, o incluso circulares con un segmento inicial lineal. Los algoritmos para buscar u operar con ellos deben tomar precauciones para evitar entrar accidentalmente en un bucle sin fin. Un método bien conocido es hacer que un segundo puntero recorra la lista a la mitad o al doble de la velocidad, y si ambos punteros se encuentran en el mismo nodo, sabrá que encontró un ciclo.

Uso de ganglios centinela

El nodo centinela puede simplificar ciertas operaciones de lista al garantizar que existan los nodos anterior o siguiente 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 al final de la lista. Por ejemplo, al escanear la lista en busca de un nodo con un valor determinado x, establecer el campo de datos del centinela en x hace que sea innecesario probar el valor final. of-list dentro del bucle. Otro ejemplo es la fusión de dos listas ordenadas: si sus centinelas tienen campos de datos establecidos en +∞, la elección del siguiente nodo de salida no necesita un manejo especial para listas vacías.

Sin embargo, los nodos centinela ocupan espacio adicional (especialmente en aplicaciones que usan 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 usa simplemente para simular una lista lineal, se puede evitar parte de esta complejidad agregando un solo nodo centinela a cada lista, entre el último y el primer nodo de datos. Con esta convención, una lista vacía consiste solo en el nodo centinela, que se apunta a sí mismo a través del enlace del siguiente nodo. El identificador de la lista debería ser un puntero al último nodo de datos, antes del centinela, si la lista no está vacía; o al propio centinela, si la lista está vacía.

Se puede usar el mismo truco para simplificar el manejo de una lista lineal doblemente enlazada, convirtiéndola en una lista circular doblemente enlazada con un solo nodo centinela. Sin embargo, en este caso, el identificador debe ser un único puntero al nodo ficticio en sí.

Operaciones de listas enlazadas

Al manipular listas enlazadas en el lugar, se debe tener cuidado de no usar valores que haya invalidado en asignaciones anteriores. Esto hace que los algoritmos para insertar o eliminar nodos de listas enlazadas sean algo sutiles. Esta sección brinda pseudocódigo para agregar o eliminar nodos de listas vinculadas de forma simple, doble y circular en el lugar. En todo momento usaremos null para referirnos a un marcador o centinela de final de lista, que se puede implementar de varias maneras.

Listas enlazadas linealmente

Listas enlazadas individualmente

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 null para una lista vacía.

récord Node{}
datos; // Los datos que se almacenan en el nodo Node siguiente // Una referencia al próximo nodo, nulo para el último nodo}

récord Lista{}
 Node primero Node // señala el primer nodo de lista; null for empty list}

El recorrido de una lista enlazada individualmente es simple, comenzando en el primer nodo y siguiendo cada enlace siguiente hasta llegar al final:

nodo:= lista.
mientras nodo nulo
 (Haz algo con node.data)nodo:= nodo.next

El siguiente código inserta un nodo después de un nodo existente en una lista enlazada individualmente. El diagrama muestra cómo funciona. La inserción de un nodo antes de uno existente no se puede hacer directamente; en cambio, uno debe realizar un seguimiento del nodo anterior e insertar un nodo después.

Diagrama de insertar un nodo en una lista enlazada

función insertarDespués(Node nodo, Node newNode) // insertar nuevoNodo después del nodonewNode.next:= node.next
nodo.next:= newNode

La inserción al principio de la lista requiere una función separada. Esto requiere actualizar firstNode.

función insertarComenzar(Lista lista, Node newNode) // insertar nodo antes del primer nodo actualnewNode.next:= list.firstNode
list.firstNode:= newNode

Del mismo modo, tenemos funciones para eliminar el nodo después de un nodo determinado y para eliminar un nodo del principio de la lista. El diagrama demuestra lo primero. Para encontrar y eliminar un nodo en particular, se debe volver a realizar un seguimiento del elemento anterior.

Diagrama de borrar un nodo de una lista enlazada

función RetiradaNode nodo) // eliminar el nodo pasado esteobsoletoNodo:= nodo.next
node.next:= node.next.next
destruir obsoleto Node

función quitarComenzar(Lista lista) // quitar el primer nodoobsoleteNode:= list.firstNode
list.firstNode:= list.firstNode.next // punto pasado nodo eliminadodestruir obsoleto Node

Observe que removeBeginning() establece list.firstNode en null al eliminar el último nodo de la lista.

Dado que no podemos iterar hacia atrás, las operaciones eficientes insertBefore o removeBefore no son posibles. Insertar en una lista antes de un nodo específico requiere atravesar la lista, lo que en el peor de los casos tendría un tiempo de ejecución de O(n).

Pasar una lista vinculada a otra puede ser ineficiente a menos que una referencia a la cola se mantenga como parte de la estructura de la Lista, porque debemos atravesar toda la primera lista para encontrar la cola, y luego adjuntar la segunda lista a esto. Así, si dos listas linealmente vinculadas son cada una de longitud ${displaystyle n}$, lista pendiente tiene complejidad de tiempo asintotica ${displaystyle O(n)}$. En la familia Lisp de idiomas, lista pendiente es proporcionada por la append procedimiento.

Muchos de los casos especiales de operaciones de listas enlazadas se pueden eliminar al incluir un elemento ficticio al principio de la lista. Esto asegura que no haya casos especiales para el comienzo de la lista y hace que tanto insertBeginning() como removeBeginning() sean innecesarios. En este caso, los primeros datos útiles de la lista se encontrarán en list.firstNode.next.

Lista enlazada circularmente

En una lista enlazada circularmente, todos los nodos están enlazados en un círculo continuo, sin usar null. Para listas con un anverso y un reverso (como una cola), se almacena una referencia al último nodo de la lista. El nodo siguiente después del último nodo es el primer nodo. Los elementos se pueden agregar al final de la lista y eliminar 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 lastNode< /i> variable que apunta a algún nodo en la lista o es null si está vacío; usamos tal lastNode 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.

Algoritmos

Suponiendo que algúnNodo es algún nodo en una lista circular no vacía enlazada individualmente, este código itera a través de esa lista comenzando con algúnNodo:

función iterate(someNode)
 si algunosNodo ‹ nulonodo:= algunos Node
 doHaz algo con nodo. valor
nodo:= nodo.next
 mientras nodo י some Node

Observe que la prueba "while node ≠ someNode" debe estar al final del bucle. Si la prueba se movía al comienzo del ciclo, el procedimiento fallaría siempre que la lista tuviera un solo nodo.

Esta función inserta un nodo "newNode" en una lista enlazada circular después de un nodo dado "nodo". Si "nodo" es nulo, asume que la lista está vacía.

función insertarDespués(Node nodo, Node newNode)
 si nodo = nulo // asumir lista está vacía
newNode.next:= newNode
 másnewNode.next:= node.next
nodo.next:= newNode
actualización lastNode variable si es necesario

Suponga que "L" es una variable que apunta al último nodo de una lista circular enlazada (o nula si la lista está vacía). Para agregar "newNode" al final de la lista, uno puede hacer

insert After(L, newNode)
L:= newNode

Para insertar "nuevoNodo" al comienzo de la lista, uno puede hacer

insert After(L, newNode)
si L = nuloL:= newNode

Esta función inserta un valor "newVal" antes de un nodo dado "nodo" en tiempo O(1). Creamos un nuevo nodo entre "node" y el siguiente nodo, y luego coloque el valor de "nodo" en ese nuevo nodo y coloque "newVal" en "nodo". Por lo tanto, una lista enlazada circularmente con solo una variable firstNode puede insertarse al frente y atrás en tiempo O(1).

función insertarAntes(()Node nodo, nuevo valor)
 si nodo = nulo // asumir lista está vacía
newNode:= nuevo Node(data:=newVal, next:=newNode)
 másnewNode:= nuevo Node(datos:=node.data, siguiente:=node.next)
node.data:= nuevo Val
nodo.next:= newNode
actualización primero Node variable 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 los datos del siguiente nodo en el nodo y luego establece el puntero siguiente del nodo para saltarse el siguiente nodo.

función quitar(Node nodo)
 si nodo nulo y tamaño de la lista 1
RetiradaData:= nodo.data
node.data:= node.next.data
node.next = node.next.next
 retorno Retirada Datos

Listas enlazadas utilizando matrices de nodos

Los idiomas que no admiten ningún tipo de referencia aún pueden crear enlaces reemplazando punteros con índices de matriz. El enfoque es mantener una matriz de registros, donde cada registro tiene campos enteros que indican el índice del siguiente (y posiblemente anterior) nodo en la matriz. No es necesario utilizar todos los nodos de la matriz. Si tampoco se admiten registros, a menudo se pueden usar matrices paralelas en su lugar.

Como ejemplo, considere el siguiente registro de lista enlazada que utiliza matrices en lugar de punteros:

récord Entrada {}
 entero siguiente; // índice de la siguiente entrada en array entero prev; // entrada anterior (si está doble enlace) cuerda Nombre;
 real equilibrio;
}

Se puede construir una lista enlazada creando una matriz de estas estructuras y una variable entera para almacenar el índice del primer elemento.

entero lista Head
Entrada Documentos[1000]

Los enlaces entre elementos se forman colocando el índice de matriz de la celda siguiente (o anterior) en el campo Siguiente o Anterior dentro de un elemento determinado. Por ejemplo:

En el ejemplo anterior, ListHead se 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 variable entera ListFree, se podría crear una lista libre para realizar un seguimiento de las celdas disponibles. Si todas las entradas están en uso, el tamaño de la matriz deberá aumentarse o algunos elementos deberán eliminarse antes de que las nuevas entradas puedan almacenarse en la lista.

El siguiente código recorrería la lista y mostraría los nombres y el saldo de la cuenta:

i:= lista Head
mientras ≥ 0 // bucle a través de la listaprint i, Records[i].name, Records[i].balance // entrada de impresióni:= Records[i].next

Cuando se enfrenta a una elección, las ventajas de este enfoque incluyen:

• La lista enlazada es relocatable, lo que significa que se puede mover en memoria a voluntad, y también puede ser rápidamente y directamente serializado para el almacenamiento en disco o transferencia a través de una red.
• Especialmente para una pequeña lista, los índices de array pueden ocupar significativamente menos espacio que un puntero completo en muchas arquitecturas.
• Localidad de referencia se puede mejorar manteniendo los nodos juntos en memoria y reorganizándolos periódicamente, aunque esto también se puede hacer en una tienda general.
• Los aleatores de memoria dinámica ingenuos pueden producir una cantidad excesiva de almacenamiento de sobrecabeza para cada nodo asignado; casi ninguna asignación se incurre por nodo en este enfoque.
• Aprovechar una entrada de un array pre-alocado es más rápido que usar la asignación dinámica de memoria para cada nodo, ya que la asignación dinámica de memoria normalmente requiere una búsqueda de un bloque de memoria libre del tamaño deseado.

Sin embargo, este enfoque tiene una desventaja principal: crea y administra un espacio de memoria privado para sus nodos. Esto conduce a los siguientes problemas:

• Aumenta la complejidad de la aplicación.
• Crecer una gran matriz cuando está llena puede ser difícil o imposible, mientras que encontrar espacio para un nuevo nodo de lista vinculado en una gran piscina de memoria general puede ser más fácil.
• Agregar elementos a un array dinámico ocasionalmente (cuando está lleno) tomar inesperadamente linear (O(n))) en lugar de tiempo constante (aunque sigue siendo una constante amortizada).
• Usar un pool de memoria general deja más memoria para otros datos si la lista es más pequeña de lo esperado o si muchos nodos son liberados.

Por estas razones, este enfoque se usa principalmente para lenguajes que no admiten la asignación de memoria dinámica. Estas desventajas también se mitigan si se conoce el tamaño máximo de la lista en el momento en que se crea la matriz.

Soporte de idiomas

Muchos lenguajes de programación, como Lisp y Scheme, tienen integradas listas vinculadas individualmente. 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 celdas contras se pueden usar para construir otras estructuras de datos, este es su propósito principal.

En los idiomas que admiten plantillas o tipos de datos abstractos, las plantillas o ADT de listas vinculadas están disponibles para crear listas vinculadas. En otros idiomas, las listas enlazadas normalmente se construyen utilizando referencias junto con registros.

Almacenamiento interno y externo

Al construir una lista enlazada, uno se enfrenta a la elección de almacenar los datos de la lista directamente en los nodos de la lista enlazada, llamados almacenamiento interno, o simplemente almacenar una referencia a la 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 administración de la memoria para la lista (sus datos se asignan y desasignan al mismo tiempo que los nodos de la lista).

El almacenamiento externo, por otro lado, tiene la ventaja de ser más genérico, ya que se puede usar la misma estructura de datos y código de máquina para una lista enlazada sin importar el tamaño de los datos. También facilita colocar los mismos datos en varias listas vinculadas. Aunque con el almacenamiento interno se pueden colocar los mismos datos en varias listas al incluir varias referencias siguientes en la estructura de datos del nodo, entonces sería necesario crear rutinas separadas para agregar o eliminar celdas en función de cada campo. Es posible crear listas vinculadas adicionales de elementos que utilicen almacenamiento interno mediante el uso de almacenamiento externo y hacer que las celdas de las listas vinculadas adicionales almacenen referencias a los nodos de la lista vinculada que contiene los datos.

En general, si es necesario incluir un conjunto de estructuras de datos en listas vinculadas, el mejor enfoque es el almacenamiento externo. Si es necesario incluir un conjunto de estructuras de datos en una sola lista vinculada, entonces el almacenamiento interno es ligeramente mejor, a menos que esté disponible un paquete genérico de listas vinculadas que use almacenamiento externo. Del mismo modo, si se van a incluir diferentes conjuntos de datos que se pueden almacenar en la misma estructura de datos en una sola lista enlazada, entonces el almacenamiento interno estaría bien.

Otro enfoque que se puede usar con algunos idiomas implica tener diferentes estructuras de datos, pero todos tienen los campos iniciales, incluido el siguiente (y anterior si la lista tiene doble enlace) Referencias en el mismo lugar. 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 contenido en la parte superior (comienzo) de las estructuras. Luego se pueden crear rutinas genéricas que usen la estructura mínima para realizar operaciones de tipo lista enlazada, pero luego las rutinas separadas pueden manejar los datos específicos. Este enfoque se usa a menudo en las rutinas de análisis de mensajes, donde se reciben varios tipos de mensajes, pero todos comienzan con el mismo conjunto de campos, que generalmente incluye 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. El campo de tipo de mensaje se usa luego para llamar a la rutina correcta para procesar el tipo específico de mensaje.

Ejemplo de almacenamiento interno y externo

Suponga que desea crear una lista vinculada de familias y sus miembros. Usando el almacenamiento interno, la estructura podría tener el siguiente aspecto:

récord miembro {} // miembro de una familia miembro siguiente;
 cuerda primero Nombre;
 entero edad;
}
récord familia {} // la propia familia familia siguiente;
 cuerda LastName;
 cuerda dirección;
 miembro miembros // jefe de lista de miembros de esta familia}

Para imprimir una lista completa de las familias y sus miembros que utilizan el almacenamiento interno, podríamos escribir:

aFamilia:= Familia // comenzar a la cabeza de la lista de familiasmientras aFamilia nulo // bucle a través de la lista de familiasinformación sobre la familia
aMember:= aFamily.members // conseguir jefe de lista de los miembros de esta familia mientras aMember √ nulo // bucle a través de la lista de miembrosimprimir información sobre el miembro
aMember:= aMember.next
aFamilia:= aFamilia.next

Usando almacenamiento externo, crearíamos las siguientes estructuras:

récord nodos {} / Estructura de enlace genérica nodos siguiente;
 puntero datos // puntero genérico para datos en nodo}
récord miembro {} // estructura para miembro de la familia cuerda primero Nombre;
 entero Edad
}
récord familia {} // estructura para la familia cuerda LastName;
 cuerda dirección;
 nodos miembros // jefe de lista de miembros de esta familia}

Para imprimir una lista completa de familias y sus miembros usando almacenamiento externo, podríamos escribir:

node:= Familias // comenzar a la cabeza de la lista de familiasmientras famNode ل nulo // bucle a través de la lista de familiasaFamilia:= (familia) famNode.data // Extraer familia del nodoinformación sobre la familia
memNode:= aFamily.members // obtener lista de miembros de la familia mientras memNode ل nulo // bucle a través de la lista de miembrosaMember:= (member)memNode.data // Extracto miembro del nodoimprimir información sobre el miembro
memNode:= memNode.next
famNode:= famNode.next

Tenga en cuenta que cuando se usa 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 vinculadas que utilizan la misma estructura de datos (nodo), y este lenguaje no tiene tipos paramétricos.

Siempre que se conozca el número de familias a las que puede pertenecer un miembro en el momento de la compilación, el almacenamiento interno funciona bien. Sin embargo, si un miembro necesitara ser incluido en un número arbitrario de familias, con el número específico conocido solo en tiempo de ejecución, sería necesario un almacenamiento externo.

Acelerar la búsqueda

Encontrar un elemento específico en una lista enlazada, incluso si está ordenado, normalmente requiere tiempo O(n) (búsqueda lineal). Esta es una de las principales desventajas de las listas enlazadas sobre otras estructuras de datos. Además de las variantes discutidas anteriormente, a continuación hay dos formas simples de mejorar el tiempo de búsqueda.

En una lista desordenada, una heurística simple para disminuir el tiempo promedio de búsqueda es la heurística de mover al frente, que simplemente mueve un elemento al principio de la lista una vez que se encuentra. Este esquema, útil para crear cachés simples, garantiza que los elementos usados más recientemente también sean los más rápidos de encontrar de nuevo.

Otro enfoque común es "indexar" una lista enlazada usando 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 crear múltiples índices de este tipo en una sola lista. La desventaja es que es posible que estos índices deban actualizarse cada vez que se agrega o elimina un nodo (o al menos, antes de que ese índice se use nuevamente).

Listas de acceso aleatorio

Una lista de acceso aleatorio es una lista con soporte para acceso aleatorio rápido para leer o modificar cualquier elemento de la lista. Una posible implementación es una lista de acceso aleatorio binaria sesgada utilizando el sistema numérico binario sesgado, que implica una lista de árboles con propiedades especiales; esto permite operaciones head/cons de tiempo constante en el peor de los casos, y acceso aleatorio de tiempo logarítmico en el peor de los casos a un elemento por índice. Las listas de acceso aleatorio se pueden implementar como estructuras de datos persistentes.

Las listas de acceso aleatorio se pueden ver como listas enlazadas inmutables en el sentido de que también admiten las mismas operaciones de cabeza y cola de O(1).

Una extensión simple de las listas de acceso aleatorio es min-list, que proporciona una operación adicional que produce el elemento mínimo en toda la lista en tiempo constante (sin complejidades de mutación).

Estructuras de datos relacionadas

Tanto las pilas como las colas a menudo se implementan mediante listas vinculadas y simplemente restringen el tipo de operaciones que se admiten.

La lista de omisión es una lista vinculada aumentada 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 verse como un tipo de lista enlazada donde los elementos son 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 que, junto con su contenido, forman los subárboles 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 conduce a un mejor rendimiento de la memoria caché, ya que hay más elementos de la lista contiguos en la memoria y reduce la sobrecarga de la memoria, ya que es necesario almacenar menos metadatos para cada elemento de la lista.

Una tabla hash puede usar listas enlazadas para almacenar las cadenas de elementos que se han convertido en hash en 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 nodo a nodo, los índices de datos anterior y siguiente se calculan utilizando el índice de datos actual.

Una lista autoorganizada reorganiza sus nodos en función de alguna heurística que reduce los tiempos de búsqueda para la recuperación de datos al mantener los nodos de acceso común al principio de la lista.