• Author / Uploaded
• Roberto Castillo

Citation preview

INSTITUTO POLITÉCNICO NACIONAL

ESIME CULHUACÁN

INGENIERÍA EN COMUNICACIONES Y ELECTRÓNICA

MATERIA: ESTRUCTURA Y BASE DE DATOS

PROFESOR: JUAN CARLOS GONZALEZ AMADO

EQUIPO 3: FLORES GONZALEZ LUZ AURORA GUZMÁN ELIGIO MIGUEL ÁNGEL IBAÑEZ CASTILLLO ROBERTO GERARDO SALAZAR AROCHE EDUARDO ZALDIVAR GALEANA ABEL

TEMA: LISTAS ENLAZADAS

GRUPO: 3EV26

1

ÍNDICE

1. CONCEPTOS BÁSICOS (Pag. 3) 2. OPERACIONES EN LISTA (Pag. 4) 3. BORRADO (Pag. 5) 4. LISTAS SIMPLEMENTE ENLAZADAS (Pag. 7) 5. ALGORITMO (Pag. 8) 6. LISTAS CIRCULARES (Pag. 11)

7. LISTAS DOBLEMENTE ENLAZADAS (Pag. 15)

8. OPERACIONES BÁSICAS (Pag. 16)

9. EJEMPLO (Pag. 23)

LISTAS ENLAZADAS 2

 Son colecciones de elementos llamados nodos (desde 0) y el orden entre estos se establece por medio de un tipo de datos denominado punteros.  Si la lista no tiene elementos se dice que está vacía  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.  Son mas flexibles que los arreglos y permiten un trabajo dinámico con un grupo de elementos

CONCEPTOS BÁSICOS •

Lista continua: se considerarse como una colección o secuencia de elementos del mismo tipo que van en una posición uno de tras del otro. Ej.: Las entradas de una guía o directorio telefónico, por ejemplo, están en líneas sucesivas, excepto en las partes superior e inferior de cada columna.

•

Una lista lineal se almacena en la memoria principal de una computadora en posiciones sucesivas o adyacentes de memoria y se procesa como un arreglo unidimensional. En este caso, el acceso a cualquier elemento de la lista es fácil; sin embargo, la inserción o borrado requiere un desplazamiento de lugar de los elementos que le siguen y en consecuencia el diseño de un algoritmo específico.

 De acuerdo a la implementación de las listas se clasifican:  Listas Simplemente enlazadas  Listas Circular simplemente enlazada  Listas Doblemente enlazadas  Lista circular doblemente enlazada  Cada elemento de la lista enlazada debe tener al menos dos campos: un campo que tiene el valor del elemento y un campo (enlace o liga) que contiene la posición del siguiente elemento, es decir, su conexión, enlace o encadenamiento

OPERACIONES EN LISTA 3

 Para permitir operaciones con las listas como arreglos se deben dimensionar éstos con tamaño suficiente para que contengan todos los posibles elementos de la lista.  La inserción o eliminación de un elemento, excepto en la cabecera o final de la lista, necesita una traslación de un parte de los elementos de la misma: la que precede o sigue a la posición del elemento modificado.  Las operaciones directas de añadir y eliminar se efectúan únicamente en los extremos de la lista.  Operación de Inserción. Esta operación consiste en agregar un nuevo elemento a la lista. Se pueden considerar tres casos especiales:  Insertar un elemento al inicio de la lista.  Insertar un elemento antes o después de un determinado elemento o nodo de la lista.  Insertar un elemento al final de la lista.  Operación de Visualización. Esta operación consiste en mostrar o visualizar los elementos de la lista que han sido insertados o almacenados previamente en la estructura, para lo cual se hace el recorrido para ir mostrando en pantalla cada elemento de la lista iniciando desde la cabeza hasta llegar al último nodo, es decir, cuando el nodo siguiente es igual a NULL.  Operación de Recorrido. Esta operación consiste en visitar cada uno de los elementos que forman la lista. Para ello se comienza con el primer elemento, se toma el valor del campo enlace para avanzar al segundo elemento, el campo enlace de este elemento dará la dirección del tercer elemento y así sucesivamente hasta que la información del campo enlace sea NULL, lo que indica que el recorrido llegó a su final.  Operación de Búsqueda. Esta operación consiste en buscar un determinado elemento en la lista, que es solicitado por el usuario en tiempo de ejecución, se procede a hacer la comparación entre el elemento a buscar con cada uno de los elementos previamente ingresados a la lista , el recorrido se hace tomando al campo enlace como puntero al siguiente elemento a visitar en la lista, una vez se encuentre el elemento se procede a mostrarlo en pantalla.  Operación de Borrado. La operación de borrado consiste en eliminar un elemento de la lista, se pueden presentar cuatro casos básicos:  Eliminar el primer elemento de la lista.  Eliminar el último elemento de la lista.  Eliminar de la lista un elemento específico, es decir, que tenga cierta información independientemente de su ubicación.

