Listas (Informática)
| ||||||
Listas (Informática). Una lista es una colección de elementos homogéneos entre los que existe una relación lineal.
1. Cada elemento de la lista, a excepción del primero, tiene un único predecesor.
2. Cada elemento de la lista, a excepción del último, tiene un único sucesor.
Sumario
Listas. Definición
Las listas no son arreglos (arrays), aunque ambos representan secuencias de elementos de un tipo, los arreglos tienen longitud fija; las listas, no; es decir, las listas son flexibles y permiten cambio de implementación.
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.
Tipos de listas
Listas simples
Se definen como un conjunto de nodos uno detrás de otro, del cual siempre se puede conocer al nodo inicial y al final, de cada nodo de la lista, se conoce un contenido, que es la información que almacena dentro puede ser de cualquier tipo de dato un sucesor único excepto el ultimo nodo de la lista.
Operaciones de las listas simples
- Creación de una lista
crearLista (nombreLista)
- Comprobación del estado
listaVacia(nombreLista) → Booleano listaVacia(referenciaNodo) → Booleano listaLlena(nombreLista) → Booleano
- Inserción de nodos
insertar(nombreLista, valorInfo, posición) insertar(nombreLista, valorInfo)
- Borrado de nodos
borrar(nombreLista, valorInfo)
- Búsqueda de un nodo
buscar(nombreLista, dato)→información buscar(nombreLista, dato)→referenciaNodo pertenece(nombreLista,informacion) → Booleano
- Recorrido de la lista
recorrer(nombreLista)
- Acceso a los nodos
info(referenciaNodo) → Informacion siguiente(referenciaNodo) → enlace
- Modificación de nodos
asignarInfo(referenciaNodo, valorInformacion) asignarEnlace(referenciaNodo, valorEnlace)
- Acotación sobre las operaciones
ListaLlena sólo tiene sentido si lista es acotada.
Acceso y modificación serán métodos get y put.
Listas ordenadas
Son las que la posición de cada nodo viene determinada por el valor de uno o más campos obligatorios de información del nodo denominados clave No se permite tener dos nodos con la misma clave.
Operaciones de las listas ordenadas
- Creación de una lista
crearLista (nombreLista)
- Comprobación del estado
listaVacia(nombreLista) → Booleano listaVacia(referenciaNodo) → Booleano listaLlena(nombreLista) → Booleano
- Insesrción de nodo
insertar(nombreLista, valorClave, valorInfo)
- Borrado de nodos
borrar(nombreLista, valorClave)
- Búsqueda de un nodo
buscar(nombreLista, valorClave) → Informacion buscar(nombreLista, valorClave)→ReferenciaNodo pertenece(nombreLista,valorClave) → Booleano
- Acceso a los nodos
clave(referenciaNodo) → Clave info(referenciaNodo) → Informacion siguiente(referenciaNodo) → enlace
- Modificación de los nodos
asignarClave(referenciaNodo, valorClave) asignarInfo(referenciaNodo, valorInformacion) asignarEnlace(referenciaNodo, valorEnlace)
Pilas
Colección ordenada de elementos homogéneos en la que sólo se pueden añadir y eliminar elementos por el principio de la misma cabecera siguiendo la Filosofía LIFO (Último en entrar primero en salir).
Operaciones con Pilas
- Creación de pila
crearPila (nombrePila)
- Comprobación del estado
pilaVacia(nombrePila) → Booleano pilaLlena(nombrePila) → Booleano
- Inserción de nodos
push(nombrePila, valorInfo)
- Extracción de nodos
pop(nombrePila) → información
- Acceso a la cabecera
cabecera(nombrePila) → informacion
- Acceso a los nodos
info(referenciaNodo) → Informacion siguiente(referenciaNodo) → Enlace
- Modificación de los nodos
asignarInfo(referenciaNodo, valorInformacion) asignarEnlace(referenciaNodo, valorEnlace)
Cola
Colección ordenada de elementos homogéneos en la que sólo se pueden añadir elementos por el final y se eliminan por el principio (frente) siguiendo la filosofía FIFO (Primero en entrar primero en salir).
Operaciones con Cola
- Creación de la cola
crearCola (nombreCola)
- Comprobación del estado
ColaVacia(nombreCola) → Booleano ColaLlena(nombreCola) → Booleano
- Inserción de nodos
encolar(nombreCola, valorInfo)
- Extracción de nodos
desencolar(nombrePila) → informacion
- Acceso a la cabecera
cabecera(nombrePila) → informacion
- Acceso a los nodos
info(referenciaNodo) → Informacion siguiente(referenciaNodo) → Enlace
- Modificación de los nodos
asignarInfo(referenciaNodo, valorInformacion) asignarEnlace(referenciaNodo, valorEnlace)
Listas Doblemente enlazadas (LDE)
Son aquellas que presentan unas relación lineal en ambos sentidos, un enlace a predecesor y antecesor en cada nodo, su recorrido puede ser en ambos sentidos y pueden ser simples u ordenadas.
Operaciones con LDE
- Creación de una lista
crearLista(nombreLista)
- Comprobación del estado
listaVacia(nombreLista) → Booleano listaVacia(referenciaNodo) → Booleano listaLlena(nombreLista) → Booleano
- Inserción de nodos
insertar(nombreLista, valorInfo, posición) insertar(nombreLista, valorInfo)
- Borrado de nodos
borrar(nombreLista, valorInfo)
- Búsqueda de un nodo
buscar(nombreLista, dato) → informacion buscar(nombreLista, dato) → referenciaNodo pertenece(nombreLista,informacion) → Booleano
- Recorrido de la lista
recorrer(nombreLista, sentido)
- Acceso a los nodos
info(referenciaNodo) → Informacion anterior(referenciaNodo) → enlace siguiente(referenciaNodo) → enlace
- Modificación de los nodos
asignarInfo(referenciaNodo, valorInformacion) asignarAnterior(referenciaNodo, valorEnlace) asignarSiguiente(referenciaNodo, valorEnlace)
Fuente
Portal de los Joven Club en Ciego de Ávila
Enlaces externos
