LISTAS ENLAZADAS ESTRUCTURA DATOS C#

Todo sobre Apple, Mac e IphoneNoticias sobre apple,mac, osx, iphone,ipad,apple watch, juegos para mac y appletv

 

LISTAS ENLAZADAS

Una lista enlazada la constituye una colecci贸n lineal de elementos, llamados nodos, donde el orden de los mismos se establece mediante punteros. Cada nodo se divide en dos partes: una primera que contiene la informaci贸n asociada al elemento, y una segunda parte, llamada campo de enlace o campo al siguiente puntero, que contiene la direcci贸n del siguiente nodo de la lista.

Una lista enlazada es una colecci贸n lineal de elementos donde el orden de los mismos se establece mediante punteros. La idea b谩sica es que cada componente de la lista incluya un puntero que indique donde puede encontrarse el siguiente componente por lo que el orden relativo de estos puede ser f谩cilmente alterado modificando los punteros lo que permite, a su vez, a帽adir o suprimir elementos de la lista.

Una lista enlazada es una serie de nodos, conectados entre s铆 a trav茅s de una referencia, en donde se almacena la informaci贸n de los elementos de la lista. Por lo tanto, los nodos de una lista enlazada se componen de dos partes principales:

Ventajas de usar listas: Las listas son din谩micas, es decir, podemos almacenar en ellas tantos elementos como necesitemos, siempre y cuando haya espacio suficiente espacio en memoria. Al insertar un elemento en la lista, la operaci贸n tiene un tiempo constante independientemente de la posici贸n en la que se inserte, solo se debe crear el nodo y modificar los enlaces. Esto no es as铆 en los arreglos, ya que si el elemento lo insertamos al inicio o en medio, tenemos un tiempo lineal debido a que se tienen que mover todos los elementos que se encuentran a la derecha de la posici贸n donde lo vamos a insertar y despu茅s insertar el elemento en dicha posici贸n; solo al insertar al final del arreglo se obtienen tiempos constantes. Al eliminar un elemento paso lo mismo que se menciono en el punto anterior.

Desventajas de usar listas:

El acceso a un elemento es m谩s lento, debido a que la informaci贸n no est谩 en posiciones contiguas de memoria, por lo que no podemos acceder a un elemento con base en su posici贸n como se hace en los arreglos.

REPRESENTACION DE LISTAS ENLAZADAS EN MEMORIA

Sea LISTA una lista enlazada, salvo que se indique lo contrario. Almacenaremos LISTA en memoria de la forma siguiente. Como m铆nimo, LISTA estar谩 compuesta por dos arrays lineales, a los que llamaremos INFO y ENLACE, tales que INFO [K] y ENLACE [K] contienen la parte de informaci贸n y el campo de puntero de cada nodo de LISTA respectivamente. Necesitamos tambi茅n una variable especial llamada COMIENZO que contiene la posici贸n ocupada por el primer elemento de la lista, y una marca especial NULO que indica el final de la misma. Puesto que los 铆ndices de los arrays INFO y ENLACE ser谩n habitualmente positivos, el valor NULO ser谩 el -999, salvo que digamos lo contrario.

El siguiente ejemplo muestra la representaci贸n memoria de una lista enlazada en la que cada nodo de la lista contiene un 煤nico car谩cter. Podemos obtener la lista de caracteres o, en otras palabras, la cadena de la forma siguiente:

COMIENZO = 9, luego INFO [9] = N primer car谩cter.

ENLACE [9] = 3, luego INFO [3] = 0 segundo car谩cter.

ENLACE [3] = 6, luego INFO [6] = (car谩cter blanco) tercer car谩cter.

ENLACE [6] = 11, luego INFO [11] = E cuarto car谩cter.

ENLACE [11] = 7, luego INFO [7] = X quinto car谩cter.

ENLACE [7] = 10, luego INFO [10] = I sexto car谩cter.

ENLACE [10] = 4, luego INFO [4] = T s茅ptimo car谩cter.

ENLACE [4] = -999 valor nulo, luego termina la lista.

FORMA PRINCIPAL DE LA LISTA ENLAZADA

Codigo:

