Lista doblemente enlazada

From Wikipedia, the free encyclopedia

En ciencias de la computación, una lista doblemente enlazada es una estructura de datos que consiste en un conjunto de nodos enlazados secuencialmente. Cada nodo contiene tres campos, dos para los llamados enlaces, que son referencias al nodo siguiente y al anterior en la secuencia de nodos, y otro más para el almacenamiento de la información (en este caso un entero). El enlace al nodo anterior del primer nodo y el enlace al nodo siguiente del último nodo, apuntan a un tipo de nodo que marca el final de la lista, normalmente un nodo centinela o puntero null, para facilitar el recorrido de la lista. Si existe un único nodo centinela, entonces la lista es circular a través del nodo centinela.

Una lista doblemente enlazada cuyos nodos contienen tres campos: un valor entero, el enlace al nodo siguiente, y el enlace al nodo anterior.

El doble enlace de los nodos permite recorrer la lista en cualquier dirección. Mientras que agregar o eliminar un nodo en una lista doblemente enlazada requiere cambiar más enlaces que en estas mismas operaciones en una lista enlazada simple, las operaciones son más simples porque no hay necesidad de mantener guardado el nodo anterior durante el recorrido, ni necesidad de recorrer la lista para hallar el nodo anterior, la referencia al nodo que se quiere eliminar o insertar es lo único necesario.

El primer y el último nodo de una lista doblemente enlazada son accesibles inmediatamente (o sea, accesibles sin necesidad de recorrer la lista, y usualmente llamados cabeza y cola) y esto permite recorrerla desde el inicio o el final de la lista, respectivamente. Cualquier nodo de la lista doblemente enlazada, una vez obtenido, puede ser usado para empezar un nuevo recorrido de la lista, en cualquier dirección (hacia el principio o el final), desde el nodo dado.

Los enlaces de un nodo de una lista doblemente enlazada son frecuentemente llamados anterior y siguiente o antecesor y sucesor. Las referencias guardadas en los enlaces son usualmente implementadas como punteros,pero también podrían ser índices de un array donde están los nodos.

Algoritmos Básicos

Lista doblemente enlazada

record NodoDoblementeEnlazado {
    siguiente // Una referencia al nodo siguiente
    anterior // Una referencia al nodo anterior
    dato // dato o referencia al dato 
 }

record ListaDoblementeEnlazada {
     NodoDoblementeEnlazado primerNodo   // referencia al primer nodo de la lista
     NodoDoblementeEnlazado ultimoNodo    // referencia al último nodo de la lista
}

Recorriendo la lista

Recorrer una lista doblemente enlazada puede ser en cualquier dirección. De hecho, la dirección del recorrido puede cambiar muchas veces, si se desea. Recorrido es frecuentemente llamado iteración.

Hacia adelante

nodo  := lista.primerNodo
 while nodo ≠ null
     <Hacer algo con nodo.dato>
     nodo  := nodo.siguiente

Hacia atrás

nodo  := lista.ultimoNodo    
 while nodo ≠ null
     <Hacer algo con nodo.dato>
     nodo  := nodo.anterior

Insertando un nodo

Estas funciones insertan un nodo ya sea adelante o atrás de un nodo dado:

function InsertaAtras(Lista lista, Nodo nodo, Nodo nuevoNodo)
     nuevoNodo.anterior  := nodo
     nuevoNodo.siguiente  := nodo.siguiente  
     if nodo.siguiente  == null
         lista.ultimoNodo  := nuevoNodo
     else
         nodo.siguiente.anterior := nuevoNodo
     nodo.siguiente  := nuevoNodo

function InsertaAdelante(Lista lista, Nodo nodo, Nodo nuevoNodo)
     nuevoNodo.anterior  := nodo.anterior  
     nuevoNodo.siguiente  := nodo
     if nodo.anterior  == null
         lista.primerNodo  := nuevoNodo
     else
         nodo.anterior.siguiente  := nuevoNodo
     nodo.anterior  := nuevoNodo