BORRADO 4

La operación borrar consiste en la eliminación de la lista de un elemento concreto. El elemento a borrar será escogido por el programador. La eliminación en una lista no conlleva ningún trabajo adicional más que el propio de la eliminación del elemento en sí. Para borrar un elemento cualquiera habría que realizar un recorrido secuencial de la lista hasta encontrar el nodo buscado y una vez localizado reestructurar los punteros para saltarse el nodo a borrar y así poder eliminarlo.

Borrado del elemento 76 Dependiendo de la posición en la que este se encuentre, se pueden presentar diferentes casos, como los que se señalan a continuación: •

Eliminar el primer nodo

•

Eliminar el ultimo nodo

•

Eliminar un nodo con información X

•

Eliminar el nodo anterior al nodo con información X

•

Eliminar el nodo posterior al nodo con información X

a) Eliminar el primer nodo Esta operación es muy sencilla, ya que solo es necesario redefinir el apuntador al inicio de la lista. Si esta quedara vacía ( es decir, si la lista tenia solo un elemento), entonces apuntaría a NIL.

eliminación del primer nodo utilizando el algoritmo anterior.

b) Eliminación del ultimo nodo

5

En este caso se debe eliminar el ultimo nodo de una lista simplemente ligada. Es importante observar que para alcanzar el ultimo nodo, se debe recorrer toda la lista, excepto si se usara un apuntador que indique su final.

La flecha discontinua indica los cambios originados por la eliminación del último nodo de la lista.

c) Eliminar un nodo con información X

Eliminación de un nodo con información X.

d) Eliminar el nodo anterior al nodo con información X Este es el caso de eliminación mas complicando en listas simplemente ligadas, porque tiene muchas variantes. Por ejemplo, el nodo con información X puede ser el primero - entonces no hay nada que eliminar -, el segundo - entonces hay que eliminar el primero de la lista-, estar en cualquier otra posición, o bien no encontrarse en la lista.

LISTAS SIMPLEMENTE ENLAZADAS 6

Una lista enlazada o estructura ligada, es una estructura lineal que almacena una colección de elementos generalmente llamados nodos, en donde cada nodo puede almacenar datos y ligas a otros nodos. De esta manera los nodos pueden localizarse en cualquier parte de la memoria, utilizando la referencia que lo relaciona con otro nodo dentro de la estructura. Las listas enlazadas son estructuras dinámicas que se utilizan para almacenar datos que están cambiando constante mente. A diferencia de los vectores, las estructuras dinámicas se expanden y se contraen haciéndolas más flexibles a la hora de añadir o eliminar información.

Las listas enlazadas permiten almacenar información en posiciones de memoria que no sean contiguas; para almacenar la información contienen elementos llamados nodos. Estos nodos poseen dos campos uno para almacenar la información o valor del elemento y otro para el enlace que determina la posición del siguiente elemento o nodo de la lista. •

Listas enlazadas simples (con una sola dirección).

Una lista enlazada simple es una colección de nodos que tienen una sola dirección y que en conjunto forman una estructura de datos lineal. Cada nodo es un objeto compuesto que guarda una referencia a un elemento (dato) y una referencia a otro nodo (dirección). La referencia que guarda un nodo a otro nodo se puede considerar un enlace o un puntero hacia el segundo nodo y el salto que los relaciona recibe el nombre de salto de enlace o salto de puntero. El primer nodo de una lista recibe el nombre de cabeza, cabecera o primero y el último es llamado final, cola o último (es el único nodo con la referencia a otro objeto como nula). Un nodo de una lista enlazada simple puede determinar quien se encuentra después de él pero no puede determinar quien se encuentra antes, ya que solo cuenta con la dirección del nodo siguiente pero no del anterior

ALGORITMO 7

