Listas (Informática)

Listas Concepto: Una lista es una colección de elementos homogéneos entre los que existe una relación lineal.

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.

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

• Estructuras de datos
  
• Estructuras de datos. Listas enlazadas, pilas y colas