Lista enlazada

Las listas enlazadas simples contienen nodos que poseen un campo 'valor' y un campo 'siguiente', que apunta al siguiente nodo en la secuencia. Las operaciones que se pueden realizar en las listas enlazadas simples incluyen la inserción, la eliminación y el recorrido.

El siguiente código en lenguaje C demuestra cómo agregar un nuevo nodo con el "valor" al final de una lista enlazada simple:

#include <stdlib.h>// Cada nodo en una lista enlazada es una estructura. El nodo cabeza es el primer nodo de la lista.typedef struct Nodo {valor entero ;struct Nodo * siguiente ;} Nodo ;Nodo * addNodeToTail ( Nodo * cabeza , int valor ) {// Declara un puntero al nodo y lo inicializa para que apunte al nuevo nodo (es decir, tendrá la dirección de memoria del nuevo nodo) que se agregará al final de la lista.Nodo * temp = ( Nodo * ) malloc ( sizeof * temp ); /// 'malloc' en stdlib.temp -> valor = valor ; // Agrega datos al campo valor del nuevo nodo.temp -> next = NULL ; // inicializar los enlaces no válidos a nil.si ( ! cabeza ) {cabeza = temp ; // Si la lista enlazada está vacía (es decir, el puntero del nodo cabeza es un puntero nulo), entonces el puntero del nodo cabeza apunta al nuevo nodo.} demás {Nodo * p = cabeza ; // Asigna el puntero del nodo cabeza al puntero del nodo 'p'.mientras ( p -> siguiente ) {p = p -> next ; // Recorre la lista hasta que p sea el último nodo. El último nodo siempre apunta a NULL.}p -> next = temp ; // Hace que el último nodo anterior apunte al nuevo nodo.}return head ; // Devuelve el puntero al nodo cabeza.}

En una lista doblemente enlazada, cada nodo contiene, además del enlace al nodo siguiente, un segundo campo de enlace que apunta al nodo anterior en la secuencia. Estos dos enlaces pueden denominarse «adelante» y «atrás», o «siguiente» y «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, por lo que podría no estar disponible en algunos lenguajes de alto nivel.

Muchos sistemas operativos modernos utilizan listas doblemente enlazadas para mantener referencias a procesos activos, subprocesos y otros objetos dinámicos. ^{[ 4 ]} Una estrategia común para que los rootkits evadan la detección es desvincularse de estas listas. ^{[ 5 ]}

En una lista enlazada múltiple, cada nodo contiene dos o más campos de enlace, donde cada campo conecta el mismo conjunto de datos organizados en un orden diferente (por ejemplo, por nombre, departamento, fecha de nacimiento, etc.). Si bien una lista doblemente enlazada puede considerarse un caso especial de una lista enlazada múltiple, el hecho de que los dos o más órdenes sean opuestos entre sí da lugar a algoritmos más sencillos y eficientes, por lo que generalmente se tratan como un caso aparte.

En el último nodo de una lista enlazada, el campo de enlace suele contener una referencia nula , un valor especial que indica la ausencia de más nodos. Una convención menos común es que apunte al primer nodo de la lista; en ese caso, se dice que la lista es circular o está enlazada circularmente; de ​​lo contrario, se dice que es abierta o lineal. Se trata de una lista en la que el puntero del último nodo apunta al primero (es decir, el puntero "enlace al siguiente nodo" del último nodo tiene la dirección de memoria del primer nodo).

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

En algunas implementaciones, se puede agregar un nodo adicional, denominado "centinela" o "ficticio", 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 forma segura y que cada lista (incluso una que no contenga elementos de datos) siempre tenga un nodo "inicial" y un nodo "final".

Una lista vacía es aquella que no contiene ningún registro de datos. Esto suele ser equivalente a decir que tiene cero nodos. Si se utilizan nodos centinela, se suele decir que la lista está vacía cuando solo contiene dichos nodos.

