Una lista vinculada es una colección de objetos vinculados entre sí por referencias de un objeto a otro objeto. Por convención, estos objetos son nombres como nodos . Por lo tanto, la lista enlazada básica, o comúnmente llamada lista enlazada individualmente, consiste en nodos donde cada nodo contiene uno o más campos de datos Y una referencia al siguiente nodo. El último nodo contiene una referencia nula para indicar el final de la lista. A diferencia de las matrices donde la memoria se asigna como un bloque contiguo de memoria, la memoria requerida para cada nodo se puede asignar según sea necesario, proporcionando así una mejor manera de administrar la memoria libre.
Características de las listas vinculadas:
- • sin tamaño fijo; crecer un elemento a la vez
- • espacio por encima
- • cada elemento debe almacenar una referencia adicional
- • S = nx sizeof (elemento) + nx sizeof (referencia)
- • no hay acceso fácil al elemento i-ésimo wrt el encabezado de la lista
- • necesita saltar todos los elementos anteriores
Tipos de listas enlazadas
- Cómo guardar una entrada del usuario en una matriz definida en Java
- Con los algoritmos de cifrado modernos, ¿es factible que alguien sepa qué algoritmo se utilizó al mirar el texto cifrado?
- En programación de computadoras, ¿cómo es recursivo el proceso de evaluación?
- ¿Cuáles son las aplicaciones de la lista de enlaces simple, doble, circular y de encabezado en la estructura de datos?
- ¿Existe un algoritmo para aplicar a una imagen que muestre lo que vería alguien que necesita corrección de la visión?
Hay pocos tipos diferentes de listas vinculadas. Una lista vinculada individualmente como se describe anteriormente proporciona acceso a la lista desde el nodo principal. El recorrido está permitido solo de una manera y no hay marcha atrás. El final de la lista se indica mediante una referencia nula. Aquí hay un ejemplo de una lista individualmente vinculada.
12
34
56
nulo
Cabeza
Una lista doblemente vinculada es una lista que tiene dos referencias de cada nodo, una al siguiente nodo y otra al nodo anterior. Las listas doblemente vinculadas también comienzan desde el nodo principal, pero proporcionan acceso en ambos sentidos. La flexibilidad de una lista doblemente vinculada es que uno puede atravesar hacia adelante o hacia atrás desde cualquier nodo. Una lista doblemente vinculada puede ser adecuada para aplicaciones que requieren actualizaciones frecuentes de nodos que están en un rango cercano. Aquí hay un ejemplo de un
lista doblemente vinculada.
nulo nulo
Una lista multienlace es una lista vinculada más general con múltiples enlaces desde nodos. Por ejemplo, supongamos que necesitamos mantener una lista en dos órdenes, edad y nombre. Podemos definir un nodo que tenga dos referencias, un puntero de edad y un puntero de nombre. Entonces es posible mantener una lista, donde si seguimos el puntero de nombre podemos atravesar la lista en orden alfabético y si atravesamos el puntero de edad, podemos atravesar la lista por edad. Este tipo de organización de nodos puede ser útil para mantener una lista de clientes en un banco donde se pueda recorrer la misma lista en cualquier orden (nombre, edad o cualquier otro criterio) según la necesidad. Aquí hay un ejemplo de una lista multienlace.
La lista anterior muestra cómo se mantienen dos punteros para seguir la lista en orden de edad o de nombre. Se puede utilizar una lista multienlace más compleja para almacenar una matriz “dispersa” de la siguiente manera.
Otro tipo importante de una lista vinculada se llama una lista vinculada circular donde el último nodo de la lista apunta al primer nodo (o el encabezado) de la lista. Aquí hay un ejemplo de una lista circular individualmente vinculada.
Aplicaciones de listas enlazadas
El concepto de Lista enlazada se puede utilizar para tratar muchos problemas prácticos.
Problema 1: suponga que necesita programar una aplicación que tenga un número predefinido de categorías, pero se desconocen los elementos exactos de cada categoría.
Solución: El número predefinido de categorías implica que podemos usar una estructura estática simple como una matriz para representar las categorías. Como no conocemos el número de elementos en cada categoría, podemos representar elementos en cada categoría usando una lista vinculada. Entonces, lo que necesitamos es una serie de listas vinculadas
Más ejemplos
- También puede pensar en representar un índice web utilizando una matriz de listas vinculadas, donde
- La matriz contiene las palabras clave y las listas enlazadas contiene las URL de la web donde
Matrices dispersas
• La mayoría de los problemas pueden ser modelados por un sistema de ecuaciones lineales.
– Miles de ecuaciones (restricciones)
– Miles de variables (incógnitas)
– No es práctico asignar espacio n por n para almacenar un sistema lineal
– Cuánto espacio es necesario para una matriz de tamaño 10000 × 10000 donde cada entrada
es un doble?
– Escasa representación matricial
Diseño del nodo para matriz dispersa
Nodo de clase pública
{
datos comparables públicos;
public int row, col;
Nodo público nextrow;
Nodo público nextcol;
Nodo (int fila, int col, datos comparables) {
this.data = datos; this.row = fila; this.col = col;
nextrow = nulo; nextcol = nulo;
}
public String toString () {return data.toString ();}
Otras operaciones avanzadas en listas enlazadas
- Revertir una lista vinculada
- Clonando una Lista Vinculada
Comencemos evaluando el siguiente código
Lista LinkedList = new LinkedList ();
list.prepend (new Node (“first”));
list.append (nuevo nodo (“último”));
LinkedList list2 = list;
La referencia list2 es un alias, apunta al mismo objeto que list1. Esto significa que una vez que
c Ordenar una lista vinculada
• Ordenar una lista es una de las operaciones comunes que se realizan.
• Ordenar una lista vinculada no es tan trivial ya que no se puede acceder aleatoriamente a los nodos de la lista vinculada.
• Una forma útil de ordenar una lista vinculada es eliminar un nodo de la lista anterior e insertarlo en un
nueva lista en orden.
o Sin embargo, para listas grandes, esto no es muy práctico ya que la ordenación por inserción requiere O (n2
) operaciones.
• Un método alternativo es definir un método toArray para la clase de lista vinculada que permite
la lista vinculada se convertirá primero en una matriz y luego se aplicará un algoritmo más eficiente
como clasificación rápida para ordenar.
o Una vez ordenado, la matriz se puede convertir de nuevo en una lista vinculada.
Estos cambios también ocurren en list2. En este caso, consideramos list2 como una copia superficial de list1. En otras palabras, list1 y list2 comparte los mismos nodos en una lista vinculada. En muchos casos, será bastante útil tener una copia profunda de un objeto. Para crear una copia profunda, necesitamos duplicar todos los nodos en la lista. Para este propósito, la clase Object proporciona el método clone (), que reemplazaremos en la clase LinkedList:
public Object clone () arroja java.lang.CloneNotSupportedException
{
LinkedList twin = new LinkedList ();
if (head == null) devuelve gemelo;
Nodo tmp = cabeza;
para (int i = 0; i <tamaño; i ++)
{ Yo
twin.append (tmp.data);
tmp = tmp.getNext ();
}
volver gemelo;
}
Ordenar una lista vinculada
• Ordenar una lista es una de las operaciones comunes que se realizan.
• Ordenar una lista vinculada no es tan trivial ya que no se puede acceder aleatoriamente a los nodos de la lista vinculada.
• Una forma útil de ordenar una lista vinculada es eliminar un nodo de la lista anterior e insertarlo en una nueva lista en orden.
o Sin embargo, para listas grandes, esto no es muy práctico ya que la ordenación por inserción requiere O (n2
)
Operaciones
• Un método alternativo es definir un método toArray para la clase de lista vinculada que permite
la lista vinculada se convertirá primero en una matriz y luego aplicará un algoritmo más eficiente, como la ordenación rápida para ordenar.
o Una vez ordenado, la matriz se puede convertir de nuevo en una lista vinculada.
Preguntas
• La elección de la estructura de datos adecuada depende de la aplicación. Especifique qué estructura de datos elegiría en cada uno de los siguientes casos. Puede elegir entre una matriz estática, una lista vinculada individualmente, una LL circular, una LL doble, una matriz de LL, una lista multienlace, etc.
– Se proporciona un archivo ordenado y se debe construir una lista en orden inverso en O (n)
– Una aplicación requiere una estructura en la que los nuevos nodos se puedan agregar fácilmente al frente y la parte posterior de un nodo dado en O (1)
– Una aplicación requiere una estructura de datos a la que se pueda acceder aleatoriamente
– Un conjunto de entradas debe ordenarse primero por una categoría. Cada categoría recibirá un número desconocido de entradas
– Una aplicación requiere inserciones frecuentes, generalmente en la misma región
– Una lista debe mantenerse en múltiples órdenes ordenadas, pero el espacio para cada entrada se puede asignar solo una vez.
