PDF de programación - Listas enlazadas

Programación de sistemas



Listas enlazadas



MATERIALES BASADOS EN EL TRABAJO DE DIFERENTES AUTORES:

Carlos Delgado Kloos, Jesús Arias Fisteus, Carlos Alario Hoyos

Julio Villena Román

<[email protected]>

1

Contenidos

 Estructuras de datos
 Listas enlazadas

•

•

La clase Node

La clase LinkedList

• Ventajas y desventajas de las listas enlazadas

2

Estructuras de datos

• Abstracción que representa un conjunto
de datos en un programa con el objetivo

de facilitar su manipulación

• Diferentes estructuras de datos presentan
ventajas o desventajas dependiendo de la

naturaleza de los datos y los tipos de
manipulaciones que se necesite hacer

sobre los mismos

3

Estructuras de datos lineales

• Organizan los datos en secuencia, donde cada

dato se relaciona con un dato anterior (excepto el

primero) y un dato posterior (excepto el último)

• Ejemplos de estructuras de datos lineales:

 Arrays
 Listas enlazadas
 Pilas
 Colas
 Colas dobles

4

Arrays

• Ventajas para el almacenamiento de colecciones

lineales de datos:
 Acceso aleatorio: se puede acceder a cualquier posición

del array en tiempo constante.

 Uso eficiente de memoria cuando todas las posiciones

están ocupadas: por guardarse en posiciones

consecutivas de memoria.

5

Arrays

• Desventajas

 Tamaño estático: debe asignarse un tamaño al crear el

array, y no se puede cambiar. Da lugar a problemas:
o Uso no eficiente de memoria por tener que reservar espacio

para el caso peor

o Posibilidad de sobrepasar el tamaño reservado en tiempo de

ejecución

 Necesidad de memoria contigua:

o Puede ocurrir que, pese a haber suficiente memoria libre, no

haya un bloque contiguo suficientemente grande

6

Arrays

• Desventajas

 Ciertas operaciones tienen un coste no óptimo:

o Inserciones y eliminaciones de datos en la primera posición o

posiciones intermedias: necesidad de desplazar datos entre

posiciones consecutivas.

o Concatenación de dos o más arrays: necesidad de copiar los datos a

un nuevo array.

o Partición de un array en varios fragmentos: necesidad de copiar

datos a nuevos arrays.

7

Ejercicio 1

• Crea un array de diez elementos de tipo entero e

inicialízalos todos con el valor 0. Después inserta

un elemento adicional con valor 1 en la cuarta

posición del array

8

Listas enlazadas

• Secuencia ordenada de nodos donde cada nodo

almacena:
 Un dato (información)
 Una referencia al siguiente nodo

• Los nodos no tienen por qué estar contiguos en

memoria

first

next

next

next

null

9

La clase Node

Dos atributos: dato y

referencia al siguiente nodo

Uso de genéricos para almacenar
información de diferentes tipos


public class Node<E> {
private E info;
private Node<E> next;

public Node(E info) {…}

public Node<E> getNext() {…}
public void setNext(Node<E> next) {…}
public E getInfo() {…}
public void setInfo(E info) {…}

}


Constructor para
inicializar el dato

Métodos get y set de los atributos



10

La clase Node (sin genéricos)


public class Node {
private Object info;
private Node next;

public Node(Object info) {…}

public Node getNext() {…}
public void setNext(Node next) {…}
public Object getInfo() {…}
public void setInfo(Object info) {…}

}



11

Ejercicio 2

• Completa el código de la clase Node. Incluye tres
constructores: uno que no recibe información para

inicializar ningún atributo; otro que permite

inicializar el atributo info, y otro que permite

inicializar los dos atributos

12

La clase MyLinkedList


public class MyLinkedList<E> {
private Node<E> first;

public MyLinkedList() {…}

public void insert(E info) {…}
public E extract() {…}
public void insert(E info, Node<E> previous) {…}
public E extract(Node<E> previous) {…}
public void print() {…}
public Node<E> searchLastNode() {…}
public int search(E info) {…}
…
}



13

Inserción al principio
public void insert(E info)

first

newNode

null

null

Paso 1: Crear un nuevo nodo

Node<E> newNode = new Node<E>(info);

14

Inserción al principio
public void insert(E info)

first

newNode

null

Paso 2: Asignar como siguiente del
nodo creado al primero de la lista

newNode .setNext(first);

15

Inserción al principio
public void insert(E info)

first