También necesitamos una función para insertar un nodo al principio de una lista posiblemente vacía:

function InsertaAlPrincipio(Lista lista, Nodo nuevoNodo)
     if lista.primerNodo == null
         lista.primerNodo := nuevoNodo
         lista.ultimoNodo   := nuevoNodo
         nuevoNodo.anterior  := null
         nuevoNodo.siguiente  := null
     else
         InsertaAtras(lista, lista.primerNodo , nuevoNodo)

La siguiente función inserta al final:

function InsertaAlFinal(Lista lista, Nodo nuevoNodo)
     if lista.ultimoNodo == null
         InsertaAlPrincipio(lista, nuevoNodo)
     else
         InsertatAdelante(lista, lista.ultimoNodo, nuevoNodo)

Borrando un Nodo

Eliminar un nodo es más fácil que insertar, pero requiere un manejo especial si el nodo a eliminar es el primerNodo o el ultimoNodo:

function Elimina(Lista lista, Nodo nodo)
   if nodo.anterior == null
       lista.primerNodo  := nodo.siguiente
   else
       nodo.anterior.siguiente := nodo.siguiente
   if nodo.siguiente== null
       lista.ultimoNodo  := nodo.anterior
   else
       nodo.siguiente.anterior := nodo.anterior
   destroy nodo

Una sutil consecuencia del procedimiento de arriba es que eliminando el último nodo de una lista asigna a primerNodo y a ultimoNodo a null, y de esta forma maneja correctamente eliminar el último nodo de una lista de un solo elemento. Tampoco necesitamos separar los métodos "EliminarAtras" o "EliminarAdelante", porque en una lista doblemente enlazada podemos usar "Elimina(nodo.anterior)" o "Elimina(nodo.siguiente)" cuando sea válido. También se asume que está garantizado que el nodo siendo eliminado existe. Si el nodo no existe en la lista, entonces algún manejo de error será requerido.

Lista Doblemente Enlazada Circular

Recorriendo la lista

Asumir que algunNodo es algún nodo en una lista no vacía, este código recorre la lista empezando por' 'algunNodo:

Hacia adelante

nodo  := algunNodo
 do
     <Hacer algo con nodo.dato>
     nodo  := nodo.siguiente
 while nodo ≠ algunNodo

Hacia atrás

nodo  := algunNodo
 do
     <Hacer algo con nodo.dato>
     nodo  := nodo.anterior
 while nodo ≠ algunNodo

Notar que la condición se ejecuta al final del ciclo. Esto es importante para el caso en que la lista contiene el único nodo algunNodo.

Insertar un Nodo

Esta simple función inserta un nodo en una lista doblemente enlazada circular delante de un elemento dado:

function InsertaDelante(Nodo nodo, Nodo nuevoNodo)
     nuevoNodo.siguiente  := nodo.siguiente  
     nuevoNodo.anterior  := nodo
     nodo.siguiente.anterior  := nuevoNodo
     nodo.siguiente       := nuevoNodo

Para hacer un "InsertaAtras" podemos hacer simplemente "InsertaDelante(nodo.anterior, nuevoNodo)".

Insertar un elemento en una lista posiblemente vacía requiere una función especial:

function InsertaAlFinal(Lista lista, Nodo nodo)
     if lista.ultimoNodo == null
         nodo.anterior := nodo
         nodo.siguiente := nodo
     else
         InsertaDelante(lista.ultimoNodo, nodo)
     lista.ultimoNodo:= nodo

Para insertar en el principio simplemente hacemos "InsertaDelante(lista.ultimoNodo , nodo)".

Finalmente para eliminar un nodo debemos lidiar con el caso donde la lista es vacía:

function Elimina(Lista lista, Nodo nodo)
     if nodo.siguiente == nodo
         lista.ultimoNodo := null
     else
         nodo.siguiente.anterior := nodo.anterior
         nodo.anterior.siguiente := nodo.siguiente
         if nodo == lista.ultimoNodo
             lista.ultimoNodo:= nodo.anterior;
     destroy nodo

