Listas Enlazadas
- Concepto
En una lista enlazada, cada elemento apunta al siguiente excepto el último que no tiene sucesor y el valor del enlace es null. Por ello los elementos son registros que contienen el dato a almacenar y un enlace al siguiente elemento. Los elementos de una lista, suelen recibir también el nombre de nodos de la lista.
- Caracterizticas
Una lista enlazada es un tipo de dato auto-referenciado porque contienen un puntero o link a otro dato del mismo tipo. Las listas enlazadas permiten inserciones y eliminación de nodos en cualquier punto de la lista en tiempo constante (suponiendo que dicho punto está previamente identificado o localizado), pero no permiten un acceso aleatorio. Existen diferentes tipos de listas enlazadas: Lista Enlazadas Simples, Listas Doblemente Enlazadas, Listas Enlazadas Circulares y Listas Enlazadas Doblemente Circulares.
Las listas enlazadas pueden ser implementadas en muchos lenguajes. Lenguajes tales como Lisp y Scheme tiene estructuras de datos ya construidas, junto con operaciones para acceder a las listas enlazadas. Lenguajes imperativos u orientados a objetos tales como C o C++ y Java, respectivamente, disponen de referencias para crear listas enlazadas.
- Operaciones
- Recorrido. Esta operación consiste en visitar cada uno de los nodos que forman la lista . Para recorrer todos los nodos de la lista, se comienza con el primero, se toma el valor del campo liga para avanzar al segundo nodo, el campo liga de este nodo nos dará la dirección del tercer nodo, y así sucesivamente.
- Inserción. Esta operación consiste en agregar un nuevo nodo a la lista. Para esta operación se pueden considerar tres casos:
- Insertar un nodo al inicio.
- Insertar un nodo antes o después de cierto nodo.
- Insertar un nodo al final.
- Borrado. La operación de borrado consiste en quitar un nodo de la lista, redefiniendo las ligas que correspondan. Se pueden presentar cuatro casos:
- Eliminar el primer nodo.
- Eliminar el último nodo.
- Eliminar un nodo con cierta información.
- Eliminar el nodo anterior o posterior al nodo cierta con información.
- Búsqueda. Esta operación consiste en visitar cada uno de los nodos, tomando al campo liga como puntero al siguiente nodo a visitar.
- Programa
/*
* Lista Simplemente enlazada.
*
*/ /**
*
* @author Pain
*/
//Clase Nodo. Utiliza el enlace llamado nodoDer o nodo derecho y el valor a introducir.
public class Nodo {
Nodo nodoDer;
int dato;
public Nodo(int dato) {
this.dato = dato;
this.nodoDer = null;
}
}
/*
* Clase de Lista enlazada y metodos de agregar al final y borrar del mismo, asi como mostrar tamaño y visualizar lista.
*
*/
import javax.swing.JOptionPane;
/**
*
* @author Pain
*/
public class ListaS {
private Nodo primero;
private Nodo ultimo;
private int tamano;
public ListaS() {
this.primero = null;
this.ultimo = null;
this.tamano = 0;
}
//Metodo utilizado para denotar que la lista se encuentra vacia.
public boolean siVacio() {
return (this.primero == null);
}
//Metodo para agregar al final de la lista.
public ListaS addLast(int dato) {
if(siVacio()) {
Nodo nuevo = new Nodo(dato);
primero = nuevo;
ultimo = nuevo;
nuevo.nodoDer = nuevo;
}
else {
Nodo nuevo = new Nodo(dato);
nuevo.nodoDer = null;
ultimo.nodoDer = nuevo;
ultimo = nuevo;
}
this.tamano++;
return this;
}
//Metodo para borrar al final de la lista.
public Nodo deleteLast() {
Nodo eliminar = null;
if(siVacio()) {
JOptionPane.showMessageDialog(null, "La lista se encuentra vacia");
return null;
}
if(primero == ultimo) {
primero = null;
ultimo = null;
}
else {
Nodo actual = primero;
while(actual.nodoDer != ultimo) {
actual = actual.nodoDer;
}
eliminar = actual.nodoDer;
actual.nodoDer = null;
ultimo = actual;
}
this.tamano--;
return eliminar;
}
//Metodo que imprime el tamaño de la lista.
public void tamano() {
JOptionPane.showMessageDialog(null, "El tamaño es:\n " + this.tamano);
}
//Metodo que imprime la lista y los valores ingresados.
public void imprimir() {
if(tamano != 0) {
Nodo temp = primero;
String str = "";
for(int i = 0; i < this.tamano; i++) {
str = str + temp.dato + "\n";
temp = temp.nodoDer;
}
JOptionPane.showMessageDialog(null, str);
}
}
}
* Lista Simplemente enlazada.
*
*/ /**
*
* @author Pain
*/
//Clase Nodo. Utiliza el enlace llamado nodoDer o nodo derecho y el valor a introducir.
public class Nodo {
Nodo nodoDer;
int dato;
public Nodo(int dato) {
this.dato = dato;
this.nodoDer = null;
}
}
/*
* Clase de Lista enlazada y metodos de agregar al final y borrar del mismo, asi como mostrar tamaño y visualizar lista.
*
*/
import javax.swing.JOptionPane;
/**
*
* @author Pain
*/
public class ListaS {
private Nodo primero;
private Nodo ultimo;
private int tamano;
public ListaS() {
this.primero = null;
this.ultimo = null;
this.tamano = 0;
}
//Metodo utilizado para denotar que la lista se encuentra vacia.
public boolean siVacio() {
return (this.primero == null);
}
//Metodo para agregar al final de la lista.
public ListaS addLast(int dato) {
if(siVacio()) {
Nodo nuevo = new Nodo(dato);
primero = nuevo;
ultimo = nuevo;
nuevo.nodoDer = nuevo;
}
else {
Nodo nuevo = new Nodo(dato);
nuevo.nodoDer = null;
ultimo.nodoDer = nuevo;
ultimo = nuevo;
}
this.tamano++;
return this;
}
//Metodo para borrar al final de la lista.
public Nodo deleteLast() {
Nodo eliminar = null;
if(siVacio()) {
JOptionPane.showMessageDialog(null, "La lista se encuentra vacia");
return null;
}
if(primero == ultimo) {
primero = null;
ultimo = null;
}
else {
Nodo actual = primero;
while(actual.nodoDer != ultimo) {
actual = actual.nodoDer;
}
eliminar = actual.nodoDer;
actual.nodoDer = null;
ultimo = actual;
}
this.tamano--;
return eliminar;
}
//Metodo que imprime el tamaño de la lista.
public void tamano() {
JOptionPane.showMessageDialog(null, "El tamaño es:\n " + this.tamano);
}
//Metodo que imprime la lista y los valores ingresados.
public void imprimir() {
if(tamano != 0) {
Nodo temp = primero;
String str = "";
for(int i = 0; i < this.tamano; i++) {
str = str + temp.dato + "\n";
temp = temp.nodoDer;
}
JOptionPane.showMessageDialog(null, str);
}
}
}
- Videos
- Bibliografia
http://sistemas.itlp.edu.mx/tutoriales/estru1/42.htm
http://www.calcifer.org/documentos/librognome/glib-lists-queues.html
http://www.javamexico.org/blogs/pain5610/estructura_de_datos_java_listas_simplemente_enlazadas_primer_aporte
---------------------------------------------------------------------------------------------------------
Actualizado al 22 de Septiembre de 2011
---------------------------------------------------------------------------------------------------------
Listas Enlazadas Simples en Java
Tema de exposición
Conceptos desde diferentes aspectos, los dos tratan de explicar las listas simples:
(1) Una lista de enlace simple es una lista enlazada de nodos, donde cada nodo tiene un único campo de enlace. Una variable de referencia contiene una referencia al primer nodo, cada nodo (excepto el último) enlaza con el nodo siguiente, y el enlace del último nodo contiene null para indicar el final de la lista. Aunque normalmente a la variable de referencia se la suele llamar top, usted puede elegir el nombre que quiera.
Consiste en una secuencia de nodos, en los que se guardan campos de datos arbitrarios y una o dos referencias (punteros) al nodo anterior o posterior. El principal beneficio de las listas enlazadas respecto a los array convencionales es que el orden de los elementos enlazados puede ser diferente al orden de almacenamiento en la memoria o el disco, permitiendo que el orden de recorrido de la lista sea diferente al de almacenamiento.
(2) Una lista enlazada es un tipo de dato auto-referenciado porque contienen un puntero o link a otro dato del mismo tipo. Las listas enlazadas permiten inserciones y eliminación de nodos en cualquier punto de la lista en tiempo constante (suponiendo que dicho punto está previamente identificado o localizado), pero no permiten un acceso aleatorio. Existen diferentes tipos de listas enlazadas: Lista Enlazadas Simples, Listas Doblemente Enlazadas, Listas Enlazadas Circulares y Listas Enlazadas Doblemente Circulares.
Las listas enlazadas pueden ser implementadas en muchos lenguajes. Lenguajes tales como Lisp y Scheme tiene estructuras de datos ya construidas, junto con operaciones para acceder a las listas enlazadas. Lenguajes imperativos u orientados a objetos tales como C o C++ y Java, respectivamente, disponen de referencias para crear listas enlazadas.
Cómo funciona una lista
Para crear una lista necesitamos recordar nuestros conocimientos sobre estructuras y asignación dinámica de memoria. Vamos a desarrollar este tema creando una sencilla agenda que contiene el nombre y el número de teléfono.
Una lista enlazada simple necesita una estructura con varios campos, los campos que contienen los datos necesarios (nombre y teléfono) y otro campo que contiene un puntero a la propia estructura. Este puntero se usa para saber dónde está el siguiente elemento de la lista, para saber la posición en memoria del siguiente elemento.
Una lista enlazada simple necesita una estructura con varios campos, los campos que contienen los datos necesarios (nombre y teléfono) y otro campo que contiene un puntero a la propia estructura. Este puntero se usa para saber dónde está el siguiente elemento de la lista, para saber la posición en memoria del siguiente elemento.
Operaciones en listas enlazadas
Algunas de las operaciones básicas que pueden realizarse en una lista enlazada son:
* Crear una lista
* Buscar un elemento en la lista
* Insertar un elemento al final de la lista
* Eliminar una elemento de la lista
Breve explicación en imagenes:
Esta imagen representa en enlace que hay entre la cabeza y los nodos de los demás, mostrando al final de cada nodo, un valor nulo, en el final se muestra que ya no hay valor y solo corresponde un espacio nulo, en espera de otro nodo.
En esta se muestra la eliminación de un nodo al medio de la lista, mostrando que al eliminar el nodo, solo se abren los eslabones y se cierran después de la eliminacion para que la lista siga corriendo, y por lo tanto siga haciendo su trabajo.
Aquí el ejemplo en código, para ayudar al entendimiento de estas:
package borrarNodo;
// SLLDelDemo.java
class SLLDelDemo {
static class Node {
String name;
Node next;
}
public static void main (String [] args) {
// Build Figure 6's singly linked list (i.e., B A D C)
Node top = new Node ();
top.name = "C";
top.next = null;
Node temp = new Node ();
temp.name = "D";
temp.next = top;
top = temp;
temp = new Node ();
temp.name = "A";
temp.next = top;
top = temp;
temp = new Node ();
temp.name = "B";
temp.next = top;
top = temp;
dump ("Initial singly-linked list", top);
// 1. Delete the first node
top = top.next;
dump ("After first node deletion", top);
// Put back B
temp = new Node ();
temp.name = "B";
temp.next = top;
top = temp;
// 1. Delete the first node
top = top.next;
dump ("After first node deletion", top);
// Put back B
temp = new Node ();
temp.name = "B";
temp.next = top;
top = temp;
// 2. Delete any node but the first node
temp = top;
while (temp.name.equals ("A") == false)
temp = temp.next;
temp.next = temp.next.next;
dump ("After D node deletion", top);
}
static void dump (String msg, Node topNode) {
System.out.print (msg + " ");
while (topNode != null) {
System.out.print (topNode.name + " ");
topNode = topNode.next;
}
System.out.println ();
}
}
Bibliografia:
Descarga de Presentación de Exposición
http://www.megaupload.com/?d=JGOU954C
Tipos de Pilas
Pila Estatica
package pila;
import java.util.Scanner;
public class PilaEstatica {
public static void main(String[] args) {
int dato;
int pila[]=new int [5];
Scanner captura= new Scanner(System.in);
for(int tope=0; tope<4; tope++){
System.out.println("Prop. Datos Para Pila: ");
dato= captura.nextInt();
pila[tope]=dato;
}
for (int tope=4; tope>=0;tope--)
System.out.println("La Pila Tine Los Sig. Datos: " + pila[tope]);
}
}
import java.util.Scanner;
public class PilaEstatica {
public static void main(String[] args) {
int dato;
int pila[]=new int [5];
Scanner captura= new Scanner(System.in);
for(int tope=0; tope<4; tope++){
System.out.println("Prop. Datos Para Pila: ");
dato= captura.nextInt();
pila[tope]=dato;
}
for (int tope=4; tope>=0;tope--)
System.out.println("La Pila Tine Los Sig. Datos: " + pila[tope]);
}
}
Pila (Programa)
package listaligada;
import java.util.*;
public class ListaLigada {
public static void main (String args[])
{
Scanner leer = new Scanner(System.in);
int num;
int op;
LinkedList lista = new LinkedList();
do{
System.out.println( "\t Menú \t" );
System.out.println( "Operaciones con listas" );
System.out.println( "1.- Insertar al principio" );
System.out.println( "2.- Insertar al final" );
System.out.println( "3.- Borrar al principio" );
System.out.println( "4.- Borrar al final" );
System.out.println( "5.- Mostrar la lista" );
System.out.println( "6.- Borrar toda la lista" );
System.out.println( "7.- Salir" );
System.out.println( "\n" );
System.out.println( "Elija la operación que desee" );
op = leer.nextInt();
switch(op){
case 1:
System.out.println( "Insertar Numero" );
num = leer.nextInt();
lista.addFirst(num);
break;
case 2:
System.out.println("Insertar Numero");
num=leer.nextInt();
lista.addLast(num);
break;
case 3:
System.out.println( "Borrar Al Prinicipio" );
lista.removeFirst();
break;
case 4:
System.out.println( "Borrar Al Final" );
lista.removeLast();
break;
case 5:
System.out.println( "" );
List lista2 = new ArrayList(lista);
Iterator it = lista2.iterator();
while (it.hasNext()){
System.out.println(it.next()+"");
}
break;
case 6:
System.out.println( "Se borraran todos los elementos de la lista" );
lista.clear();
break;
case 7:
System.out.println( "Ahorita" );
break;
}
}
while( op != 6 );
}
}
import java.util.*;
public class ListaLigada {
public static void main (String args[])
{
Scanner leer = new Scanner(System.in);
int num;
int op;
LinkedList lista = new LinkedList();
do{
System.out.println( "\t Menú \t" );
System.out.println( "Operaciones con listas" );
System.out.println( "1.- Insertar al principio" );
System.out.println( "2.- Insertar al final" );
System.out.println( "3.- Borrar al principio" );
System.out.println( "4.- Borrar al final" );
System.out.println( "5.- Mostrar la lista" );
System.out.println( "6.- Borrar toda la lista" );
System.out.println( "7.- Salir" );
System.out.println( "\n" );
System.out.println( "Elija la operación que desee" );
op = leer.nextInt();
switch(op){
case 1:
System.out.println( "Insertar Numero" );
num = leer.nextInt();
lista.addFirst(num);
break;
case 2:
System.out.println("Insertar Numero");
num=leer.nextInt();
lista.addLast(num);
break;
case 3:
System.out.println( "Borrar Al Prinicipio" );
lista.removeFirst();
break;
case 4:
System.out.println( "Borrar Al Final" );
lista.removeLast();
break;
case 5:
System.out.println( "" );
List lista2 = new ArrayList(lista);
Iterator it = lista2.iterator();
while (it.hasNext()){
System.out.println(it.next()+"");
}
break;
case 6:
System.out.println( "Se borraran todos los elementos de la lista" );
lista.clear();
break;
case 7:
System.out.println( "Ahorita" );
break;
}
}
while( op != 6 );
}
}
Pila (Tipos)
Iniciar pila.
| Operador | Funciones asociadas. |
|---|---|
| Iniciar pila. | GQueue* g_queue_new (void) |
| Pila vacía. | gboolean g_queue_is_empty (GQueue* queue) |
| Consultar pila. | gpointer g_queue_peek_head (GQueue* queue) |
| Meter. | void g_queue_push_head (GQueue* queue, gpointer data) |
| Sacar. | gpointer g_queue_pop_head (GQueue* queue) |
| Vaciar pila. | void g_queue_free (GQueue* queue) |
El operador "iniciar pila" es el encargado de crear una nueva pila y inicializarla al estado de pila vacía.
Definicion de Pila
Son aquellas que solo tiene 2 operaciones, Push(Inserción) y Pop(Eliminación) la cual solo se puede efectuar por un extremo llamado Top. Sin Embargo se le pueden aplicar todas las operaciónes al igual que a las listas.
Tiempo De Ejecucion
Pila basada en la asignación de memoria y Pila máquina. Una serie de lenguajes de programación están orientadas a la pila, lo que significa que la mayoría definen operaciones básicas (añadir dos números, la impresión de un carácter) cogiendo sus argumentos de la pila, y realizando de nuevo los valores de retorno en la pila. Por ejemplo, PostScript tiene una pila de retorno y un operando de pila, y también tiene un montón de gráficos estado y un diccionario de pila. Forth utiliza dos pilas, una para pasar argumentos y una subrutina de direcciones de retorno. El uso de una pila de retorno es muy común, pero el uso poco habitual de un argumento para una pila legible para humanos es el lenguaje de programación Forth razón que se denomina una pila basada en el idioma.
Muchas máquinas virtuales también están orientadas hacia la pila, incluida la p-código máquina y la máquina virtual Java.
Casi todos los entornos de computación de tiempo de ejecución de memoria utilizan una pila especial PILA para tener información sobre la llamada de un procedimiento o función y de la anidación con el fin de cambiar al contexto de la llamada a restaurar cuando la llamada termina. Ellos siguen un protocolo de tiempo de ejecución entre el que llama y el llamado para guardar los argumentos y el valor de retorno en la pila. Pila es una forma importante de apoyar llamadas anidadas o a funciones recursivas. Este tipo de pila se utiliza implícitamente por el compilador para apoyar CALL y RETURN estados (o sus equivalentes), y no es manipulada directamente por el programador.
Algunos lenguajes de programación utilizar la pila para almacenar datos que son locales a un procedimiento. El espacio para los datos locales se asigna a los temas de la pila cuando el procedimiento se introduce, y son borradas cuando el procedimiento termina. El lenguaje de programación C es generalmente aplicado de esta manera. Utilizando la misma pila de los datos y llamadas de procedimiento tiene importantes consecuencias para la seguridad (ver más abajo), de los que un programador debe ser consciente, a fin de evitar la introducción de graves errores de seguridad en un programa.
Muchas máquinas virtuales también están orientadas hacia la pila, incluida la p-código máquina y la máquina virtual Java.
Casi todos los entornos de computación de tiempo de ejecución de memoria utilizan una pila especial PILA para tener información sobre la llamada de un procedimiento o función y de la anidación con el fin de cambiar al contexto de la llamada a restaurar cuando la llamada termina. Ellos siguen un protocolo de tiempo de ejecución entre el que llama y el llamado para guardar los argumentos y el valor de retorno en la pila. Pila es una forma importante de apoyar llamadas anidadas o a funciones recursivas. Este tipo de pila se utiliza implícitamente por el compilador para apoyar CALL y RETURN estados (o sus equivalentes), y no es manipulada directamente por el programador.
Algunos lenguajes de programación utilizar la pila para almacenar datos que son locales a un procedimiento. El espacio para los datos locales se asigna a los temas de la pila cuando el procedimiento se introduce, y son borradas cuando el procedimiento termina. El lenguaje de programación C es generalmente aplicado de esta manera. Utilizando la misma pila de los datos y llamadas de procedimiento tiene importantes consecuencias para la seguridad (ver más abajo), de los que un programador debe ser consciente, a fin de evitar la introducción de graves errores de seguridad en un programa.
Pila como tipo abstracto de datos
A modo de resumen tipo de datos, la pila es un contenedor de nodos y tiene dos operaciones básicas: push (o apilar) y pop (o desapilar). 'Push' añade un nodo a la parte superior de la pila, dejando por debajo el resto de los nodos. 'Pop' elimina y devuelve el actual nodo superior de la pila. Una metáfora que se utiliza con frecuencia es la idea de una pila de platos en una cafetería con muelle de pila. En esa serie, sólo la primera placa es visible y accesible para el usuario, todas las demás placas permanecen ocultas. Como se añaden las nuevas placas, cada nueva placa se convierte en la parte superior de la pila, escondidos debajo de cada plato, empujando a la pila de placas. A medida que la placa superior se elimina de la pila, la segunda placa se convierte en la parte superior de la pila. Dos principios importantes son ilustrados por esta metáfora: En primer lugar la última salida es un principio, la segunda es que el contenido de la pila está oculto. Sólo la placa de la parte superior es visible, por lo que para ver lo que hay en la tercera placa, el primer y segundo platos tendrán que ser retirados.
La biblioteca de plantillas de C++ estándar proporciona una "pila" clase templated que se limita a sólo apilar/desapilar operaciones. Java contiene una biblioteca de la clase Pila que es una especialización de Vector. Esto podría ser considerado como un defecto, porque el diseño heredado get () de Vector método LIFO ignora la limitación de la Pila.
Estos son ejemplos sencillos de una pila con las operaciones descritas anteriormente (pero no hay comprobación de errores).
A modo de resumen tipo de datos, la pila es un contenedor de nodos y tiene dos operaciones básicas: push (o apilar) y pop (o desapilar). 'Push' añade un nodo a la parte superior de la pila, dejando por debajo el resto de los nodos. 'Pop' elimina y devuelve el actual nodo superior de la pila. Una metáfora que se utiliza con frecuencia es la idea de una pila de platos en una cafetería con muelle de pila. En esa serie, sólo la primera placa es visible y accesible para el usuario, todas las demás placas permanecen ocultas. Como se añaden las nuevas placas, cada nueva placa se convierte en la parte superior de la pila, escondidos debajo de cada plato, empujando a la pila de placas. A medida que la placa superior se elimina de la pila, la segunda placa se convierte en la parte superior de la pila. Dos principios importantes son ilustrados por esta metáfora: En primer lugar la última salida es un principio, la segunda es que el contenido de la pila está oculto. Sólo la placa de la parte superior es visible, por lo que para ver lo que hay en la tercera placa, el primer y segundo platos tendrán que ser retirados.
Operaciones
Una pila cuenta con 2 operaciones imprescindibles: apilar y desapilar, a las que en las implementaciones modernas de las pilas se suelen añadir más de uso habitual.- Crear: se crea la pila vacía.
- Apilar: se añade un elemento a la pila.(push)
- Desapilar: se elimina el elemento frontal de la pila.(pop)
- Cima: devuelve el elemento que esta en la cima de la pila. (top o peek)
- Vacía: devuelve cierto si la pila está vacía o falso en caso contrario.
Implementación
Un requisito típico de almacenamiento de una pila de n elementos es O(n). El requisito típico de tiempo de O las operaciones también son fáciles de satisfacer con un array o con listas enlazadas simples.La biblioteca de plantillas de C++ estándar proporciona una "pila" clase templated que se limita a sólo apilar/desapilar operaciones. Java contiene una biblioteca de la clase Pila que es una especialización de Vector. Esto podría ser considerado como un defecto, porque el diseño heredado get () de Vector método LIFO ignora la limitación de la Pila.
Estos son ejemplos sencillos de una pila con las operaciones descritas anteriormente (pero no hay comprobación de errores).
