sábado, 15 de julio de 2017

Listas simplemente enlazadas (Linked List)

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.

Listas simplemente enlazadas


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();
        }
    }

2 comentarios:

  1. gracias por el aporte. si fuera doblemente enlazada como seria?

    ResponderEliminar
  2. igual pero con un puntero al dato siguiente y otro al dato anterior
    https://es.wikipedia.org/wiki/Lista_doblemente_enlazada

    ResponderEliminar