聽using System;using System.Collections.Generic;using System.ComponentModel;using System.Data;using System.Drawing;using System.Text;using System.Windows.Forms;聽namespace WindowsApplication1{ public partial class Listas : Form { public Listas() { InitializeComponent(); } public static int[] enlace = new int[10] { 2, 3, 4, 0, -999, 6, 7, 8, 9, -999 }; public static string[] alumno = new string[10] { "Jose", "Ana", "Rosa", "Beto", "zeta", "", "", "", "", "" }; public static int comienzo = 1; public static int disponible = 5; private void cmdInsercion_Click(object sender, EventArgs e) { Insercion ins = new Insercion(); ins.Show(); }聽 private void cmdRecorrido_Click(object sender, EventArgs e) { Recorrer rec = new Recorrer(); rec.Show(); }聽 private void cmdBusqueda_Click(object sender, EventArgs e) { Busqueda bus = new Busqueda(); bus.Show(); }聽 private void cmdEliminacion_Click(object sender, EventArgs e) { Eliminacion eli = new Eliminacion(); eli.Show(); } }}

Corrida

:estructura_datos_csharp:listas_enlazadas.jpg

RECORRIDO DE UNA LISTA ENLAZADA

Sea la lista enlazada, almacenada en memoria mediante dos arrays INFO y ENLACE. Adicionalmente definimos la variable COMIENZO que apunta al primer elemento de la lista y suponemos que el 煤ltimo nodo de la lista contiene en su campo ENLACE el valor NULO. Supongamos que queremos recorrer LISTA para procesar cada uno de sus nodos exactamente una vez. A continuaci贸n te mostrare el algoritmo que realiza esta tarea y que utilizaremos en otras aplicaciones.

Nuestro algoritmo utiliza una variable puntero PTR que apunta siempre al nodo procesado en cada momento. Por ello ENLACE [PTR] indica el siguiente nodo a ser procesado. De esta forma la asignaci贸n PTR:= ENLACE [PTR] Tiene el efecto de mover el puntero al siguiente nodo de la lista.

La descripci贸n del algoritmo es la siguiente. Inicializamos PTR a COMIENZO. A continuaci贸n procesamos INFO [PTR], es decir, la informaci贸n del primer nodo. En el paso siguiente actualizamos PTR mediante la asignaci贸n PRT: = ENLACE [PTR], lo que hace que PTR apunte ahora al segundo nodo. Nuevamente tratamos de la informaci贸n contenida en INFO [PTR] (segundo nodo) y tras esto volvemos a actulizar PTR y procesamos INFO [PTR], y asi sucesivamente. Este proceso de actualizacion y procesamiento continuara hasta que en una de las actualizaciones de PTR obtengamos que PTR = NULO, que marca el final de la lista.

Una representaci贸n formal de algoritmo es la siguiente.

Algoritmo: Recorrido de una lista enlazada.

Sea LISTA una lista enlazada que almacenamos en memoria. El algoritmo recorre LISTA realizando la operaci贸n PROCESO a cada elemento de LISTA. La variable PTR, apunta en cada momento al nodo que se esta tratando.

  1. PTR: = COMIENZO. [inicializa el puntero].
  2. repetir pasos 3 y 4 mientras PTR != 0.
  3. aplicar PROCESO a INFO [PTR].
  4. PTR: = ENLACE [PTR]. [PTR apunta ahora al siguiente nodo]. [fin del ciclo paso 2].
  5. salir.

Codigo:

聽using System;using System.Collections.Generic;using System.ComponentModel;using System.Data;using System.Drawing;using System.Text;using System.Windows.Forms;聽namespace WindowsApplication1{ public partial class Recorrer : Form { public Recorrer() { InitializeComponent(); Recorrido(); }聽 private void cmdRecorrer_Click(object sender, EventArgs e) { listBox1.Items.Clear(); Recorrido(); }聽 private void Recorrido() { int ptr = Listas.comienzo; while (ptr != -999) { listBox1.Items.Add(Listas.alumno[ptr]); ptr = Listas.enlace[ptr]; } } private void button1_Click(object sender, EventArgs e) { this.Close(); } }}

Corrida

:estructura_datos_csharp:listas_recorrido.jpg

BUSQUEDA EN UNA LISTA ENLAZADA

