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 consta de 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 añaden 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 de la lista. Debido a que los nodos están vinculados en serie, acceder a cualquier nodo requiere acceder al nodo anterior de antemano (lo que introduce dificultades en la canalización ). 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 utilizar 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 utilizar 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 de forma contigua en la memoria o en el disco, mientras se reestructura una lista vinculada. 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í solas 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 dato determinado o localizar 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.
Las listas enlazadas fueron desarrolladas en 1955-1956 por Allen Newell , Cliff Shaw y Herbert A. Simon en RAND Corporation y la Universidad Carnegie Mellon como estructura de datos principal para su lenguaje de procesamiento de información (IPL). Los autores utilizaron IPL para desarrollar varios de los primeros programas de inteligencia artificial , incluida la Logic Theory Machine, el General Problem Solver y un programa de ajedrez por computadora. Los informes sobre su trabajo aparecieron en IRE Transactions on Information Theory en 1956, y en varias actas de conferencias de 1957 a 1959, incluidas las Actas de la Western Joint Computer Conference de 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" de Newell y Shaw en Proc. WJCC, febrero de 1957. Newell y Simon fueron reconocidos con el premio ACM Turing en 1975 por haber "hecho 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. [ cita necesaria ]
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 , 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 Their Computation by Machine, Part 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 enlazadas como de los lenguajes que utilizan estas estructuras como representación principal 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 resumía 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 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) utilizaron listas enlazadas individualmente como estructuras de archivos. Una entrada de directorio apuntaba al primer sector de un archivo, y las partes siguientes del archivo se localizaban mediante punteros transversales. Los sistemas que utilizaban esta técnica incluían Flex (para la CPU Motorola 6800 ), mini-Flex (misma CPU) y Flex9 (para la CPU Motorola 6809). Una variante desarrollada por TSC y comercializada por Smoke Signal Broadcasting en California, 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 doble enlazada 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.
Cada registro de una lista enlazada suele denominarse "elemento" o " nodo ".
El campo de cada nodo que contiene la dirección del siguiente nodo suele denominarse 'enlace siguiente' o 'puntero siguiente'. Los campos restantes se conocen como campos de "datos", "información", "valor", "carga" o "carga útil".
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 denominarse ' cdr ' (pronunciado /'kʊd.əɹ/ ) de la lista, mientras que la carga útil del nodo principal puede denominarse 'carro'.
Las listas enlazadas individualmente contienen nodos que tienen un campo de "valor" así como un campo "siguiente", 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.
El siguiente código en lenguaje C demuestra cómo agregar un nuevo nodo con el "valor" al final de una lista enlazada individualmente:
// Cada nodo en una lista vinculada es una estructura. El nodo principal es el primer nodo de la lista.Nodo * addNodeToTail ( Nodo * cabeza , valor int ) { // declara el puntero del Nodo e inicializa para que apunte 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 ( tamaño de * temp ); /// 'malloc' en stdlib. temperatura -> valor = valor ; // Agrega datos al campo de valor del nuevo Nodo. temperatura -> siguiente = NULL ; // inicializa enlaces no válidos a cero. si ( cabeza == NULL ) { cabeza = temperatura ; // Si la lista vinculada está vacía (es decir, el puntero del nodo principal es un puntero nulo), haga que el puntero del nodo principal apunte al nuevo Nodo. } demás { Nodo * p = cabeza ; // Asigne el puntero del nodo principal al puntero de nodo 'p'. mientras ( p -> siguiente ! = NULL ) { p = p -> siguiente ; // Recorre la lista hasta que p sea el último Nodo. El último nodo siempre apunta a NULL. } p -> siguiente = temperatura ; // Hacer que el último Nodo anterior apunte al nuevo Nodo. } cabeza de retorno ; // Devuelve el puntero del nodo principal. }En una 'lista doblemente enlazada', cada nodo contiene, además del enlace del siguiente nodo, un segundo campo de enlace que apunta al nodo "anterior" de la secuencia. Los dos enlaces pueden denominarse 'adelante('s') y 'hacia atrás', o 'siguiente' y 'anterior'('anterior').
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, es posible que no esté 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 para que los rootkits evadan la detección es desvincularse de estas listas. [3]
En una 'lista de enlaces múltiples', cada nodo contiene dos o más campos de enlace, y cada campo 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 verse como un caso especial de una lista múltiplesmente enlazada, el hecho de que 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 a menudo contiene una referencia nula ; se utiliza 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 "enlazada circularmente"; de lo contrario, se dice que es "abierto" o "lineal". Es una lista donde el puntero del último nodo apunta al primer nodo (es decir, el puntero del "siguiente 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 se puedan desreferenciar todos los enlaces 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 tiene cero nodos. Si se utilizan ganglios centinela, normalmente se dice que la lista está vacía cuando solo tiene ganglios centinela.
No es necesario que los campos de enlace formen parte físicamente 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 a menudo se denomina "dirección", "puntero" o "identificador" de la lista. Los algoritmos que manipulan listas enlazadas generalmente obtienen dichos identificadores en las listas de entrada y los devuelven a las listas resultantes. De hecho, en el contexto de tales algoritmos, la palabra "lista" a menudo significa "identificador de lista". En algunas situaciones, sin embargo, 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 enlazadas individualmente con centinelas, etc.
Como ocurre 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 puede 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 vinculadas.
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 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 esto 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 se puede "eliminar" un elemento de una matriz en un tiempo constante marcando de alguna manera su ranura como "vacía", esto provoca una fragmentación que impide la realización de la iteración.
Además, se pueden insertar muchos elementos arbitrariamente 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 reasignar, una operación costosa, que puede que 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 debida a reasignación aún se amortizaría O (1). Esto ayuda a agregar elementos al final de la matriz, pero insertarlos (o eliminarlos) en posiciones intermedias aún conlleva costos prohibitivos debido al movimiento de datos para mantener la contigüidad. Es posible que también sea necesario 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 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 individualmente 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 rápidamente un elemento por su índice, como heapsort . El acceso secuencial a matrices y matrices dinámicas también es más rápido que a 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 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 de los enlaces puede exceder en un factor de dos o más el tamaño de las listas enlazadas. los datos. Por el contrario, una matriz dinámica solo requiere 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 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 enlazadas desenrolladas almacenan varios elementos en cada nodo de la lista, lo que aumenta el rendimiento de la 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 desde el final del registro de referencia.
Un buen ejemplo que resalta los pros y los contras del uso de matrices dinámicas frente a listas enlazadas es la implementación de 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 formen un círculo. A partir de una persona predeterminada, se puede contar alrededor del círculo n veces. Una vez que se llega a la enésima persona, se debe sacarla 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, entonces muestra con qué facilidad la lista enlazada puede eliminar nodos (ya que solo tiene que hacerlo). reorganizar los enlaces a los diferentes nodos). Sin embargo, la lista vinculada no podrá encontrar a la siguiente persona a eliminar y deberá buscar en la lista hasta encontrarla. Una matriz dinámica, por otro lado, será deficiente a la hora de eliminar nodos (o elementos), ya que no puede eliminar un nodo sin desplazar individualmente todos los elementos uno por uno hacia arriba en la lista. Sin embargo, es excepcionalmente fácil encontrar la enésima persona en el círculo haciendo referencia a ella directamente 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 una sobrecarga de espacio similares a los de una lista vinculada, al tiempo que permite una indexación mucho más eficiente, tomando O(log n) tiempo 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 manipulaciones del árbol 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 .
Si bien 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 utilice comandos iterativos . Si bien esas soluciones recursivas se pueden adaptar para listas doblemente enlazadas y enlazadas circularmente, los procedimientos generalmente necesitan argumentos adicionales y casos base más complicados.
Las listas lineales enlazadas individualmente también permiten compartir cola , es decir, el uso de una parte final común de la sublista como parte terminal de dos listas diferentes. En particular, si se agrega un nuevo nodo al principio de una lista, la lista anterior permanece disponible como 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 ganglios centinela finales se pueden compartir entre listas no circulares vinculadas individualmente. Se puede utilizar el mismo ganglio centinela final para cada lista de este tipo. En Lisp , por ejemplo, cada lista adecuada termina con un enlace a un nodo especial, indicado por nilo ().
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, normalmente puede emularse mediante una lista lineal junto con dos variables que apuntan al primer y último nodo, sin coste adicional.
Las listas con doble enlace requieren más espacio por nodo (a menos que se utilice enlace XOR ) y sus operaciones elementales son más caras; pero suelen ser más fáciles de manipular porque permiten un acceso secuencial rápido y sencillo 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 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 cola y no pueden usarse 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 conjunto de buffers que se usan y liberan en orden FIFO ("primero en entrar, primero en salir"), o un conjunto de procesos que deben compartirse en tiempo compartido en orden round-robin . 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. Así, 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 único 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 el quad-edge y el 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 indicar una lista lineal vacía es más natural y suele crear menos casos especiales.
Para algunas aplicaciones, puede resultar útil utilizar listas enlazadas individualmente que pueden variar entre circulares y lineales, o incluso circulares con un segmento inicial lineal. Los algoritmos para buscarlos o operarlos 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 velocidad, y si ambos punteros se encuentran en el mismo nodo, sabrá que encontró un ciclo.
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 utilizar un ganglio 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 dado x , configurar el campo de datos del centinela en x hace que sea innecesario probar el final de la 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 ganglios centinela consumen 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 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 consta únicamente del ganglio centinela, que apunta a sí mismo a través del enlace del siguiente nodo. El identificador de la lista debería entonces 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.
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 puntero único al propio nodo ficticio. [8]
Al manipular listas vinculadas in situ, se debe tener cuidado de no utilizar 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 proporciona pseudocódigo para agregar o eliminar nodos de listas con enlaces simples, dobles y circulares in situ. En todo momento usaremos null para referirnos a un marcador de fin de lista o centinela , que puede implementarse de varias maneras.
Nuestra estructura de datos de nodo tendrá dos campos. También mantenemos una variable firstNode que siempre apunta al primer nodo de la lista, o es nula para una lista vacía.
nodo de registro{ datos; // Los datos se almacenan en el nodo Nodo siguiente // Una referencia [2] al siguiente nodo, nula para el último nodo} lista de registros{ Nodo primerNodo // apunta al primer nodo de la lista; nulo para lista vacía}Recorrer una lista unidireccional es simple, comenzando en el primer nodo y siguiendo cada vínculo siguiente hasta llegar al final:
nodo: = list.firstNode mientras el nodo no sea nulo (haga algo con node.data) nodo := nodo.siguiente
El siguiente código inserta un nodo después de un nodo existente en una lista enlazada individualmente. El diagrama muestra cómo funciona. Insertar un nodo antes de uno existente no se puede hacer directamente; en su lugar, se debe realizar un seguimiento del nodo anterior e insertar un nodo después de él.
función insertarDespués( Nodo nodo, Nodo nuevoNodo) // insertar nuevoNodo después del nodo nuevoNodo.siguiente := nodo.siguiente nodo.siguiente := nuevoNodo
Insertar al principio de la lista requiere una función separada. Esto requiere actualizar firstNode .
función insertarBeginning( Lista lista , Nodo nuevoNodo) // insertar nodo antes del primer nodo actual nuevoNodo.siguiente:= lista.primerNodo lista.primerNodo:= nuevoNodo
De manera similar, tenemos funciones para eliminar el nodo después de un nodo determinado y para eliminar un nodo al principio de la lista. El diagrama demuestra lo primero. Para encontrar y eliminar un nodo en particular, uno debe nuevamente realizar un seguimiento del elemento anterior.
función removeAfter( Nodo nodo) // eliminar el nodo más allá de este Nodoobsoleto:= nodo.siguiente nodo.siguiente := nodo.siguiente.siguiente destruir el 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 el nodo obsoleto
Observe que removeBeginning()se establece list.firstNodeen nullcuando se elimina el último nodo de la lista.
Como no podemos iterar hacia atrás, las operaciones insertBeforeu eficientes removeBeforeno son posibles. Insertar en una lista antes de un nodo específico requiere atravesar la lista, lo que tendría un tiempo de ejecución en el peor de los casos de O(n).
Agregar una lista vinculada 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 agregarle la segunda lista. Por lo tanto, si dos listas enlazadas linealmente tienen cada una una longitud , la lista anexada tiene una complejidad temporal asintótica de . En la familia de idiomas Lisp, el procedimiento proporciona la adición de listas .append
Muchos de los casos especiales de operaciones de listas enlazadas se pueden eliminar incluyendo un elemento ficticio al principio de la lista. Esto asegura que no haya casos especiales para el comienzo de la lista y hace que ambos insertBeginning()sean removeBeginning()innecesarios, es decir, cada elemento o nodo está al lado de otro nodo (incluso el primer nodo está al lado del nodo ficticio). En este caso, los primeros datos útiles de la lista los encontraremos en .list.firstNode.next
En una lista enlazada circularmente, todos los nodos están enlazados en un círculo continuo, sin utilizar nulo. Para listas con un frente y un final (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. Los elementos se pueden agregar al final de la lista y eliminarse del frente en un 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 determinado. 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; Aquí utilizamos un último nodo de este tipo . Esta representación simplifica significativamente agregar y eliminar nodos con una lista no vacía, pero las listas vacías son un caso especial.
Suponiendo que algúnNodo es algún nodo en una lista circular simple enlazada no vacía, este código recorre esa lista comenzando con algúnNodo :
función iterar (algúnNodo) si algúnNodo ≠ nulo nodo := algúnNodo hacer hacer algo con node.value nodo := nodo.siguiente mientras nodo ≠ algúnNodo
Observe que la prueba " while node ≠ someNode" debe estar al final del ciclo. Si la prueba se movía al principio del ciclo, el procedimiento fallaría siempre que la lista tuviera un solo nodo.
Esta función inserta un nodo "newNode" en una lista circular enlazada después de un nodo "nodo" determinado. Si "nodo" es nulo, se supone que la lista está vacía.
función insertAfter( Nodo nodo, Nodo nuevoNodo) si nodo = nulo // asume 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 circular enlazada (o nula si la lista está vacía). Para agregar "newNode" al final de la lista, se puede hacer
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 "nodo" determinado en tiempo O(1). Creamos un nuevo nodo entre "nodo" y el siguiente nodo, luego colocamos el valor de "nodo" en ese nuevo nodo y ponemos "newVal" en "nodo". Por lo tanto, una lista enlazada circularmente enlazada individualmente con solo una variable firstNode puede insertarse al principio y al final en tiempo O(1).
función insertBefore ( nodo nodo , nuevoVal) si nodo = nulo // suponemos que la lista está vacía nuevoNodo := nuevo Nodo(datos:=nuevoVal, siguiente:=nuevoNodo) else nuevoNodo := nuevo Nodo(datos:=nodo.datos, siguiente:=nodo.siguiente) nodo.datos: = nuevoVal 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 al nodo y luego configura el siguiente puntero del nodo para omitir el siguiente nodo.
función eliminar ( nodo nodo ) si nodo ≠ nulo y tamaño de lista> 1 datos eliminados: = nodo.datos nodo.datos := nodo.siguiente.datos nodo.siguiente = nodo.siguiente.siguiente devolver datos eliminados
Los idiomas que no admiten ningún tipo de referencia aún pueden crear enlaces reemplazando punteros con índices de matriz. El enfoque consiste en mantener una matriz de registros , donde cada registro tiene campos de números enteros que indican el índice del siguiente (y posiblemente anterior) nodo de la matriz. No es necesario utilizar todos los nodos de la matriz. Si tampoco se admiten registros, a menudo se pueden utilizar matrices paralelas .
Como ejemplo, considere el siguiente registro de lista enlazada que utiliza matrices en lugar de punteros:
entrada de registro { entero siguiente; // índice de la siguiente entrada en la matriz integer prev; // entrada anterior (si tiene doble enlace) nombre de cadena ; equilibrio real ;}Se puede construir una lista vinculada creando una matriz de estas estructuras y una variable entera para almacenar el índice del primer elemento.
lista de enterosRegistros de entrada de encabezado [1000]
Los vínculos 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, 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 gratuita para realizar un seguimiento de las celdas que están disponibles. Si todas las entradas están en uso, sería necesario aumentar el tamaño de la matriz o 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 // recorre la lista print i, Records[i].name, Records[i].balance // imprime la entrada i := Registros[i].siguiente
Cuando se enfrenta a una elección, las ventajas de este enfoque incluyen:
Sin embargo, este enfoque tiene una desventaja principal: crea y gestiona un espacio de memoria privado para sus nodos. Esto lleva a los siguientes problemas:
Por estos motivos, este enfoque se utiliza 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.
Muchos lenguajes de programación, como Lisp y Scheme , tienen integradas listas enlazadas individualmente. En muchos lenguajes funcionales , estas listas se construyen a partir de nodos, cada uno llamado contras o celda de contras . El cons tiene dos campos: el auto , una referencia a los datos de ese nodo, y el cdr , una referencia al siguiente nodo. Aunque las celdas de contras se pueden utilizar para construir otras estructuras de datos, este es su propósito principal.
En los idiomas que admiten plantillas o tipos de datos abstractos , hay plantillas o ADT de listas vinculadas disponibles para crear listas vinculadas. En otros idiomas, las listas enlazadas normalmente se crean utilizando referencias junto con registros .
Al construir una lista vinculada, uno se enfrenta a la elección de almacenar los datos de la lista directamente en los nodos de la lista vinculada, 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 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 utilizar la misma estructura de datos y código de máquina para una lista vinculada sin importar el tamaño de los datos. También facilita colocar los mismos datos en múltiples listas vinculadas. Aunque con el almacenamiento interno los mismos datos se pueden colocar en varias listas al incluir múltiples referencias siguientes en la estructura de datos del nodo, entonces sería necesario crear rutinas separadas para agregar o eliminar celdas según cada campo. Es posible crear listas vinculadas adicionales de elementos que usan almacenamiento interno utilizando almacenamiento externo y haciendo 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 almacenamiento externo es el mejor enfoque. 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 lista vinculada que utilice almacenamiento externo. Del mismo modo, si se incluyen diferentes conjuntos de datos que se pueden almacenar en la misma estructura de datos en una única lista vinculada, entonces el almacenamiento interno estaría bien.
Otro enfoque que se puede utilizar con algunos lenguajes implica tener diferentes estructuras de datos, pero todas tienen los campos iniciales, incluidas las referencias siguientes (y anteriores si la lista tiene doble enlace) 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 contenidos en la parte superior (principio) de las estructuras. Luego se pueden crear rutinas genéricas que utilizan la estructura mínima para realizar operaciones de tipo lista vinculada, 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 normalmente 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 vinculada de familias y sus miembros. Usando almacenamiento interno, la estructura podría verse como la siguiente:
registrar miembro { // miembro de un familiar siguiente ; cadena nombre; edad entera ;} familia de registros { // la familia misma familia siguiente; cadena apellido; dirección de cadena ; miembros miembros // cabeza de lista de miembros de esta familia}Para imprimir una lista completa de familias y sus miembros usando almacenamiento interno, podríamos escribir:
aFamily := Familias // comienza en la cabeza 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 que aMember ≠ null // recorre la lista de miembros imprimir información sobre el miembro un Miembro := un Miembro.siguiente unaFamilia := unaFamilia.siguiente
Usando almacenamiento externo, crearíamos las siguientes estructuras:
nodo de registro { // nodo de estructura de enlace genérico siguiente; datos del puntero // puntero genérico para datos en el nodo} miembro de registro { // estructura para el miembro de la familia cadena nombre; edad entera} familia de registros { // estructura para la cadena familiar apellido; dirección de cadena ; miembros del nodo // jefe de la lista de miembros de esta familia}Para imprimir una lista completa de familias y sus miembros que utilizan almacenamiento externo, podríamos escribir:
famNode := Familias // 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 // obtiene la lista de miembros de la familia mientras memNode ≠ null // recorre la lista de miembros aMember := (miembro)memNode.data // extrae el miembro del nodo imprimir información sobre el miembro memNode := memNode.siguiente famNode := famNode.siguiente
Tenga en cuenta que cuando se utiliza almacenamiento externo, se necesita un paso adicional para extraer el registro del nodo y convertirlo al 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 usando 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 fuera necesario incluir a un miembro en un número arbitrario de familias y el número específico se conociera sólo en tiempo de ejecución, sería necesario el almacenamiento externo.
Encontrar un elemento específico en una lista vinculada, incluso si está ordenado, normalmente requiere O( n ) tiempo ( búsqueda lineal ). Ésta es una de las principales desventajas de las listas vinculadas sobre 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 promedio de búsqueda es la heurística de pasar 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 nuevamente.
Otro enfoque común es " indexar " una lista vinculada 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 crear varios índices de este tipo en una sola lista. La desventaja es que es posible que sea necesario actualizar estos índices 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 que admite un acceso aleatorio rápido para leer o modificar cualquier elemento de la lista. [9] Una posible implementación es una lista de acceso aleatorio binario sesgado utilizando el sistema numérico binario sesgado , que implica 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 de tiempo logarítmico a un elemento por índice en el peor de los casos. [9] Las listas de acceso aleatorio se pueden implementar como estructuras de datos persistentes . [9]
Las listas de acceso aleatorio pueden verse como listas enlazadas inmutables en el sentido de 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 lista mínima, que proporciona una operación adicional que produce el elemento mínimo en la lista completa en tiempo constante (sin [se necesita aclaración ] complejidades de mutación). [9]
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 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 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 caché , ya que hay más elementos de la lista contiguos en la memoria, y a una menor sobrecarga de memoria, porque 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 tienen el hash en la misma posición en la tabla hash.
Un montón comparte algunas de las propiedades de orden de una lista vinculada, 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 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 web}}: Mantenimiento CS1: copia archivada como título ( enlace ){{cite book}}: |work=ignorado ( ayuda )