LISTAS ENLAZADAS ESTRUCTURA DATOS C#

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

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

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. Viajes y turismo

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

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 

LISTAS ENLAZADAS ESTRUCTURA DATOS C#

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

adsl

es

https://adsltodo.es/static/images/adsl-listas-enlazadas-estructura-datos-c-1755-0.jpg

2024-11-19

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 [email protected] y retiraremos este contenido inmediatamente