Es un conjunto prescrito de instrucciones o reglas bien definidas, ordenadas y finitas que permite llevar a cabo una actividad mediante pasos sucesivos que no generen dudas a quien deba hacer dicha actividad.2 Dados un estado inicial y una entrada, siguiendo los pasos sucesivos se llega a un estado final y se obtiene una solución. Los algoritmos son el objeto de estudio de la algoritmia. •

Operaciones con algoritmos

1. Búsqueda: Se trata de localizar una clave de valor determinado (pasado como argumento) sin entrar en consideraciones de qué se va a hacer con ella. En cualquier caso este tipo de algoritmos no tienen efecto alguno sobre la estructura (no se modifica el número de nodos). En principio la condición de finalización se consigue al llegar al final de la lista (inicio == null). Se produce una terminación anticipada en caso de encontrar la clave buscada. Ejemplo: static boolean busqueda (NodoLista nodoLista, int x) { boolean resul = false; if (nodoLista != null) if (nodoLista.clave == x) resul = true; else resul = busqueda (nodoLista.sig, x); return resul; } public boolean busqueda (int x) { return busqueda (inicio, x); } 2. Inserción: El efecto de este tipo de algoritmos es incrementar el número de nodos. Para crear un nuevo nodo es necesario conocer tanto la naturaleza de la estructura utilizada (estática o dinámica) como los recursos del lenguaje de programación empleado. Lo más sencillo y eficiente es insertar el nuevo nodo al principio de la lista Ejemplo: static NodoLista insertarAlFinal (NodoLista nodoLista, int dato) { NodoLista aux = nodoLista; if (nodoLista!= null) if (nodoLista.clave != dato) nodoLista.sig = insertarAlFinal (nodoLista.sig, dato); 8

else System.out.println ("la clave ya existe"); else aux = new NodoLista (dato, nodoLista); return aux; } public void insertar (int dato) { inicio = insertarAlFinal (inicio, dato); } Si se desea realizar la inserción en una lista calificada no ordenada de manera iterativa, se podría utilizar el algoritmo que aparece a continuación. Obsérvese que, además de la variable aux, es necesario utilizar otros dos referencias, actual y anterior para recorrer la lista y verificar que el elemento no existe. Se utiliza, además, la variable seguir, de tipo boolean, que inicialmente es true y lo seguirá siendo a no ser que encontremos la clave en la lista. Ejemplo: public void insertarIterativo (int dato) { NodoLista anterior, actual, aux; boolean seguir; anterior = inicio; actual = inicio; seguir = true; while ((actual != null) && seguir) if (actual.clave == dato) seguir= false; else { anterior = actual; actual = actual.sig; } if (seguir) { aux = new NodoLista (dato, null); if (inicio == null) inicio = aux; else anterior.sig = aux; } 9

else System.out.println ("Error. Elemento repetido"); } •

3.Eliminación.

Este tipo de algoritmos reduce el número de nodos de la estructura. En la mayoría de los lenguajes de programación deberá prestarse atención especial a liberar el espacio de memoria de los nodos eliminados para posibles usos posteriores.6 Se procede a recorrer la lista comparando las sucesivas claves con el argumento recibido (dato). La condición de finalización “pesimista” sería alcanzar el final de la lista, lo que significaría que no se habría encontrado la clave a eliminar. No obstante lo normal es que se produzca una terminación anticipada en el momento en que se encuentra la clave a eliminar. Ejemplo: static NodoLista eliminar (NodoLista nodoLista, int dato) { NodoLista resul = nodoLista; if (nodoLista!= null) if (nodoLista.clave != dato) nodoLista.sig = eliminar (nodoLista.sig, dato); else resul = nodoLista.sig; else System.out.println ("la clave no existe"); return resul; } public void eliminar (int dato) { inicio = eliminar (inicio, dato); }

LISTAS CIRCULARES La lista circular es una especie de lista enlazada simple o doblemente enlazada, pero que posee una característica adicional para el desplazamiento dentro de la lista: esta no tiene fin. 10

Para que la lista sea sin fin, el puntero siguiente del último elemento apuntará hacia el primer elemento de la lista.

En las listas circulares, nunca se llega a una posición en la que ya no sea posible desplazarse. Cuando se llegue al último elemento, el desplazamiento volverá a comenzar desde el primer elemento.

