Listas Simplemente Enlazadas Estructura de datos
Enviado por Moises Sierra Dubon • 26 de Septiembre de 2015 • Informes • 2.085 Palabras (9 Páginas) • 286 Visitas
Listas Simplemente Enlazadas
Estructura de datos
Catedrático: Lic. Juan Gabriel García
Integrantes:
Melvin Moises Sierra Dubon 1130584
Moises Bernardo Pejuan Enamorado 1130558
Carlos Manuel Romero Cruz 3090098
SAN PEDRO SULA, 22 de Septiembre de 2015
INTRODUCCIÓN
El objetivo de esta exposición es el de comprender el uso de las listas enlazadas simples. Las listas enlazadas pueden ser utilizadas cuando se necesitan hacer varias operaciones de inserción y eliminación de elementos.
DEFINICION SOBRE LAS LISTAS ENLAZADAS
Las listas enlazadas son estructuras de datos semejantes a los ”array” salvo que el acceso a un elemento no se hace mediante un índice sino mediante un puntero.
La asignación de memoria es hecha durante la ejecución.
OPERACIONES QUE SE HACEN CON LAS LISTAS ENLAZADAS
- Agregar al final.
- Agregar al inicio.
- Agregar después de un nodo en específico.
- Agregar antes de un nodo en específico.
- Eliminar al inicio.
- Eliminar al final.
- Eliminar antes de un nodo en específico.
- Eliminar después de un nodo en específico.
- Eliminar un nodo en específico.
- Recorrido.
Listas Simplemente Enlazadas
En esta estructura de dato se presenta el concepto de Nodo. El Nodo tiene dos partes, la parte del dato y la parte donde se apunta al otro nodo.
Insertar al inicio
Para insertar al inicio; al ser por primera vez que se inserta, decimos que nuestro inicio va a ser igual a nuestro nodo nuevo que este apuntara a null. Al haber ya un elemento existente o elementos ya existentes lo que asemos es recorrer la lista mientras el apuntador del nodo auxiliar sea diferente de null, y que nuestro nuevo nodo apunte a null y el nodo auxiliar apunte al nuevo nodo.
Insertar al final
Al insertar por primera vez el inicio será igual al nuevo nodo, y el nuevo nodo apuntara a null. Al haber ya elemento o elementos ya existentes nuestro nodo nuevo apuntara a inicio y nuestro nuevo inicio será el nuevo nodo.
Insertar después de un nodo en específico
Para insertar después de un nodo en específico primero hay que recorrer la lista hasta encontrar el nodo que contenga el número al que queremos ingresarle después de él, el nodo nuevo, aremos que el nodo encontrado apunte al nuevo nodo y el nuevo nodo que apunte hacia el nodo que estaba apuntando el nodo encontrado.
Insertar antes de un nodo en específico
Para insertar antes de un nodo en específico primero hay que recorrer la lista hasta encontrar el nodo que contenga el numero al que queremos ingresarle antes de él, el nuevo nodo, después el nodo anterior al nodo encontrado lo aremos apuntar hacia el nuevo nodo, y el nuevo nodo apuntar hacia el nodo del numero encontrado.
Eliminar al inicio
Para eliminar al inicio tenemos que crear un nuevo nodo llamado auxiliar, y aremos que el inicio sea igual hacia donde está apuntando el nodo auxiliar y después que donde está apuntando el nodo auxiliar sea igual a null.
Eliminar al final
Para eliminar al final se necesitan dos nodos auxiliares; auxiliar1 y auxiliar2. Con el auxiliar1 recorremos la lista mientras el apuntador sea diferente de null y que nuestro auxliar2 sea igual a nuestro auxiliar 1 y el auxiliar1 se irá incrementando dentro del ciclo. Al terminarse el ciclo el apuntador del auxiliar2 apuntara a null.
public class Funciones {
class Nodo { // Definición de nodo a utilizar en la lista
int dato;
Nodo enlace;
Nodo (int n){ // Contructor de la clase Nodo
dato = n;
enlace = null;
}
}
Nodo P;
Funciones(){ // Contructor de la clase Lista
P=null;
}
public void agregaL_final(int s){
Nodo tmp =new Nodo(s);
if(P==null){
P=tmp;
P.enlace=null;
}
else{
tmp.enlace=P;
P=tmp;
}
}
public void agregar_inicio(int s){
Nodo tmp=new Nodo(s);
Nodo aux=P;
if(P==null){
P=tmp;
P.enlace=null;
}
else{
while(aux.enlace!=null){
aux=aux.enlace;
}
aux.enlace =tmp;
tmp.enlace=null;
}
}
public void agregar_antes(int s, int x){
Nodo tmp=new Nodo(s);
Nodo aux=P;
Nodo aux2=P;
while(aux.dato!= x){
aux=aux.enlace;
}
if(aux!=null){
while(aux2.enlace!=aux){
aux2=aux2.enlace;
}
aux2.enlace=tmp;
tmp.enlace=aux;
}
}
public void Agregar_despues(int s, int x){
...