newNode

null

Paso 3: Asignar como primero de la

lista al nodo creado

first = newNode;

16

Extracción del primer nodo
public E extract()

first

null

Paso 1: Comprobar que la lista no está vacía

if (first != null)

17

Extracción del primer nodo
public E extract()

first

data

null

Paso 2: Recuperar la información del

nodo a extraer

E data = first.getInfo();


18

Extracción del primer nodo
public E extract()

first

data

null

Paso 3: Asignar como primer nodo de

la lista al segundo
first = first.getNext();


19

Extracción del primer nodo
public E extract()

first

data

El nodo queda aislado y ya no

pertenece a la lista

Paso 4: Devolver el dato

return data;


null

20

Inserción en un punto intermedio

public void insert(E info, Node<E> previous)

first

previous

null

Paso 1: Comprobar que previous no es null

if (previous != null)

21

Inserción en un punto intermedio

public void insert(E info, Node<E> previous)

first

previous

newNode

null

null

Paso 2: Crear un nuevo nodo

Node<E> newNode = new Node<E>(info);

22

Inserción en un punto intermedio

public void insert(E info, Node<E> previous)

first

previous

newNode

null

Paso 3: Asignar como siguiente del
nodo creado al siguiente a previous
newNode.setNext(previous.getNext());

23

Inserción en un punto intermedio

public void insert(E info, Node<E> previous)

first

previous

newNode

null

Paso 4: Asignar el nodo creado como

el siguiente a previous

previous.setNext(newNode);

24

Eliminación de un dato intermedio

public E extract(Node<E> previous)

first

previous

null

Paso 1: Comprobar que la lista no está vacía.

Comprobar que previous no es null.

Comprobar que el siguiente a previous no es null

if (first != null && previous!= null && previous.getNext() != null)

25

Eliminación de un dato intermedio

public E extract(Node<E> previous)

first

previous

data

null

Paso 2: Recuperar la información del nodo a

extraer

E data = previous.getNext().getInfo();

26

Eliminación de un dato intermedio

public E extract(Node<E> previous)

first

previous

data

null

Paso 3: Asignar como siguiente a

previous el siguiente al nodo a extraer

previous.setNext(previous.getNext().getNext())

27

Eliminación de un dato intermedio

public E extract(Node<E> previous)

first

previous

data

El nodo queda aislado y ya no

pertenece a la lista

Paso 4: Devolver el dato

return data;


null

28

Recorrido de la lista e impresión

public void print()

current

first

null


Node<E> current = first;
while (current != null) {
System.out.println(current.getInfo());
current = current.getNext();
}



29

Recorrido: buscar el último nodo

public Node<E> searchLastNode()

• Se avanza una referencia hasta localizar un nodo

cuyo siguiente sea null:


public Node<E> searchLastNode() {
Node<E> last = null;
Node<E> current = first;
if (current != null) {

while (current.getNext() != null) {

current = current.getNext();

}
last = current;

}
return last;

}



30

Recorrido: buscar posición de un dato

public int search(E info)

• Se avanza una referencia hasta localizar el dato.

Se va incrementando un contador al mismo tiempo:

public int search(E info) {
int pos = 1;
Node<E> current = first;
while (current != null
&& !current.getInfo().equals(info)) {
pos += 1;
current = current.getNext();
}
if (current != null){
return pos;
} else {
return -1;
}
}


Ejercicio 3

• Crea el método

public int numberOfOcurrences(E info),
que devuelva el número de nodos de una lista

enlazada cuya información almacenada es la misma

que la proporcionada como argumento

32

Ventajas de las listas enlazadas

•

Inserción y extracción de nodos con coste

independiente del tamaño de la lista

• Concatenación y partición listas con coste

independiente del tamaño de las listas

• No hay necesidad de grandes cantidades de

memoria contigua

• El uso de memoria se adapta dinámicamente al

número de datos almacenados en la lista en cada

momento

33

Desventajas de las listas enlazadas

• Acceso a posiciones intermedias con coste

dependiente del tamaño de la lista

• Necesidad de memoria adicional para

almacenar los objetos Node con sus

atributos

34

Ejercicio 4

• Crea una Lista Enlazada de diez elementos de tipo
entero e inicialízalos todos con el valor 0. Después

inserta un elemento adicional con valor 1 en la

cuarta posición de la Lista Enlazada. Asume que ya

existen la clase Node y la clase MyLinkedList

tal y como se han programado anteriormente.

35