Cómo construir el modelo de un elemento de la lista La palabra reservada “struct” indica que se está definiendo una estructura. struct fecha { int dia; int mes; int anio; int dia del anio; char nombre mes[9]; };

Para definir un elemento de la lista, el tipo struct será utilizado. El elemento de la lista va a tener un campo dato y un puntero siguiente. Este debe ser del mismo tipo que el elemento, en caso contrario no podrá apuntar hacia el elemento. El puntero siguiente permitirá el acceso al próximo elemento. typedef struct ElementoLista { char *dato; struct ElementoLista *siguiente; }Elemento;

11

Para tener el control de la lista es mejor guardar ciertos elementos: el primer elemento, el último elemento y el número de elementos. Para ello, otra estructura será utilizada (no es obligatorio, pueden ser utilizadas variables). typedef struct ListaIdentificar { Elemento *inicio; Elemento *fin; int tamaño; }Lista; El puntero inicio albergará la dirección del primer elemento de la lista. El puntero fin contendrá la dirección del último elemento de la lista. La variable tamaño contiene el número de elementos. Cualquiera que sea la posición en la lista, los punteros inicio y finsiempre apuntarán hacia el primer y el último elemento respectivamente. El campo tamaño contendrá el número de elementos de la lista cualquiera sea la operación efectuada sobre la lista Operaciones sobre las listas circulares Inicialización Modelo de la función: void inicialización (Lista *lista); Esta operación debe ser realizada primero antes de cualquier otra operación sobre la lista. Comienza colocando el puntero inicio y fin con el puntero NULL, y el tamaño con el valor 0. La función: void inicialización (Lista *lista){ lista->inicio = NULL; lista->fin = NULL; tamaño = 0; }

Inserción de un elemento en la lista Enseguida, el algoritmo de inserción y el registro de los elementos: afirmación del elemento que se insertará, asignación de la memoria destinada al nuevo elemento, llenar el contenido del campo de los datos, actualizar los punteros hacia el primer y último elemento si es necesario. Caso particular: en una lista con un solo elemento, el primer elemento es al mismo tiempo el último. Luego, se tiene que actualizar el tamaño de la lista. 12

Inserción en una lista vacía Modelo de la función: int ins_lista_circ_vacia(Lista * lista, char *dato);

La función devuelve -1 en caso de falla, si no devuelve 0. Etapas: asignación de memoria para el nuevo elemento, rellenar el campo de datos del elemento nuevo, el puntero siguiente del nuevo elemento apuntará hacia si mismo (es la etapa que vuelve a la lista circular), los punteros inicio y fin apuntarán hacia el nuevo elemento, el tamaño es actualizado.

Inserción en una lista no vacía Modelo de la función: int ins_lista_circ(Lista * lista, Elemento *actual, char *dato);

La función devuelve -1 en caso de equivocación, si no devuelve 0. La inserción se efectuará al final de la lista. Etapas: asignación de memoria para el nuevo elemento, rellenar el campo de datos del reciente elemento, el puntero siguiente del nuevo elemento apunta hacia la dirección del primer elemento (conservar la lista circular), el puntero inicio no cambia, el puntero fin apunta hacia el nuevo elemento, el tamaño se incrementa en una unidad. 13

LISTAS DOBLEMENTE ENLAZADAS

14

Una lista doblemente enlazada es una lista lineal en la que cada nodo tiene dos enlaces, uno al nodo siguiente, y otro al anterior. Las listas doblemente enlazadas no necesitan un nodo especial para acceder a ellas, pueden recorrerse en ambos sentidos a partir de cualquier nodo, esto es porque a partir de cualquier nodo, siempre es posible alcanzar cualquier nodo de la lista, hasta que se llega a uno de los extremos. El nodo típico es el mismo que para construir las listas que hemos visto, salvo que tienen otro puntero al nodo anterior: struct nodo { int dato; struct nodo *siguiente; struct nodo *anterior; };

Declaraciones de tipos para manejar listas doblemente enlazadas en C Para C, y basándonos en la declaración de nodo que hemos visto más arriba, trabajaremos con los siguientes tipos: typedef struct _nodo { int dato; struct _nodo *siguiente; struct _nodo *anterior; } tipoNodo; typedef tipoNodo *pNodo; typedef tipoNodo *Lista;