Los campos de enlace no tienen por qué formar parte físicamente de los nodos. Si los registros de datos se almacenan en una matriz y se referencian mediante sus índices, el campo de enlace puede almacenarse en una matriz independiente con los mismos índices que los registros de datos.

Dado que una referencia al primer nodo da acceso a toda la lista, a esa referencia se la suele llamar «dirección», «puntero» o «identificador» de la lista. Los algoritmos que manipulan listas enlazadas suelen obtener estos identificadores de las listas de entrada y devolver los identificadores de las listas resultantes. De hecho, en el contexto de estos algoritmos, la palabra «lista» suele significar «identificador de lista». Sin embargo, en algunas situaciones, puede resultar conveniente referirse a una lista mediante un identificador compuesto por dos enlaces que apuntan a su primer y último nodo.

Las alternativas enumeradas anteriormente se pueden combinar arbitrariamente de casi cualquier forma, por lo que se pueden tener listas doblemente enlazadas circulares sin centinelas, listas simplemente enlazadas circulares con centinelas, etc.

Un array dinámico es una estructura de datos que asigna todos los elementos de forma contigua en la memoria y mantiene un contador del número actual de elementos. Si se supera el espacio reservado para el array dinámico, este se reasigna y (posiblemente) se copia, lo cual es una operación costosa.

Las listas enlazadas presentan varias ventajas sobre los arreglos dinámicos. La inserción o eliminación de un elemento en un punto específico de una lista, suponiendo que ya existe un puntero que apunta al nodo (anterior al que se va a eliminar o al punto de inserción), es una operación de tiempo constante (de lo contrario, sin esta referencia, la complejidad es O(n)). En cambio, la inserción en un arreglo dinámico en posiciones aleatorias requiere, en promedio, mover la mitad de los elementos, y en el peor de los casos, todos. Si bien es posible "eliminar" un elemento de un arreglo en tiempo constante marcando su posición como "vacante", esto provoca una fragmentación que dificulta la iteración.

Además, se puede insertar una cantidad arbitraria de elementos en una lista enlazada, limitada únicamente por la memoria total disponible; mientras que un arreglo dinámico eventualmente llenará su estructura de datos subyacente y tendrá que reasignar memoria, una operación costosa que incluso podría no ser posible si la memoria está fragmentada, aunque el costo de la reasignación se puede promediar entre las inserciones, y el costo de una inserción debido a la reasignación aún se amortizaría O(1). Esto facilita la adición de elementos al final del arreglo, pero insertar (o eliminar) en posiciones intermedias aún conlleva costos prohibitivos debido al movimiento de datos para mantener la contigüidad. Un arreglo del que se eliminan muchos elementos también podría tener que redimensionarse para evitar desperdiciar demasiado espacio.

Por otro lado, los arreglos dinámicos (así como las estructuras de datos de arreglos de tamaño fijo ) permiten el acceso aleatorio en tiempo constante , mientras que las listas enlazadas solo permiten el acceso secuencial a los elementos. De hecho, las listas enlazadas simples solo se pueden recorrer fácilmente en una dirección. Esto las hace inadecuadas para aplicaciones donde es útil buscar un elemento rápidamente por su índice, como en el algoritmo de ordenación por montículos (heapsort ). El acceso secuencial a arreglos y arreglos dinámicos también es más rápido que a listas enlazadas en muchas máquinas, debido a que tienen una localidad de referencia óptima y, por lo tanto, hacen un buen uso del almacenamiento en caché de datos.

Otra desventaja de las listas enlazadas es el almacenamiento adicional necesario para las referencias, lo que a menudo las hace poco prácticas para listas de elementos de datos pequeños como caracteres o valores booleanos , porque la sobrecarga de almacenamiento para los enlaces puede superar en un factor de dos o más el tamaño de los datos. En cambio, un arreglo dinámico solo requiere el espacio para los datos en sí (y una cantidad muy pequeña de datos de control). ^{[ nota 1 ]} También puede ser lento, y con un asignador ingenuo, derrochador, asignar memoria por separado para cada nuevo elemento, un problema que generalmente se resuelve usando grupos de memoria .