Sea LISTA una lista enlazada, almacenada en memoria. En esta seccion discutimos dos algoritmos de b煤squeda que localizan la posici贸n del nodo (LUG) en el cual un elemento dado (ELEMENTO) aparece por primera vez en la lista. El primer algoritmo no necesita que la lista este ordenada, mientras que el segundo si lo exige.

Si ELEMENTO es una valor de clave y buscamos en el archivo para encontrar el registro que lo contiene, este solo puede aparecer una vez en la lista.

Lista no ordenadas

Supongamos que los datos de lista no estan ordenados (necesariamente). En este caso podremos localizar ELEMENTO sin mas que recorrer LISTA utilizando el puntero PTR y comparando ELEMENTO con el contenido INFO [PTR] de cada nodo. Cada vez que actualicemos PTR mediante la asignaci贸n PTR: = ENLACE [PTR], necesitamos dos comprobaciones. Primero necesitamos ver si hemos alcanzado el final de la lista, es decir comprobamos si PTR = NULO, si no, entonces comprobamos si INFO [PTR] = ELEMENTO.

Las dos comprobaciones no podemos realizarlas simult谩neamente, puesto que si PTR = NULO no existira INFO [PTR]. De acuerdo con esto utilizamos la primera comparaci贸n para controlar la ejecuci贸n de un ciclo y realizamos la segunda comparaci贸n dentro de este.

Algoritmo: BUSQ(INFO, ENLACE, COMIENZO, ELEMENTO, LUG)

LISTA es una lista enlazada almacenada en memoria. el algoritmo encuentra la posicion LUG del nodo donde ELEMENTO aparece por primera vez en lista y devuelve LUG = NULO.

  1. PTR: = COMIENZO.
  2. repetir paso 3 mientras PTR != NULO:
  3. si ELEMENTO = INFO[PTR], entonces: LUG: = PTR y salir.
  4. si no: PTR: = ENLACE [PTR]. [PTR apunta ahora al nodo siguiente].
  5. [final de la estructura condicional].
  6. [final del ciclo del paso 2].
  7. [la busqueda es fallida]. LUG: = NULO.
  8. salir

Lista ordenada

Supongamos que los datos de LISTA estan ordenados. de nuevo buscamos ELEMENTO en la lista recorriendo la misma utilizando una variable puntero y comparando ELEMENTO con el contenido de INFO[PTR] nodo a nodo. en este caso, sin embargo, podremos finalizar la busqueda una vez que ELEMENTO sea mayor que INFO[PTR].

Algoritmo: BUSQ(INFO, ENLACE, COMIENZO, ELEMENTO, LUG)

LISTA es una lista ordenada que se encuentra en memoria. el algoritmo encuentra la posicion LUG del nodo donde se encuentra por pirmera vez ELEMENTO o bien devuelve LUG = NULO.

  1. PTR:= COMIENZO.
  2. repetir paso 3 mientras PTR != NULO:
  3. si ELEMENTO
  4. PTR: = ENLACE [PTR]. [PTR apunta al siguiente nodo].
  5. si no, si ELEMENTO = INFO[PTR], entonces:
  6. LUG = PTR y salir. [la busqueda es satisfactoria].
  7. si no: LUG: = NULO y salir. [ELEMENTO es mayor que INFO[PTR]].
  8. [final de la estructura condicional]
  9. [final del ciclo del paso 2]
  10. LUG: = NULO.
  11. salir.

Codigo:

聽using System;using System.Collections.Generic;using System.ComponentModel;using System.Data;using System.Drawing;using System.Text;using System.Windows.Forms;聽namespace WindowsApplication1{ public partial class Busqueda : Form { public Busqueda() { InitializeComponent(); }聽 private void cmdBuscar_Click(object sender, EventArgs e) { string elemento = txtbuscador.Text.ToString(); int lug = -999; int ptr = Listas.comienzo; if (ptr == -999) MessageBox.Show("Lista vacia", "Error"); while (ptr != -999) { if (Listas.alumno[ptr] == elemento) { lug = ptr; MessageBox.Show("Elemento encontrado en posicion: " + lug.ToString(), "Elemento Encontrado"); txtbuscador.Clear(); } else ptr = Listas.enlace[ptr]; } if (lug == -999) MessageBox.Show("Elemento no encontrado", "Error"); }聽 private void button1_Click(object sender, EventArgs e) { this.Hide(); } }}

