Listas Enlazadas Java

INGENIERIA DE SISTEMAS

1

ESTRUCTURAS DE DATOS (Listas simples)

INTRODUCCIÓN A LAS ESTRUCTURAS DE DATOS
1. INTRODUCCIÓN
Las computadoras fueron diseñadas o ideadas como una herramienta mediante la cual podemos realizar
operaciones de cálculo complicadas en un lapso de mínimo tiempo. Pero, la mayoría de las aplicaciones de
este fantástico invento del hombre, son las de almacenamiento yacceso de grandes cantidades de
información.
La información que se procesa en la computadora es un conjunto de datos, que pueden ser simples o
estructurados. Los datos simples son aquellos que ocupan sólo una localidad de memoria, mientras que los
estructurados son un conjunto de casillas de memoria a las cuales hacemos referencia mediante un
identificador único.
Debido a que por lo generaltenemos que tratar con conjuntos de datos y no con datos simples (enteros,
reales, booleanos, etc.) que por sí solos no nos dicen nada, ni nos sirven de mucho, es necesario tratar con
estructuras de datos adecuadas a cada necesidad.
2. CONCEPTO
Una estructura de datos es una colección de datos organizados de un modo particular, las estructuras de datos
pueden ser de dos tipos: estructuras dedatos estáticas y estructuras de datos dinámicas. Las estructuras de
datos estáticas son aquellas en las que el espacio en memoria se define en tiempo de compilación y no
pueden ser modificados durante la ejecución del programa, corresponden a este tipo los arrays (vectores y
matrices). Las estructuras de datos dinámicas son aquellas en las que el espacio ocupado en memoria puede
sermodificada en tiempo de ejecución, corresponden a este tipo: las listas, árboles y grafos.

3. TIPOS DE DATOS PRIMITIVOS (SIMPLES)
Son aquellos que ya están definidos por los lenguajes de programación, donde solo utilizan una localidad de
memoria, entre ellos se encuentran:
-

char
boolean
byte
short
int
long
float
doublé

4. ESTRUCTURAS DE DATOS
TAD (Tipo de Dato Abstracto)
Los TAD sondefinidos por el programador

TAD = datos + Operaciones (funciones)

INGENIERIA DE SISTEMAS

2

ESTRUCTURAS DE DATOS (Listas simples)

5. LISTAS
La lista es un TAD, que consta de una secuencia de elementos llamados nodos.
Nodo
-

Datos (Información)
Enlace o apuntador (Apunta al siguiente nodo)
Info

Enlace

Nodos enlazados
Los nodos forman una secuencia desde el primerelemento al último elemento. El primer nodo se enlaza al
segundo, éste se enlaza al tercero y así sucesivamente hasta llegar al último nodo, que debe ser representado
de forma diferente para especificar que este nodo no se enlaza a ningún otro.

6. PILA
Una pila es TAD de tipo de lista LIFO (el último en entrar es el primero en salir), tal como una pila de platos.
Operaciones sobre la pila:
-Meter (push)
Sacar (pop)
Es vacía

7. COLA
Una cola es TAD de tipo de lista FIFO (el primero en entrar es el primero en salir), tal como la fila de un
banco.
Operaciones sobre la cola:
-

Insertar
Remover
Es vacia

INGENIERIA DE SISTEMAS

3

ESTRUCTURAS DE DATOS (Listas simples)

LISTAS ENLAZADAS SIMPLES
1. INTRODUCCIÓN
Las listas enlazadas son una secuencia de nodos quese encuentran enlazados uno con el siguiente mediante
un enlace. Cada elemento (nodo) de una lista enlazada debe tener dos campos: un campo (info) que contiene
el valor de ese elemento y un campo (enlace) que indica la posición del siguiente elemento.
Aunque se pueden crear muchos tipos de listas enlazadas, las tres variantes más populares son la lista de
enlace simple, la lista doblementeenlazada y la lista enlazada circular.
2. LISTA DE ENLACE SIMPLE.

Una lista de enlace simple es una lista enlazada de nodos, donde cada nodo tiene un único campo de enlace.
Una variable de referencia contiene una referencia al primer nodo, cada nodo (excepto el último) enlaza con
el nodo siguiente, y el enlace del último nodo contiene null para indicar el final de la lista.
En java para...