tipoNodo es el tipo para declarar nodos, evidentemente. pNodo es el tipo para declarar punteros a un nodo. Lista es el tipo para declarar listas abiertas doblemente enlazadas. También es posible, y potencialmente útil, crear listas doblemente enlazadas y circulares.

15

El movimiento a través de listas doblemente enlazadas es más sencillo, y como veremos las operaciones de búsqueda, inserción y borrado, también tienen más ventajas.

OPERACIONES BASICAS 

Añadir o insertar elementos.



Buscar o localizar elementos.



Borrar elementos.



Moverse a través de la lista, siguiente y anterior.

Nos encontramos ahora ante un tipo de estructura algo diferente de las que hemos estado viendo, así que entraremos en más detalles. Vamos a intentar ver todos los casos posibles de inserción de elementos en listas doblemente enlazadas.

AÑADIR UN ELEMENTO Partiremos de que ya tenemos el nodo a insertar y, por supuesto un puntero que apunte a él, además el puntero que define la lista, que valdrá NULL: El proceso es muy simple, bastará con que: 1.

lista apunta a nodo.

2.

lista->siguiente y lista->anterior apunten a null.

Partimos de una lista no vacía. Para simplificar, consideraremos que lista apunta al primer elemento de la lista doblemente enlazada:

16

El proceso es el siguiente: 1.

nodo->siguiente debe apuntar a Lista.

2.

nodo->anterior apuntará a Lista->anterior.

3.

Lista->anterior debe apuntar a nodo.

Recuerda que Lista no tiene por qué apuntar a ningún miembro concreto de una lista doblemente enlazada, cualquier miembro es igualmente válido como referencia.

INSERTAR UN ELEMENTO EN LA ULTIMA POSICION DE LA LISTA Igual que en el caso anterior, partiremos de una lista no vacía, y de nuevo para simplificar, que Lista está apuntando al último elemento de la lista:

El proceso es el siguiente: 1.

nodo->siguiente debe apuntar a Lista->siguiente (NULL).

2.

Lista->siguiente debe apuntar a nodo.

3.

nodo->anterior apuntará a Lista.

17

INSERTAR UN ELEMENTO A CONTINUACION DE UN NODO CUALQUIERA DE UNA LISTA Bien, este caso es más genérico, ahora partimos de una lista no vacía, e insertaremos un nodo a continuación de uno nodo cualquiera que no sea el último de la lista:

El proceso sigue siendo muy sencillo: 1.

Hacemos que nodo->siguiente apunte a lista->siguiente.

2.

Hacemos que Lista->siguiente apunte a nodo.

3.

Hacemos que nodo->anterior apunte a lista.

4.

Hacemos que nodo->siguiente->anterior apunte a nodo.

18

Lo que hemos hecho es trabajar como si tuviéramos dos listas enlazadas, los dos primeros pasos equivalen a lo que hacíamos para insertar elementos en una lista abierta corriente. Los dos siguientes pasos hacen lo mismo con la lista que enlaza los nodos en sentido contrario. El paso 4 es el más oscuro, quizás requiera alguna explicación. Supongamos que disponemos de un puntero auxiliar, "p" y que antes de empezar a insertar nodo, hacemos que apunte al nodo que quedará a continuación de nodo después de insertarlo, es decir p = Lista->siguiente. Ahora empezamos el proceso de inserción, ejecutamos los pasos 1, 2 y 3. El cuarto sería sólo hacer que p->anterior apunte a nodo. Pero nodo->siguiente ya apunta a p, así que en realidad no necesitamos el puntero auxiliar, bastará con hacer que nodo->siguiente->anterior apunte a nodo.

AÑADIR ELEMENTO EN UNA LISTA DOBLEMENTE ENLAZADA EN CASO GENERAL Para generalizar todos los casos anteriores, sólo necesitamos añadir una operación: 1.

Si lista está vacía hacemos que Lista apunte a nodo. Y nodo->anterior y nodo>siguiente a NULL.

2.

Si lista no está vacía, hacemos que nodo->siguiente apunte a Lista->siguiente.

3.

Después que Lista->siguiente apunte a nodo.

4.

Hacemos que nodo->anterior apunte a Lista.

5.

Si nodo->siguiente no es NULL, entonces hacemos que nodo->siguiente->anterior apunte a nodo.