Corrida

:estructura_datos_csharp:listas_busqueda.jpg

INSERCION EN UNA LISTA ENLAZADA

Sea LISTA una lista enlazada en la que los nodos A y B ocupan posiciones sucesivas en el orden impuesto en la lista. Supongamos que queremos insertar en ella un nodo N que debe ocupar un lugar entre A y B. Despu茅s de la operaci贸n el nodo A apuntara al nodo N y este apuntara al nodo B, es decir, el nodo al que apuntaba antes A.

Algoritmo de insercion

tres son las situaciones mas comunes que nos encontraremos cuando insertamos nodos en una lista. Primero cuando queremos insertar un nodo al principio de la lista, segundo cuando queramos insertar un nodo detras de un detreminado, y tercero, cuando insertamos un nodo en una lista previamente ordenada. A continuacion discutimos los algoritmos que llevan a cabo estas tareas suponiendo que la lista esta almacenada en memoria en la forma LISTA(INFO, ENLACE, COMIENZO, DISP) y que la variable ELEMENTO contiene la informacion que debe incorporarse a la lista.

Puesto que nuestros algoritmos de insercion utilizaran nodos de la lista de nodos disponibles, todos ellos deben incluir los siguientes pasos:

  • Estudiar si existe espacio libre en la lista de espacio disponible. Si no es asi, es decir, si DISPONIBLE = NULO, el algoritmo debe imprimir el mensaje OVERFLOW.
  • Extraer el primer nodo de la lista de disponible. Si utilizamos la variable Nuevo, esta operacion puede realizarse mediante dos asignaciones (en este orden) NUEVO: = DISP. DISP: = ENLACE[DISP].
  • Incorporar la informacion a insertar en el nodo recien obtenido, es decir: INFO[NUEVO] = ELEMENTO.

Insercion al principio de una lista

Supongamos que nuestra lista no esta ordenada ni existe ninguna razon por la cual cualquier nodo que insertemos deba ocupar una determinada posicion. En este caso lo mas sencillo sera insertar el nuevo nodo al comienzo de la misma. Un algoritmo que realiza esta operacion es el siguiente.

Algoritmo: INSPRIN(INFO, ENLACE, COMIENZO, DISP, ELEMENTO)

El algoritmo coloca ELEMENTO como primer componente de la lista.

  1. [Overflow] si DISP = NULO, entonces: Escribir: OVERFLOW y salir.
  2. [extrae el primer nodo de la lista DISP].
  3. NUEVO: = DISP y DISP: = ENLACE[DISP].
  4. INFO[NUEVO]: = ELEMENTO. [copia el dato en el nodo].
  5. ENLACE[NUEVO]: = COMIENZO. [el nuevo nodo apunta ahora al que ocupa antes la primera posicion].
  6. COMIENZO: = NUEVO. [COMIENZO apunta ahora al elemento que ocupa la primera posicion de la lista].
  7. Salir.

Insercion a continuacion de un nodo determinado

Supongamos en este caso que se nos da un valor LUG que o bien representa la localizacion de un nodo A determinado o bien LUG = NULO. El algoritmo siguiente inserta ELEMENTO en la lista a continuacion de A o bien coloca ELEMENTO como primer componente de la lista si LUG = NULO.

Sea N el nuevo nodo (cuya posicion es NUEVO). Si LUG = NULO, entonces el nodo se coloca al comienzo de la lista. En otro caso hacemos que N apunte al nodo B (que originalmente seguia a A). El proceso implica las siguientes operaciones:

ENLACE[NUEVO]: = ENLACE[LUG]

despues del cual N apunta a B y

ENLACE[LUG]: = NUEVO

tras el cual A apunta al nodo N.

Algoritmo: INSLUG(INFO, ENLACE, COMIENZO, DISP, LUG, ELEMENTO)