Implementaciones en Java

Lista doblemente enlazada

class NodoDoble{
    int informacion;
    NodoDoble siguiente, anterior;
    
    public NodoDoble(int info){
        informacion=info;
        siguiente=null;
        anterior=null;
    }
}

public class ListaDoblementeEnlazada{
    NodoDoble inicio, fin;
    
    public ListaDoblementeEnlazada(){
        inicio=fin=null;
    }
    
    boolean estaVacia(){
        if(inicio == null && fin == null)
            return true;
        return false;
    }
    
    void insertarEnfrente(int dato){
        NodoDoble nodito=new NodoDoble(dato);
        if(estaVacia()==true){
            inicio=nodito;
            fin=nodito;
        }
        else{
            nodito.siguiente=inicio;
            inicio.anterior=nodito;
        }
        inicio=nodito;
    }
    
    void insertarAtras(int dato){
        NodoDoble nodito=new NodoDoble(dato);
        if(estaVacia()==true){
            inicio=nodito;
            fin=nodito;
        }
        else{
            fin.siguiente=nodito;
            nodito.anterior=fin;
        }
        fin=nodito;
    }
    
    void eliminarEnfrente(){
        if(estaVacia()==true){
            System.out.println("Lista vacía, no se puede eliminar");
        }
        else if(inicio == fin){
            inicio=null;
            fin=null;
        }
        else{
            NodoDoble auxiliar=inicio;
            System.out.println("El dato que fue eliminado es: "+inicio.informacion);
            inicio=inicio.siguiente;
            auxiliar.anterior=null;
            auxiliar.siguiente=null;
            inicio.anterior=null;
        }
    }
    
    void eliminarAtras(){
        if(estaVacia() == true){
            System.out.println("Lista vacía, no se puede eliminar");
        }
        else if(inicio == fin){
            inicio=null;
            fin=null;
        }
        else{
            NodoDoble auxiliar=fin;
            System.out.println("El dato que fue eliminado es: "+fin.informacion);
            fin=fin.anterior;
            fin.siguiente=null;
            auxiliar.anterior=null;
            auxiliar.siguiente=null;
        }
    }
    
    void imprimirListaIzqDer(){//Impresion de inicio a fin
        if(estaVacia() == true){
            System.out.println("Lista vacía");
        }
        else if(inicio == fin){
           System.out.println(inicio.informacion);
        }
        else{
            NodoDoble auxiliar=inicio;
            while(auxiliar != null){
                System.out.println(auxiliar.informacion+" ");
                auxiliar=auxiliar.siguiente;
            }
        }
    }
    
    void imprimirListaDerIzq(){//Impresion de fin a inicio
        if(estaVacia() == true){
            System.out.println("Lista vacía");
        }
        else if(inicio == fin){
           System.out.println(inicio.informacion);
        }
        else{
            NodoDoble auxiliar=fin;
            while(auxiliar != null){
                System.out.println(auxiliar.informacion+" ");
                auxiliar=auxiliar.anterior;
            }
        }
    }
    
    public static void main(String arrr[]){
        ListaDoblementeEnlazada listita = new ListaDoblementeEnlazada();
        listita.insertarEnfrente(19);
        listita.insertarAtras(28);
        listita.insertarEnfrente(11);
        listita.insertarAtras(51);
        listita.eliminarEnfrente();
        listita.imprimirListaIzqDer();
        listita.insertarAtras(9);
        listita.imprimirListaIzqDer();
        listita.eliminarAtras();
        listita.imprimirListaDerIzq();
    }
}

Lista doblemente enlazada circular

class NodoDoble{
    int informacion;
    NodoDoble siguiente, anterior;
    
    public NodoDoble(int info){
        informacion=info;
        siguiente=null;
        anterior=null;
    }
}

class ListaDoblementeEnlazadaCircular{
    NodoDoble inicio;
    
