Concepto de lista enlazada
Una lista simplemente enlazada pertenece a las estructuras de datos fundamentales. Suele utilizarse para implementar otras estructuras de datos.
Está estructurada en una secuencia de nodos, en los que se guardan los datos y un puntero que apunta (contiene la dirección de la ubicación) al siguiente nodo.
La principal utilidad de la lista enlazada es que el orden de los elementos enlazados puede ser diferente al orden de almacenamiento físico en memoria. De este modo se permite que el orden de lectura de la lista sea diferente al orden de almacenamiento físico. Al contrario de un array, el acceso a cada elemento no se hace a través de un índice sino mediante un puntero. Otra diferencia con los arrays es que estos pueden ser accedidos de forma aleatoria mientras que la lista se recorre de forma ordenada.
La lista también permite añadir o eliminar nodos en cualquier lugar aunque no permite un acceso aleatorio. Cuando es necesario hacer varias operaciones de inserción y eliminación de elementos en un conjunto resulta conveniente utilizar listas enlazadas. El puntero del último nodo contiene un valor vacío Null.
Si queremos leer un nodo es necesario comenzar a recorrer la lista desde el principio, el puntero al siguiente es el que apunta al siguiente elemento. El movimiento a través de la lista se realiza en una sola dirección, desde el primer al último elemento. Mientras que en un array el acceso es aleatorio, como contrapartida una lista sólo utiliza la memoria si tiene datos mientras que el array ocupa toda la memoria asignada aunque esté vacío.
Listas simplemente enlazadas en Microsoft Visual Studio
Existe un objeto de lista simplemente enlazada en visual studio, para acceder a es necesario invocar las siguientes librerías de microsoft
using System;
using System.Text;
using System.Collections.Generic;
Después podemos utilizar
el objeto de la librería llamado
LinkedList
Construcción de la Lista
Cada elemento de la
lista contiene uno o varios campos con los datos y un puntero apuntando a la dirección
donde está ubicado el siguiente nodo. Cada objeto de la lista se llama nodo y
contiene como se ha dicho los datos y un puntero al siguiente elemento.
La lista comienza desde la pila con un
puntero apuntando al primer nodo, después el
primer nodo tiene un puntero apuntando al segundo nodo y así
sucesivamente hasta que el puntero del último nodo contiene null.
Operaciones sobre listas enlazadas
Una lista enlazada vacía es un Null.
Nodo y Puntero
Un nodo es una variable de un tipo dado,
entero, cadena, etc almacenada en la memoria. En este caso es una variable de
tipo object.
Un puntero es un dato que contiene la
dirección del siguiente nodo. En este caso es un objeto de tipo nodo que apunta
al siguiente nodo llamado next.
public class Nodo {
public Object dato; // dato contenido en el nodo
public Nodo siguiente; //puntero al siguiente
nodo
}
Insertar un elemento en la lista
Para insertar un nuevo elemento en la lista se sigue la
siguiente secuencia:
-Declaración del elemento a insertar.
-Asignación de la memoria para el nuevo elemento
- Insertar el contenido en los datos.
-Actualizar los punteros que apuntan al primer y
último elemento.
-Actualizar el tamaño de la lista.
Además se presentan varios casos a la hora de insertar un elemento en una lista:
- 1. Inserción en una lista vacía.
- 2. Inserción al comienzo de la lista.
- 3. Inserción al final de la lista.
- 4. Inserción en otra parte de la lista.
Inserción en una lista vacía
Las etapas para insertar un elemento en una lista vacía son las
siguientes:
-Reserva de memoria para el nuevo
elemento.
-Introducir el nuevo elemento en memoria.
-Como es una lista vacía el puntero hacia el siguiente elemento apuntará
a Null.
-Los punteros inicio y fin apuntaran hacia
el nuevo elemento.
- Se actualiza la variable que contiene el tamaño
de la lista.
Inserción al comienzo de la lista
-Reserva de memoria para el nuevo
elemento.
Nodo Añadir
= new Nodo();
-Introducir el nuevo elemento en memoria.
Añadir.dato = dato;
-El puntero hacia el siguiente elemento apuntará al primer elemento.
Añadir.siguiente = comienzo;
-El puntero inicio apuntará al nuevo elemento.
comienzo = Añadir;
-El puntero
fin se queda sin cambios.
- Se actualiza la variable que contiene el tamaño
de la lista.
Esto lo podemos implementar ya en el siguiente
código
public void InsertarComienzo(Object dato)
{
Nodo Añadir = new Nodo();
Añadir.dato = dato;
Añadir.siguiente = comienzo;
comienzo = Añadir;
}
Inserción al final de la lista
-Reserva de memoria para el nuevo
elemento.
Nodo añadir
= new Nodo();
-Introducir el nuevo elemento en memoria.
añadir.dato = dato;
-El puntero hacia el siguiente elemento apuntará al último elemento.
comienzo.siguiente = null;
-El puntero de fin apunta hacia el nuevo elemento introducido.
while (actual.siguiente
!= null)
{
actual = actual.siguiente;
}
-El puntero inicio se queda sin cambios.
- Se actualiza la variable que contiene el tamaño
de la lista.
public void InsertarFinal(Object dato)
{
if (comienzo == null)
{
comienzo = new Nodo();
comienzo.dato = dato;
comienzo.siguiente = null;
}
else
{
Nodo añadir = new Nodo();
añadir.dato = dato;
Nodo actual = comienzo;
while (actual.siguiente != null)
{
actual = actual.siguiente;
}
actual.siguiente = añadir;
}
}
}
Inserción en cualquier lugar de la lista
Para insertar un elemento en cualquier parte de la
lista previamente hay que pasar a la función una posición como argumento. Si la posición indicada no es el
primer o el último elemento para lo que ya se han expuesto los casos
anteriores.
-Reserva de memoria para el nuevo elemento.
-Introducir el nuevo elemento en memoria.
-El puntero hacia el siguiente elemento apuntará a la dirección a la que
apunta el puntero siguiente del elemento actual.
- El puntero hacia el siguiente elemento del elemento actual apuntará
hacia el nuevo elemento
- No se producen cambios en los punteros inicio y fin.
- Se actualiza la variable que contiene el tamaño
de la lista.
Eliminar un elemento en la lista
Para eliminar un elemento en la lista se sigue la
siguiente secuencia:
-Es necesario utilizar un puntero temporal que almacene
la dirección del nodo que será eliminado.
- El elemento a eliminar se encontrará después del
elemento actual.
El puntero a siguiente del elemento actual deberá
apuntar a la dirección del puntero siguiente a la que apunta el elemento que se
elimina.
- se libera la memoria que ocupaba el viejo elemento.
- Se actualiza la variable que contiene el tamaño
de la lista.
Además se presentan dos casos a la hora de eliminar un elemento en una lista:
- Eliminación al comienzo de la lista.
- Eliminación en cualquier otra parte de la lista.
Eliminación al inicio de la lista
-Introducir el nuevo elemento en memoria.
-El puntero temporal apuntará al primer elemento.
-El puntero inicio apuntará al segundo elemento.
- Se actualiza la variable que contiene el tamaño
de la lista para disminuirla en un elemento.
Eliminación en cualquier lugar de la lista
-El puntero temporal apuntará a la dirección a la que apunta el puntero
siguiente del elemento actual.
-El puntero siguiente apuntará al elemento al que apunta el puntero
siguiente del elemento que sigue al elemento que estamos eliminado.
- Si el elemento que estamos eliminando es el penúltimo, se actualizará
el puntero fin.
- Se actualiza la variable que contiene el tamaño
de la lista para disminuirla en un elemento.
Visualización de la lista
Para visualizar la lista completa hay que posicionarse
al inicio (con el puntero inicio).
Luego con el puntero siguiente de cada elemento se recorre la lista.
La condición para detenerse es proporcionada por el
puntero siguiente del último elemento que posee el valor
NULL.
public class ListaEnlazada
{
private Nodo comienzo;
public void imprimeTodosLosNodos()
{
Nodo actual = comienzo;
while (actual != null)
{
Console.WriteLine(actual.dato);
actual =
actual.siguiente;
}
}
Implementación en C#
A continuación el programa completo, creamos una aplicación de consola
(sin formulario) y ponemos este código.
using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;
namespace LSE
{
//clase
que define el nodo de la lista
public class Nodo
{
public Object dato; // dato contenido en
el nodo
public Nodo siguiente; //
puntero al siguiente nodo
public Nodo comienzo; //Cabecera
de la lista
public void InsertarComienzo(Object dato)
{
Nodo Añadir = new Nodo();
Añadir.dato = dato;
Añadir.siguiente = comienzo;
comienzo = Añadir;
}
public void InsertarFinal(Object dato)
{
if (comienzo == null)
{
comienzo = new Nodo();
comienzo.dato = dato;
comienzo.siguiente = null;
}
else
{
Nodo añadir = new Nodo();
añadir.dato = dato;
Nodo actual = comienzo;
while (actual.siguiente != null)
{
actual = actual.siguiente;
}
actual.siguiente = añadir;
}
}
}
// Clase
que imprime todos los nodos de la lista
public class ListaEnlazada
{
private Nodo comienzo;
public void imprimeTodosLosNodos()
{
Nodo actual = comienzo;
while (actual != null)
{
Console.WriteLine(actual.dato);
actual = actual.siguiente;
}
}
}
class Program
{
static void Main(string[] args)
{
Console.WriteLine("Añade
al inicio:");
ListaEnlazada miLista1 = new ListaEnlazada();
Nodo miNodo1 = new Nodo();
miNodo1.InsertarComienzo("Hola");
miNodo1.InsertarComienzo("Mundo");
miNodo1.InsertarComienzo("Dato3");
miLista1.imprimeTodosLosNodos();
Console.WriteLine();
Console.WriteLine("Añade
al final:");
ListaEnlazada miLista2 = new ListaEnlazada();
Nodo miNodo2 = new Nodo();
miNodo2.InsertarFinal("Hola");
miNodo2.InsertarFinal("Mundo");
miNodo2.InsertarFinal("Dato3");
miLista1.imprimeTodosLosNodos();
Console.ReadLine();
}
}
}
Utilización de la lista enlazada que viene en Visual Studio (LinkedList)
Si no queremos hacerlo, no es necesario implementar
la lista enlazada. Ya viene implementada en el propio compilador de C#, por lo
que podemos hacer un programa que la llame directamente y la utilice. A continuación
un programa con varios ejemplos de utilización de la lista enlazada LinkedList del compilador de C#.
using System;
using System.Text;
using System.Collections.Generic;
using System.Linq;
using System.Threading.Tasks;
public class Ejemplo
{
public static void Main()
{
// Crea
la lista enlazada.
string[] palabras =
{ "el", "zorro", "saltó", "sobre", "el", "perro" };
LinkedList<string> frase = new LinkedList<string>(palabras);
Muestra(frase, "Valores de la lista enlazada:");
Console.WriteLine("frase.Contains(\"saltó\")
= {0}",
frase.Contains("saltó"));
// Añade
la palabra 'hoy' al comienzo de la lista.
frase.AddFirst("hoy");
Muestra(frase, "Test 1: Añade 'hoy' al comienzo de la lista:");
// Mueve
el primer nodo hasta el último nodo.
LinkedListNode<string> marca1 = frase.First;
frase.RemoveFirst();
frase.AddLast(marca1);
Muestra(frase, "Test 2: Mueve el primer nodo al la última
posición:");
// Modifica el último nodo por 'ayer'.
frase.RemoveLast();
frase.AddLast("ayer");
Muestra(frase, "Test 3: Modifica el último nodo por 'ayer':");
// Mueve
el último nodo al primero.
marca1 = frase.Last;
frase.RemoveLast();
frase.AddFirst(marca1);
Muestra(frase, "Test 4: Mueve el último nodo al primero:");
//
Indica con un paréntesis la última cocurrencia de 'el'.
frase.RemoveFirst();
LinkedListNode<string> actual = frase.FindLast("el");
IndicaNodo(actual, "Test 5: Indica con un paréntesis la última
cocurrencia de 'el'.:");
// Añade
'perezoso' y 'viejo' después de 'el' (el
LinkedListNode nombre actual).
frase.AddAfter(actual, "viejo");
frase.AddAfter(actual, "perezoso");
IndicaNodo(actual, "Test 6: Añade 'perezoso' y 'viejo' después de 'el' :");
//
Indica el nodo 'zorro'
actual = frase.Find("zorro");
IndicaNodo(actual, "Test 7: Indica el nodo 'zorro':");
// Añade
'rápido' and 'marrón' antes de 'zorro':
frase.AddBefore(actual, "rápido");
frase.AddBefore(actual, "marrón");
IndicaNodo(actual, "Test 8:Añade 'rápido' y 'marrón' antes de 'zorro':");
//
Mantiene una referencia al nodo actual 'zorro',
// y al
nodo previo previous en la lista. Indica el nodo 'perro'.
marca1 = actual;
LinkedListNode<string> marca2 = actual.Previous;
actual = frase.Find("perro");
IndicaNodo(actual, "Test 9: Indica el nodo 'perro':");
// el
método AddBefore devuelve una InvalidOperationException
// si se
intenta añadir un nodo que ya pertenece a la lista.
Console.WriteLine("Test
10: excepcion por intentar añadir el nodo (zorro) ya existe en la lista:");
try
{
frase.AddBefore(actual, marca1);
}
catch (InvalidOperationException ex)
{
Console.WriteLine("Exception
message: {0}", ex.Message);
}
Console.WriteLine();
//
Elimina el nodo al que se refiere la marca1, y añade otro
// antes
del nodo referenciado por el nodo actual.
//
Indica el nodo referenciado por el actual.
frase.Remove(marca1);
frase.AddBefore(actual, marca1);
IndicaNodo(actual, "Test 11: Mueve un nodo referenciado (zorro)antes del
nodo actual (perro):");
//
Elimina el nodo referenciado por el actual.
frase.Remove(actual);
IndicaNodo(actual, "Test 12: Elimina el nodo actual (perro) e intenta
indicarlo:");
// Añade
un nodo después del nodo referenciado por la marca2.
frase.AddAfter(marca2, actual);
IndicaNodo(actual, "Test 13: Añade el nodo eliminado en el tTest 11
después de referenciarlo (marrón):");
// El
método Remove encuentra y elimina el
//
primer nodo que tiene un valor especificado.
frase.Remove("viejo");
Muestra(frase, "Test 14: Elimina el nodo que tiene el valor 'viejo':");
//
Cuando la lista es convertida a una ICollection(de caracteres),
// el
método Add añade un nodo al final de la
lista.
frase.RemoveLast();
ICollection<string> icoleccion = frase;
icoleccion.Add("rinoceronte");
Muestra(frase, "Test 15: Elimina el último nodo convirtiéndolo a
ICollection,y añade 'rinoceronte':");
Console.WriteLine("Test
16: Copia la lista en un array:");
// Crea
un array con el mismo número de elementos que la lista
string[] sArray = new string[frase.Count];
frase.CopyTo(sArray, 0);
foreach (string s in sArray)
{
Console.WriteLine(s);
}
//
Libera todos los nodos.
frase.Clear();
Console.WriteLine();
Console.WriteLine("Test
17: Limpia la lista. Contiene 'saltó' = {0}",
frase.Contains("saltó"));
Console.ReadLine();
}
private static void Muestra(LinkedList<string> palabras, string testeo)
{
Console.WriteLine(testeo);
foreach (string palabra in palabras)
{
Console.Write(palabra + "
");
}
Console.WriteLine();
Console.WriteLine();
}
private static void IndicaNodo(LinkedListNode<string> nodo, string testeo)
{
Console.WriteLine(testeo);
if (nodo.List == null)
{
Console.WriteLine("Nodo
'{0}' no está en la lista.\n",
nodo.Value);
return;
}
StringBuilder resultado = new StringBuilder("(" + nodo.Value + ")");
LinkedListNode<string> nodoP = nodo.Previous;
while (nodoP != null)
{
resultado.Insert(0, nodoP.Value
+ " ");
nodoP = nodoP.Previous;
}
nodo = nodo.Next;
while (nodo != null)
{
resultado.Append(" " +
nodo.Value);
nodo = nodo.Next;
}
Console.WriteLine(resultado);
Console.WriteLine();
}
}
gracias por el aporte. si fuera doblemente enlazada como seria?
ResponderEliminarigual pero con un puntero al dato siguiente y otro al dato anterior
ResponderEliminarhttps://es.wikipedia.org/wiki/Lista_doblemente_enlazada