Algunas soluciones híbridas intentan combinar las ventajas de ambas representaciones. Las listas enlazadas desplegadas almacenan varios elementos en cada nodo, lo que aumenta el rendimiento de la caché y reduce la sobrecarga de memoria para las referencias. La codificación CDR también logra esto, reemplazando las referencias con los datos reales referenciados, que se extienden más allá del final del registro de referencia.

Un buen ejemplo que ilustra las ventajas y desventajas de usar arreglos dinámicos frente a listas enlazadas es la implementación de un programa que resuelve el problema de Josefo . El problema de Josefo es un método de elección que consiste en que un grupo de personas se coloque en círculo. Comenzando con una persona predeterminada, se puede contar alrededor del círculo n veces. Una vez que se llega a la persona n , se debe eliminar del círculo y hacer que los miembros lo cierren. El proceso se repite hasta que solo queda una persona. Esa persona gana la elección. Esto muestra las fortalezas y debilidades de una lista enlazada frente a un arreglo dinámico, porque si las personas se consideran nodos conectados en una lista enlazada circular, entonces se 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á ineficiente para encontrar a la siguiente persona a eliminar y tendrá que buscar en la lista hasta encontrarla. Por otro lado, un array dinámico tendrá dificultades para eliminar nodos (o elementos), ya que no puede eliminar un nodo sin desplazar individualmente todos los elementos de la lista una posición hacia arriba. Sin embargo, es excepcionalmente fácil encontrar a la enésima persona del círculo haciendo referencia directa a su posición en el array.

El problema de la clasificación de listas se refiere a la conversión eficiente de una lista enlazada en una matriz. Si bien es trivial para una computadora convencional, resolver este problema mediante un algoritmo paralelo es complejo y ha sido objeto de numerosas investigaciones.

Un árbol equilibrado tiene patrones de acceso a memoria y sobrecarga de espacio similares a los de una lista enlazada, pero permite una indexación mucho más eficiente, con un tiempo de O(log n) en lugar de O(n) para un acceso aleatorio. Sin embargo, las operaciones de inserción y eliminación son más costosas debido a la sobrecarga de las manipulaciones del árbol para mantener el equilibrio. Existen esquemas para que los árboles se mantengan automáticamente en un estado equilibrado: árboles AVL o árboles rojo-negro .

Si bien las listas doblemente enlazadas y circulares tienen ventajas sobre las listas lineales simplemente enlazadas, las listas lineales ofrecen algunas ventajas que las hacen preferibles en ciertas situaciones.

Una lista lineal enlazada simple es una estructura de datos recursiva , ya que contiene un puntero a un objeto más pequeño del mismo tipo. Por ello, muchas operaciones con listas lineales enlazadas simples (como la fusión de dos listas o la enumeración de los elementos en orden inverso) suelen tener algoritmos recursivos muy sencillos, mucho más simples que cualquier solución que utilice comandos iterativos . Si bien estas soluciones recursivas pueden adaptarse a listas doblemente enlazadas y circulares, los procedimientos generalmente requieren argumentos adicionales y casos base más complejos.

Las listas enlazadas simples lineales también permiten compartir la cola , es decir, usar una porción final común de una sublista como la porción terminal de dos listas diferentes. En concreto, si se añade un nuevo nodo al principio de una lista, la lista anterior permanece disponible como la cola de la nueva, un ejemplo sencillo de estructura de datos persistente . Sin embargo, esto no ocurre con las otras variantes: un nodo nunca puede pertenecer a dos listas circulares o doblemente enlazadas diferentes.

En particular, los nodos centinela final pueden compartirse entre listas no circulares enlazadas individualmente. El mismo nodo centinela final puede usarse para cada una de dichas listas. En Lisp , por ejemplo, cada lista propia termina con un enlace a un nodo especial, denotado por nilo ().