El paso 1 es equivalente a insertar un nodo en una lista vacía. Los pasos 2 y 3 equivalen a la inserción en una lista enlazada corriente. Los pasos 4, 5 equivalen a insertar en una lista que recorre los nodos en sentido contrario.

19

BUSCAR UN ELEMENTO DE UNA LISTA DOBLEMENTE ENLAZADA En muchos aspectos, una lista doblemente enlazada se comporta como dos listas abiertas que comparten los datos. En ese sentido, todo lo dicho en el capítulo sobre la localización de elementos en listas abiertas se puede aplicar a listas doblemente enlazadas. Pero además tenemos la ventaja de que podemos avanzar y retroceder desde cualquier nodo, sin necesidad de volver a uno de los extremos de la lista. Por supuesto, se pueden hacer listas doblemente enlazadas no ordenadas, existen cientos de problemas que pueden requerir de este tipo de estructuras. Pero parece que la aplicación más sencilla de listas doblemente enlazadas es hacer arrays dinámicos ordenados, donde buscar un elemento concreto a partir de cualquier otro es más sencillo que en una lista abierta corriente. Pero de todos modos veamos algún ejemplo sencillo. Para recorrer una lista procederemos de un modo parecido al que usábamos con las listas abiertas, ahora no necesitamos un puntero auxiliar, pero tenemos que tener en cuenta que Lista no tiene por qué estar en uno de los extremos: 1.

Retrocedemos hasta el comienzo de la lista, asignamos a lista el valor de lista>anterior mientras lista->anterior no sea NULL.

2.

Abriremos un bucle que al menos debe tener una condición, que el índice no sea NULL.

3.

Dentro del bucle asignaremos a lista el valor del nodo siguiente al actual.

Por ejemplo, para mostrar todos los valores de los nodos de una lista, podemos usar el siguiente bucle en C: typedef struct _nodo { int dato; struct _nodo *siguiente; struct _nodo *anterior; } tipoNodo; typedef tipoNodo *pNodo; typedef tipoNodo *Lista; ... pNodo = indice; ... indice = Lista; while(indice->anterior) indice = indice->anterior; while(indice) { printf("%d\n", indice->dato); indice = indice->siguiente; } ... 20

Es importante que no perdamos el nodo Lista, si por error le asignáramos un valor de un puntero a un nodo que no esté en la lista, no podríamos acceder de nuevo a ella. Es por eso que tendremos especial cuidado en no asignar el valor NULL a Lista.

ELIMINAR UN ELEMENTO DE UNA LISTA DOBLEMENTE ENLAZADA Analizaremos tres casos diferentes: 1.

Eliminar el único nodo de una lista doblemente enlazada.

2.

Eliminar el primer nodo.

3.

Eliminar el último nodo.

4.

Eliminar un nodo intermedio.

Para los casos que lo permitan consideraremos dos casos: que el nodo a eliminar es el actualmente apuntado por Lista o que no.

ELIMINAR UN NODO EN UNA LISTA DOBLEMENTE ENLAZADA En este caso, ese nodo será el apuntado por Lista. El proceso es simple: 1.

Eliminamos el nodo.

2.

Hacemos que Lista apunte a NULL.

ELIMINAR EL PRIMER NODO DE UNA LISTA DOBLEMENTE ENLAZADA Tenemos los dos casos posibles, que el nodo a borrar esté apuntado por Lista o que no. Si lo está, simplemente hacemos que Lista sea Lista->siguiente

21

1.

Si nodo apunta a Lista, hacemos que Lista apunte a Lista->siguiente.

2.

Hacemos que nodo->siguiente->anterior apunte a NULL

3.

Borramos el nodo apuntado por nodo.

El paso 2 depara el nodo a borrar del resto de la lista, independientemente del nodo al que apunte Lista.

ELIMINAR EL ÚLTIMO NODO DE UNA LISTA DOBLEMENTE ENLAZADA De nuevo tenemos los dos casos posibles, que el nodo a borrar esté apuntado por Lista o que no. Si lo está, simplemente hacemos que Lista sea Lista->anterior.

1.

Si nodo apunta a Lista, hacemos que Lista apunte a Lista->anterior.

2.

Hacemos que nodo->anterior->siguiente apunte a NULL

3.

Borramos el nodo apuntado por nodo.

El paso 2 depara el nodo a borrar del resto de la lista, independientemente del nodo al que apunte Lista.

22

