Inicio

Temas

Listas Simplemente (LSE) y Doblemente enlazadas (LDE)

Estructuras de Datos en Grafos

Operaciones Insertar, Eliminar y Buscar en LDE

Para simplificar la programaci.ón, es conveniente agregar nodos especiales en los extremos de lista doblemente enlazada: un nodo header (cabeza) justo antes de la cabeza de la lista, y un nodo trailer (cola) justo despu.es de la cola de la lista. Estos nodos \falsos" o centinelas no guardan ningún elemento. La cabeza tiene una referencia sig válida pero una referencia prev nula, mientras cola tiene una referencia prev válida pero una referencia sig nula.

Insertar:

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

El proceso es el siguiente:

nodo->siguiente debe apuntar a Lista.

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

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.

                    
                        void Insertar(Lista *lista, int v) {
                               pNodo nuevo, actual;
                            
                               /* Crear un nodo nuevo */
                               nuevo = (pNodo)malloc(sizeof(tipoNodo));
                               nuevo->valor = v;
                            
                               /* Colocamos actual en la primera posición de la lista */
                               actual = *lista;
                               if(actual) while(actual->anterior) actual = actual->anterior;
                            
                               /* Si la lista está vacía o el primer miembro es mayor que el nuevo */
                               if(!actual || actual->valor > v) {
                                  /* Añadimos la lista a continuación del nuevo nodo */
                                  nuevo->siguiente = actual;
                                  nuevo->anterior = NULL;
                                  if(actual) actual->anterior = nuevo;
                                  if(!*lista) *lista = nuevo;
                               }
                               else {
                                  /* Avanzamos hasta el último elemento o hasta que el siguiente tenga
                                     un valor mayor que v */
                                  while(actual->siguiente && actual->siguiente->valor <= v)
                                     actual = actual->siguiente;
                                  /* Insertamos el nuevo nodo después del nodo anterior */
                                  nuevo->siguiente = actual->siguiente;
                                  actual->siguiente = nuevo;
                                  nuevo->anterior = actual;
                                  if(nuevo->siguiente) nuevo->siguiente->anterior = nuevo;
                               }
                            }

Eliminar:

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.

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

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

Borramos el nodo apuntado por nodo.

                    
                        void Borrar(Lista *lista, int v) {
                               pNodo nodo;
                            
                               /* Buscar el nodo de valor v */
                               nodo = *lista;
                               while(nodo && nodo->valor < v) nodo = nodo->siguiente;
                               while(nodo && nodo->valor > v) nodo = nodo->anterior;
                            
                               /* El valor v no está en la lista */
                               if(!nodo || nodo->valor != v) return;
                            
                               /* Borrar el nodo */
                               /* Si lista apunta al nodo que queremos borrar, apuntar a otro */
                               if(nodo == *lista)
                                 if(nodo->anterior) *lista = nodo->anterior;
                                 else *lista = nodo->siguiente;
                            
                               if(nodo->anterior) /* no es el primer elemento */
                                  nodo->anterior->siguiente = nodo->siguiente;
                               if(nodo->siguiente) /* no es el último nodo */
                                  nodo->siguiente->anterior = nodo->anterior;
                               free(nodo);
                            }