Las ventajas de las variantes más sofisticadas suelen limitarse a la complejidad de los algoritmos, no a su eficiencia. Una lista circular, en particular, generalmente puede emularse mediante una lista lineal con dos variables que apunten al primer y último nodo, sin coste adicional.

Las listas doblemente enlazadas requieren más espacio por nodo (a menos que se utilice el enlace XOR ), y sus operaciones elementales son más costosas; 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 con solo conocer la dirección de ese nodo. Para hacer lo mismo en una lista simplemente enlazada, se necesita 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 se pueden usar como estructuras de datos persistentes .

Una lista enlazada circular puede ser una opción natural para representar arreglos que son inherentemente circulares, por ejemplo, los vértices 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 deben compartirse en orden rotatorio . En estas aplicaciones, un puntero a cualquier nodo sirve como identificador de toda la lista.

En una lista circular, un puntero al último nodo permite acceder fácilmente también al primero, siguiendo un único 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 gestionarla con un solo puntero, en lugar de dos.

Una lista circular se puede dividir en dos listas circulares, en tiempo constante, proporcionando las direcciones del último nodo de cada segmento. La operación consiste en intercambiar el contenido de los campos de enlace de esos dos nodos. Al aplicar la misma operación a cualquier par de nodos en dos listas distintas, se unen las dos listas en una sola. Esta propiedad simplifica enormemente algunos algoritmos y estructuras de datos, como las de aristas cuádruples y de caras .

La representación más sencilla de una lista circular vacía (cuando tiene sentido) es un puntero nulo, que indica que la lista no tiene nodos. Sin esta opción, muchos algoritmos deben comprobar este caso especial y gestionarlo por separado. En cambio, usar el puntero nulo para denotar una lista lineal vacía es más natural y suele generar menos casos especiales.

Para algunas aplicaciones, puede ser útil usar listas enlazadas simples que pueden ser circulares o lineales, o incluso circulares con un segmento inicial lineal. Los algoritmos para buscar o trabajar con estas listas deben tomar precauciones para evitar entrar accidentalmente en un bucle infinito. Un método conocido consiste en que un segundo puntero recorra la lista a la mitad o al doble de velocidad; si ambos punteros coinciden en el mismo nodo, se ha encontrado un ciclo.

Un nodo centinela puede simplificar ciertas operaciones con listas, asegurando que existan nodos siguientes o anteriores para cada elemento, e incluso que 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 comprobaciones de fin de lista. Por ejemplo, al recorrer la lista buscando un nodo con un valor x dado , establecer el campo de datos del centinela en x hace innecesario comprobar el fin de lista 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 requiere un tratamiento especial para listas vacías.

Sin embargo, los nodos 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 añadiendo un nodo centinela a cada lista, entre el último y el primer nodo de datos. Con esta convención, una lista vacía consta únicamente del nodo centinela, que apunta a sí mismo mediante el enlace al siguiente nodo. El identificador de la lista debería ser entonces un puntero al último nodo de datos, anterior al centinela, si la lista no está vacía; o al propio centinela, si la lista está vacía.

El mismo truco puede utilizarse 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 manejador debe ser un único puntero al propio nodo ficticio. ^{[ 8 ]}

En una lista enlazada circular, todos los nodos están enlazados en un círculo continuo, sin usar el valor 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 es el primero. Se pueden agregar elementos al final de la lista y eliminarlos del frente en tiempo constante.

Las listas enlazadas circularmente pueden estar enlazadas de forma simple o doble.

Ambos tipos de listas enlazadas circularmente se benefician de la capacidad de recorrer la lista completa comenzando en cualquier nodo. Esto a menudo nos permite evitar almacenar `firstNode` y `lastNode` , aunque si la lista puede estar vacía, se necesita una representación especial para la lista vacía, como una variable `lastNode` que apunte a algún nodo de la lista o sea nula si está vacía; aquí se utiliza una variable `lastNode` de este tipo . Esta representación simplifica significativamente la adición y eliminación de nodos en una lista no vacía, pero las listas vacías constituyen un caso especial.