    public ListaDoblementeEnlazadaCircular(){
        inicio=null;
    }
    
    void estaVacia(){
        if(inicio == null)
            return true;
        return false;
    }
    
    void insertarEnfrente(int dato){
        NodoDoble nodito=new NodoDoble(dato);
        if(estaVacia()==true){
            inicio=nodito;
            inicio.siguiente=inicio;
            inicio.anterior=inicio;
        }
        else{
            nodito.siguiente=inicio;
            inicio.anterior.siguiente=nodito;
            nodito.anterior=inicio.anterior;
            inicio.anterior=nodito;
        }
        inicio=nodito;
    }
    
    void insertarAtras(int dato){
        NodoDoble nodito=new NodoDoble(dato);
        if(estaVacia()==true){
            inicio=nodito;
            inicio.siguiente=inicio;
            inicio.anterior=inicio;
        }
        else{
            nodito.siguiente=inicio;
            inicio.anterior.siguiente=nodito;
            nodito.anterior=inicio.anterior;
            inicio.anterior=nodito;
        }
    }
    
    void eliminarEnfrente(){
        if(estaVacia()==true){
            System.out.println("Lista vacía, no se puede eliminar");
        }
        else if(inicio == inicio.siguiente){
            inicio=null;
        }
        else{
            NodoDoble auxiliar=inicio;
            System.out.println("El dato que fue eliminado es: "+inicio.informacion);
            inicio=inicio.siguiente;
            auxiliar.anterior.siguiente=inicio;
            inicio.anterior=auxiliar.anterior;
            auxiliar.anterior=null;
            auxiliar.siguiente=null;
        }
    }
    
    void eliminarAtras(){
        if(estaVacia() == true){
            System.out.println("Lista vacía, no se puede eliminar");
        }
        else if(inicio == inicio.siguiente){
            inicio=null;
        }
        else{
            NodoDoble auxiliar=inicio.anterior;
            System.out.println("El dato que fue eliminado es: "+fin.informacion);
            auxiliar.anterior.siguiente=inicio;
            inicio.anterior=auxiliar.anterior;
            auxiliar.anterior=null;
            auxiliar.siguiente=null;
        }
    }
    
    void imprimirListaIzqDer(){//Impresion de inicio a fin
        if(estaVacia() == true){
            System.out.println("Lista vacía");
        }
        else if(inicio == inicio.siguiente){
           System.out.println(inicio.informacion);
        }
        else{
            NodoDoble auxiliar=inicio;
            do{
                System.out.println(auxiliar.informacion+" ");
                auxiliar=auxiliar.siguiente;
            }while(auxiliar != inicio);
        }
    }
    
    void imprimirListaDerIzq(){//Impresion de fin a inicio
        if(estaVacia() == true){
            System.out.println("Lista vacía");
        }
        else if(inicio == inicio.siguiente){
           System.out.println(inicio.informacion);
        }
        else{
            NodoDoble auxiliar=inicio.previo;
            do{
                System.out.println(auxiliar.informacion+" ");
                auxiliar=auxiliar.previo;
            }while(auxiliar != inicio.previo);
        }
    }
    
    public static void main(String arrr[]){
        ListaDoblementeEnlazadaCircular listita = new ListaDoblementeEnlazadaCircular();
        listita.insertarEnfrente(19);
        listita.insertarAtras(28);
        listita.insertarEnfrente(11);
        listita.insertarAtras(51);
        listita.insertarAtras(9);
        listita.imprimirListaIzqDer();
        listita.eliminarAtras();
        listita.imprimirListaDerIzq();
    }
}

Lista doblemente enlazada

Algoritmos Básicos

Lista doblemente enlazada

Recorriendo la lista

Insertando un nodo

Borrando un Nodo

Lista Doblemente Enlazada Circular

Recorriendo la lista

Insertar un Nodo

Implementaciones en Java

Lista doblemente enlazada

Lista doblemente enlazada circular

Véase también

Related Articles