11

Listas encadenadasListas encadenadas

M.C. Juan Carlos Olivares Rojas

AgendaAgenda

Concepto de nodo y encadenamiento.

Operaciones de inserción, desplegado y eliminación de nodos de una lista.

Aplicación integradora de conceptos del curso.

22

Concepto de nodo y Concepto de nodo y encadenamientoencadenamiento

• Las listas ligadas es una de las estructuras de datos definidas por el usuario más empleada.

• Las listas tienen la característica de que son dinámicas por este motivo se hace uso de memoria dinámica, apuntadores (C/C++) y referencias (Java/C++).

33

Concepto de Nodo y Concepto de Nodo y EncadenamientoEncadenamiento

• El nodo es el elemento fundamental de la lista.

• Si una lista no tiene nodos se dice que está vacía.

• Las listas no tienen un tamaño máximo predeterminado. 44

Concepto de Nodo y Concepto de Nodo y EncadenamientoEncadenamiento

• Un nodo no es otra cosa que una estructura con los datos que nos van a interesar trabajar. El nodo contiene además al menos un enlace simple (listas ligadas) o enlaces dobles (lista doblemente ligada).

• De manera interna la lista puede tener uno o más apuntadores a los nodos de la lista (generalmente: inicio, fin y actual)

55

Concepto de Nodo y Concepto de Nodo y EncadenamientoEncadenamiento

• Los principales tipos de lista son dos dependiendo de la forma en como se accedan a los nodos:

• Cola (FIFO, Fist In First Out) en donde por un extremo se atienden clientes y por el otro van llegado.

66

Concepto de Nodo y Concepto de Nodo y EncadenamientoEncadenamiento

• Pila (LIFO, Last In First Out) en este tipo de lista sólo se trabaja con un extremo, el llamado cima de la pila.

• El encadenamiento consiste en enlazar nodo con nodo para poder ligarlos. Sin encadenamiento no se puede tener una lista ligada.

77

Concepto de Nodo y Concepto de Nodo y EncadenamientoEncadenamiento

• Generalmente el inicio y el fin de una lista están ligadas hacia un nodo vacío.

struct nodo {int valor;struct nodo *izq;struct nodo *der;}

88

Concepto de Nodo y Concepto de Nodo y EncadenamientoEncadenamiento

• Las listas circulares son aquellas que el fin de la lista apunta hacia el inicio.

• Las áreas de aplicación de las listas son muy diversas. Se utilizan para ordenamiento, búsquedas, almacenamiento de información, etc.

99

Operaciones de inserción, Operaciones de inserción, desplegado y eliminación de desplegado y eliminación de

nodos de una listanodos de una lista

• Las operaciones básicas de una lista consiste en agregar elementos, borrarlos y listarlos.

• Cada una de estas operaciones debe considerar en que parte de la lista se hace: inicio, en medio o fin.

1010

Operaciones con ListaOperaciones con Lista

• Lenguajes como Java tienen de manera predeterminada objetos del tipo Lista u objetos derivados de lista.

• Otras operaciones consiste en determinar si la lista está vacía.

• Estructuras como árboles y grafos siguen el mismo principio.

1111

Operaciones con ListaOperaciones con Lista

• Cuando se agrega un nuevo elemento lo primero que hay que realizar es crear el nuevo nodo, identificar en que parte debe de ir, actualizar los apuntadores al nuevo nodo, considerar los casos especiales.

• Al borrar se sigue el procedimiento contrario, se actualizan apuntadores, desligando el nodo y liberando memoria.

1212

Aplicación integradora de Aplicación integradora de conceptos del cursoconceptos del curso

• Realizar un programa que permita sumar números enteros muy grandes. Cada dígito debe pertenecer a un nodo. Se ordenan los nodos para ir sumando el número menos significativo. El resultado de la operación se guarda en otra lista.

1313

1414

¿Preguntas, dudas y ¿Preguntas, dudas y comentarios?comentarios?