función iterar(someNode) si someNode ≠ null nodo := algúnNodo hacer Haz algo con node.value nodo := nodo.siguiente mientras nodo ≠ algúnNodo

función insertAfter( Nodo nodo , Nodo nuevoNodo) si nodo = null // se asume que la lista está vacía nuevoNodo.siguiente := nuevoNodo demás nuevoNodo.siguiente := nodo.siguiente nodo.siguiente := nuevoNodo Actualizar la variable lastNode si es necesario.

insertarDespués(L, nuevoNodo) L := nuevoNodo

insertAfter(L, newNode) si L = null L := newNode

función insertBefore( Node node, newVal) if node = null // se asume que la lista está vacía newNode := newNode (data:=newVal, next:=newNode) else newNode := newNode (data:=node.data, next:=node.next) nodo.datos := nuevoValor nodo.siguiente := nuevoNodo Actualizar la variable firstNode si es necesario .

función remove( Nodo nodo ) si nodo ≠ null y tamaño de la lista > 1 removedData := node.data nodo.datos := nodo.siguiente.datos nodo.siguiente = nodo.siguiente.siguiente devolver datos eliminados

Los lenguajes que no admiten ningún tipo de referencia aún pueden crear enlaces reemplazando los punteros por índices de matrices. El método consiste en 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 .

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