ELIMINAR UN NODO INTERMEDIO De nuevo tenemos los dos casos posibles, que el nodo a borrar esté apuntado por Lista o que no. Si lo está, simplemente hacemos que Lista sea Lista->anterior o Lista->siguiente Se trata de un caso más general de los dos casos anteriores.

1.

Si nodo apunta a Lista, hacemos que Lista apunte a Lista->anterior (o Lista>siguiente).

2.

Hacemos que nodo->anterior->siguiente apunte a nodo->siguiente.

3.

Hacemos que nodo->siguiente->anterior apunte a nodo->anterior.

4.

Borramos el nodo apuntado por nodo.

ELIMINAR UN NODO DE UNA LISTA DOBLEMENTE ENLAZADA, CASO GENERAL De nuevo tenemos los dos casos posibles, que el nodo a borrar esté apuntado por Lista o que no. Si lo está, simplemente hacemos que Lista sea Lista->anterior, si no es NULL o Lista->siguiente en caso contrario. 1.

Si nodo apunta a Lista, o

Si Lista->anterior no es NULL hacemos que Lista apunte a Lista>anterior. 23

Si Lista->siguiente no es NULL hacemos que Lista apunte a Lista>siguiente.

o

Si ambos son NULL, hacemos que Lista sea NULL.

o

2.

Si nodo->anterior no es NULL, hacemos que nodo->anterior->siguiente apunte a nodo->siguiente.

3.

Si nodo->siguiente no es NULL, hacemos que nodo->siguiente->anterior apunte a nodo->anterior.

4.

Borramos el nodo apuntado por nodo.

Ejemplo: #include using namespace std; #define ASCENDENTE 1 #define DESCENDENTE 0 class nodo { public: nodo(int v, nodo *sig = NULL, nodo *ant = NULL) : valor(v), siguiente(sig), anterior(ant) {} private: int valor; nodo *siguiente; nodo *anterior; friend class lista; }; typedef nodo *pnodo; class lista { public: lista() : plista(NULL) {} ~lista(); void Insertar(int v); void Borrar(int v); bool ListaVacia() { return plista == NULL; } void Mostrar(int); 24

void Siguiente(); void Anterior(); void Primero(); void Ultimo(); bool Actual() { return plista != NULL; } int ValorActual() { return plista->valor; } private: pnodo plista; }; lista::~lista() { pnodo aux; Primero(); while(plista) { aux = plista; plista = plista->siguiente; delete aux; } } void lista::Insertar(int v) { pnodo nuevo; Primero(); // Si la lista está vacía if(ListaVacia() || plista->valor > v) { // Asignamos a lista un nuevo nodo de valor v y // cuyo siguiente elemento es la lista actual nuevo = new nodo(v, plista); if(!plista) plista = nuevo; else plista->anterior = nuevo; } else { // Buscar el nodo de valor menor a v // Avanzamos hasta el último elemento o hasta que el siguiente tenga // un valor mayor que v while(plista->siguiente && plista->siguiente->valor siguiente, plista); plista->siguiente = nuevo; if(nuevo->siguiente) nuevo->siguiente->anterior = nuevo; } } void lista::Borrar(int v) { pnodo nodo; nodo = plista; 25

while(nodo && nodo->valor < v) nodo = nodo->siguiente; while(nodo && nodo->valor > v) nodo = nodo->anterior; if(!nodo || nodo->valor != v) return; // Borrar el nodo if(nodo->anterior) // no es el primer elemento nodo->anterior->siguiente = nodo->siguiente; if(nodo->siguiente) // no el el último nodo nodo->siguiente->anterior = nodo->anterior; delete nodo; } void lista::Mostrar(int orden) { pnodo nodo; if(orden == ASCENDENTE) { Primero(); nodo = plista; while(nodo) { cout valor siguiente; } } else { Ultimo(); nodo = plista; while(nodo) { cout valor anterior; } } cout siguiente; } void lista::Anterior() { if(plista) plista = plista->anterior; } void lista::Primero() { while(plista && plista->anterior) plista = plista->anterior; } void lista::Ultimo() { while(plista && plista->siguiente) plista = plista->siguiente; }

26

int main() { lista Lista; Lista.Insertar(20); Lista.Insertar(10); Lista.Insertar(40); Lista.Insertar(30); Lista.Mostrar(ASCENDENTE); Lista.Mostrar(DESCENDENTE); Lista.Primero(); cout