Listas
|
|||
Definición
|
Clasificación
|
Representación
grafica y en memoria
|
Modo cabecera
|
- Una
lista es una estructura de datos lineal que se puede representar
simbólicamente como un conjunto de nodos enlazados entre si.
- Por la
forma de acceder a sus elementos.
-Por la
información utilizada para acceder a sus elementos.
|
Listas densas. Cuando la estructura que contiene la lista
es la que determina la posición del siguiente elemento.
Listas enlazadas: La localización de un elemento es:
- Estará en la dirección k, si es el primer elemento,
siendo k conocido.
-Sino es el primer elemento de la lista, estará en una
dirección, j, que está contenida en el elemento anterior.
Listas ordinales. La posición de los elementos en la
estructura la determina su orden de llegada.
Listas calificadas. Se accede a un elemento por un valor
que coincide con el de un determinado campo, conocido como clave. Este tipo
de listas se pueden clasificar a su vez en ordenadas o no ordenadas por el
campo clave.
|
Public
class ListaS {
Prívate
nodo primero;
Prívate
nodo ultimo;
Prívate
int tamaño;
Public listas(){
This.primero=null;
This.ultimo=null;
This.tamano=0;
|
Una lista con nodo de cabecera es aquella en la que el
primer nodo de la lista estará diferenciando de los demás. Una lista con nodo
cabecera satisface el requerimiento: cada nodo que tiene un elemento tiene un
nodo anterior. Esto simplifica las operaciones de eliminación e inserción,
pues no hay que tratar los casos especiales para listas vacías.
Se simplifica el código y aumenta la velocidad a cambio
de un despreciable aumento de espacio.
|
Positivo:
Las listas permiten modelar diversas entidades del
mundo real, puede implementarse en soportes informáticos de diferentes maneras.
Las listas que son un conjunto de nodos tienen cierta relación, los nodos
también tienen un valor, cada una tiene su dirección, cuando nosotros
reservamos un espacio de memoria, y por ejemplo cuando ya está en la memoria y
cada celda y cada una tiene un valor. Las listas se pueden decir que cada nodo
es un eslabón de la cadena.
Negativo:
La declaración de una lista mediante una matriz
implica conocer de antemano el número (o al menos el orden de magnitud) de
elementos que va a almacenar, pudiendo darse las circunstancias de que si se
declara pequeño podría desbordarse su capacidad o, en caso contrario,
declararlo desproporcionadamente elevado provocaría un decremento de
eficiencia.
Otro problema asociado es el tratamiento de los
elementos eliminados. Dado que en el caso de no informar, de alguna manera, de
la inexistencia de dicho elemento el nodo previamente ocupado (y ahora no
válido) quedaría como no disponible.
Interesante:
En el caso de java, se utilizan nodos que son una
clase cualquiera que creas, con unos campos dedicados a guardar información, y
otro campo que apunta a otro objeto de la clase que has creado, que a su vez
contiene información y un enlace a otro nodo, de forma que a partir de uno,
puedes avanzar al siguiente y así sucesivamente.
Conclusión:
Una lista con nodo cabecera satisface el
requerimiento: cada nodo que contiene un elemento tiene un nodo anterior. Esto
simplifica las operaciones de eliminación e inserción, pues no hay que tratar
los casos especiales para listas vacías, conocemos muchas cosas interesantes.
Bibliografía:
No hay comentarios:
Publicar un comentario