Listas (Informática)

Listas Concepto: 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. Las listas no son arreglos (arrayas), 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.

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.
Las listas no son arreglos (arrayas), 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, posicion)
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)

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, posicion)
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

Estrcturas de datos
Estructutas de datos. Listas enlazadas, pilas y colas