Registro Entrada { entero siguiente; // índice de la siguiente entrada en el array entero anterior; // entrada anterior (si está doblemente vinculada) cadena nombre; real saldo; }

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

Lista de enteros Registros de entrada de encabezado [1000]

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

En el ejemplo anterior, ListHeadse establecería en 2, la posición de la primera entrada en la lista. Nótese que las entradas 3 y de la 5 a la 7 no forman parte de la lista. Estas celdas están disponibles para añadir elementos a la lista. Al crear una ListFreevariable entera, se podría crear una lista de celdas libres para controlar qué celdas están disponibles. Si todas las entradas están en uso, habría que aumentar el tamaño del array 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 mientras i ≥ 0 // iterar sobre la lista imprimir i, Records[i].name, Records[i].balance // imprimir entrada i := Records[i].next

Ante la disyuntiva, las ventajas de este enfoque incluyen:

• La lista enlazada es reubicable, lo que significa que se puede mover en la memoria a voluntad, y también se puede serializar de forma rápida y directa para su almacenamiento en disco o transferencia a través de una red.
• Especialmente para listas pequeñas, los índices de matrices pueden ocupar mucho menos espacio que un puntero completo en muchas arquitecturas.
• La localidad de referencia se puede mejorar manteniendo los nodos juntos en la memoria y reorganizándolos periódicamente, aunque esto también se puede hacer en un almacén general.
• Los asignadores de memoria dinámica ingenuos pueden producir una cantidad excesiva de almacenamiento adicional por cada nodo asignado; con este enfoque, prácticamente no se incurre en ningún gasto adicional de asignación por nodo.
• Tomar una entrada de una matriz preasignada 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 la búsqueda de un bloque de memoria libre del tamaño deseado.

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

• Esto aumenta la complejidad de la implementación.
• Ampliar una matriz grande cuando está llena puede ser difícil o imposible, mientras que encontrar espacio para un nuevo nodo de lista enlazada en un gran conjunto de memoria general puede ser más fácil.
• Agregar elementos a una matriz dinámica ocasionalmente (cuando está llena) tomará inesperadamente un tiempo lineal ( O (n)) en lugar de un tiempo constante (aunque sigue siendo una constante amortizada ).
• El uso de un grupo de memoria general deja más memoria disponible para otros datos si la lista es más pequeña de lo esperado o si se liberan muchos nodos.

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

Para crear una lista enlazada de familias y sus miembros, utilizando el almacenamiento interno, la estructura podría ser la siguiente:

registro miembro { // miembro de una familia miembro siguiente; cadena nombre; entero edad; } registro familia { // la familia en sí familia siguiente; cadena apellido; cadena dirección; miembro miembros // cabeza de la lista de miembros de esta familia }

Para imprimir una lista completa de familias y sus miembros utilizando el almacenamiento interno, escriba:

aFamily := Families // comienza en el inicio de la lista de familias mientras aFamily ≠ null // recorre la lista de familias Imprimir información sobre la familia aMember := aFamily.members // obtener el primer elemento de la lista de miembros de esta familia mientras aMember ≠ null // recorrer la lista de miembros Imprimir información sobre el miembro unMiembro := unMiembro.siguiente unaFamilia := unaFamilia.siguiente

Mediante el uso de almacenamiento externo, se pueden crear las siguientes estructuras:

nodo de registro { // nodo de estructura de enlace genérico siguiente; puntero de datos // puntero genérico para datos en el nodo } miembro del registro { // estructura para el miembro de la familia cadena firstName; entero edad } registro familia { // estructura para la familia cadena apellido; cadena dirección; nodo miembros // cabeza de la lista de miembros de esta familia }

Para imprimir una lista completa de familias y sus miembros utilizando almacenamiento externo, escriba:

famNode := Familias // comienza en la cabecera de la lista de familias mientras famNode ≠ null // recorre la lista de familias aFamily := (familia) famNode.data // extrae la familia del nodo Imprimir información sobre la familia memNode := aFamily.members // obtener la lista de miembros de la familia while memNode ≠ null // recorrer la lista de miembros aMember := (member)memNode.data // extraer el miembro del nodo Imprimir información sobre el miembro memNode := memNode.next famNode := famNode.next

Tenga en cuenta que, al usar almacenamiento externo, se requiere un paso adicional para extraer el registro del nodo y convertirlo al tipo de dato adecuado. Esto se debe a que tanto la lista de familias como la lista de miembros dentro de la familia se almacenan en dos listas enlazadas que utilizan la misma estructura de datos ( nodo ), y este lenguaje no admite tipos paramétricos.

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

Encontrar un elemento específico en una lista enlazada, incluso si está ordenada, normalmente requiere un tiempo de O( n ) ( búsqueda lineal ). Esta es una de las principales desventajas de las listas enlazadas frente a otras estructuras de datos. Además de las variantes mencionadas anteriormente, a continuación se presentan dos maneras sencillas de mejorar el tiempo de búsqueda.

En una lista no ordenada, una heurística sencilla para reducir el tiempo medio de búsqueda es la heurística de mover al principio , que consiste simplemente en colocar un elemento al inicio de la lista una vez encontrado. Este método, útil para crear cachés sencillas, garantiza que los elementos utilizados más recientemente sean también los más fáciles de encontrar.

Otro enfoque común consiste en indexar una lista enlazada utilizando una estructura de datos externa más eficiente. Por ejemplo, se puede construir un árbol rojo-negro o una tabla hash cuyos elementos sean referencias a los nodos de la lista enlazada. Se pueden crear varios índices de este tipo sobre una misma lista. La desventaja es que estos índices pueden necesitar actualizarse cada vez que se añade o elimina un nodo (o, al menos, antes de volver a utilizar ese índice).

Una lista de acceso aleatorio es una lista que permite 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 binaria asimétrica que utiliza el sistema numérico binario asimétrico , el cual implica una lista de árboles con propiedades especiales; esto permite operaciones de cabeza/consecuencia en el peor de los casos con tiempo constante y acceso aleatorio a un elemento por índice en el peor de los casos con tiempo logarítmico. ^{[ 9 ]} Las listas de acceso aleatorio pueden implementarse como estructuras de datos persistentes . ^{[ 9 ]}

Las listas de acceso aleatorio pueden considerarse listas enlazadas inmutables, ya que también admiten las mismas operaciones de cabeza y cola de complejidad O(1). ^{[ 9 ]}

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