el algoritmo inserta ELEMENTO a continuacion del nodo que ocupa la posicion LUG o coloca ELEMENTO como primer nodo si LUG=NULO

  1. [Overflow] Si DISP = NULO, entonces: escribir: OVERFLOW y salir.
  2. [Extrae el primer nodo de la lista de disponibles]
  3. NUEVO: = DISP y DISP: = ENLACE[DISP].
  4. INFO[NUEVO]: = ELEMENTO. [copia el dato en el nodo obtenido].
  5. Si LUG = NULO, entonces [Lo inserta como primer nodo].
  6. ENLACE[NUEVO]: = COMIENZO y COMIENZO: = NUEVO.
  7. Si no: [Inserta detras del nodo de posicion LUG].
  8. ENLACE[NUEVO]: = ENLACE[LUG] y ENLACE[LUG]: = NUEVO.
  9. [Final de la estructura condicional]
  10. Salir.

Insercion de una lista enlazada y ordenada

Supongamos que queremos insertar ELEMENTO en una lista enlazada y ordenada y que ELEMENTO cumple que INFO(a) ELEMENTO, o en otras palabras, la busqueda finaliza cuando ELEMENTO 鈬 INFO[PTR].

Una representacion formal del procedimiento es el siguiente. En dicho procedimiento se comtemplan por separado los casos en que la lista esta vacia o bien cuando ELEMENTO

Procedimiento: ENCA (INFO, ENLACE, COMIENZO, ELEMENTO, LUG)

El procedimiento encuentra la posicion LUG del ultimo nodo para el que INFO[LUG]

  1. [驴Lista vacia?] Si COMIENZO = NULO, entonces: LUG = NULO y retornar.
  2. [驴caso especial?] Si ELEMENTO
  3. AUX: = COMIENZO y PTR: = ENLACE[COMIENZO]. [Inicializamos los punteros].
  4. Repetir pasos 5 y 6 mientras PTR != NULO.
  5. Si ELEMENTO
  6. LUG: = AUX y retornar.
  7. [Final de la estructura condicionla].
  8. AUX: = PTR y PTR: = ENLACE[PTR]. [Actualiza los punteros].
  9. LUG: = AUX.
  10. Salir.

Despues de esto ya tenemos las herramientas necesarias para dise帽ar un algoritmo que nos inserte ELEMENTO en una lista enlazada.

Algoritmo: INSERT(INFO, ENLACE, COMIENZO, DISP, ELEMENTO)

El algoritmo inserta ELEMENTO en una lista enlazada ordenada.

  1. [Utilizamos el procedimiento 6 para encontrar la posicion del nodo que precedera a ELEMENTO.]
  2. Llamar ENCA (INFO, ENLACE, COMIENZO, ELEMENTO, LUG)
  3. [Utilizaremos el algoritmo 5 para insertar ELEMENTO a continuacion del nodo que ocupa la posicion LUG.]
  4. Llamar INSLUG(INFO, ENLACE, COMIENZO, DISP, LUG, ELEMENTO)
  5. Salir.

Codigo:

聽using System;using System.Collections.Generic;using System.ComponentModel;using System.Data;using System.Drawing;using System.Text;using System.Windows.Forms;聽namespace WindowsApplication1{ public partial class Insercion : Form { public Insercion() { InitializeComponent(); }聽聽 private void cdmInserta_Click(object sender, EventArgs e) { string elemento = txtInser.Text; txtInser.Clear(); if (Listas.disponible == -999) { MessageBox.Show("Lista llena", "Error", MessageBoxButtons.OK); } else { int anterior = -999; int ptr = Listas.comienzo; int i = 0,nuevo; nuevo = Listas.disponible; bool aux = false; Listas.disponible = Listas.enlace[nuevo]; Listas.alumno[nuevo] = elemento; while (ptr != -999 && aux == false) { if (Listas.alumno[ptr].Length 

M脕S INFORMACI脫N

El contenido original se encuentra en https://programacionfacil.com/estructura_datos_csharp/listas_enlazadas/
Todos los derechos reservados para el autor del contenido original (en el enlace de la linea superior)
Si crees que alguno de los contenidos (texto, imagenes o multimedia) en esta p谩gina infringe tus derechos relativos a propiedad intelectual, marcas registradas o cualquier otro de tus derechos, por favor ponte en contacto con nosotros en el mail bitelchux@yahoo.es y retiraremos este contenido inmediatamente