algorithm - tipos - ¿Cuándo la lista de enlaces dobles es más eficiente que la lista de enlaces individuales?

enlace simple doble y triple del carbono

Question

En una entrevista hoy, me hicieron la pregunta.

Además de responder al reverso de la lista y al atravesarlo tanto hacia adelante como hacia atrás, había algo "fundamental" en él que el entrevistador seguía poniendo de relieve. Me di por vencido y, por supuesto, después de la entrevista hice un poco de investigación. Parece que la inserción y eliminación son más eficientes en la lista doblemente enlazada que en la lista individualmente vinculada. No estoy seguro de cómo puede ser más eficiente para una lista doblemente vinculada, ya que es obvio que se requieren más referencias para cambiar. ¿Alguien puede explicar el secreto detrás? Honestamente investigué un poco y no pude entender, siendo mi principal problema el hecho de que todavía se necesita una búsqueda de O (n) para la lista de doble enlace.

Answer 1

"Además de responder a la inversión de la lista y de atravesar hacia adelante y hacia atrás, había algo" fundamental "''.

Nadie parece haber mencionado: en una lista doblemente vinculada, es posible reinsertar un elemento eliminado simplemente con un puntero al elemento eliminado. Ver el documento de Knuth''s Dancing Links. Creo que eso es bastante fundamental.

Answer 2

Aquí están mis pensamientos sobre la Lista doblemente enlazada:

• Tiene listo el acceso / insertar en ambos extremos.

• puede funcionar como una cola y una pila al mismo tiempo.

• La eliminación del nodo no requiere punteros adicionales.

• Puede aplicar el recorrido de Hill-Climb ya que tiene acceso en ambos extremos.

• Si está almacenando valores numéricos, y su lista está ordenada, puede mantener un puntero / variable para la mediana, luego la operación de búsqueda puede ser altamente óptima usando el enfoque estadístico.

Answer 3

Aquí hay un código que me lo dejó más claro ... Tener:

class Node{
      Node next;
      Node prev;
}

ELIMINAR un nodo en una LISTA DE UN SOLO ENLACE -O (n) -

No sabe cuál es el nodo anterior, por lo que debe recorrer la lista hasta que lo encuentre:

deleteNode(Node node){
    prevNode = tmpNode;
    tmpNode = prevNode.next;

    while (tmpNode != null) {
        if (tmpNode == node) {
            prevNode.next = tmpNode.next;
        }
        prevNode = tmpNode;
        tmpNode = prevNode.next;
    }
}

BORRAR un nodo en una LISTA DOBLE DE ENLACE -O (1) -

Simplemente puede actualizar los enlaces de esta manera:

deleteNode(Node node){
    node.prev.next = node.next;
    node.next.prev = node.prev;
}

Answer 4

La inserción es claramente menos trabajo en una lista vinculada individualmente, siempre y cuando esté satisfecho con insertar siempre en la cabecera o después de algún elemento conocido. (Es decir, no puede insertar antes de un elemento conocido, pero consulte más abajo).

La eliminación, por otro lado, es más complicada porque necesita conocer el elemento antes del elemento a eliminar.

Una forma de hacerlo es hacer que la API de eliminación funcione con el predecesor del elemento que se eliminará. Esto refleja la API de inserción, que toma el elemento que será el predecesor del nuevo elemento, pero no es muy conveniente y es difícil de documentar. Sin embargo, generalmente es posible. En general, llega a un elemento en una lista al recorrer la lista.

Por supuesto, puedes buscar en la lista desde el principio para encontrar el elemento que se eliminará, para que sepas cuál era su predecesor. Eso supone que la API de eliminación incluye el encabezado de la lista, lo cual también es inconveniente. Además, la búsqueda es estúpidamente lenta.

La forma en que casi nadie usa, pero que en realidad es bastante efectiva, es definir un iterador de lista enlazado individualmente para que sea el puntero al elemento que precede al objetivo actual del iterador. Esto es simple, solo una indirección más lenta que usar un puntero directamente al elemento, y hace que tanto la inserción como la eliminación sean rápidas. La desventaja es que borrar un elemento puede invalidar otros iteradores para listar elementos, lo cual es molesto. (No invalida el iterador al elemento que se está eliminando, lo que es bueno para los cruces que eliminan algunos elementos, pero eso no es mucha compensación).

Si la eliminación no es importante, tal vez porque las estructuras de datos son inmutables, las listas de enlace único ofrecen otra propiedad realmente útil: permiten compartir la estructura. Una lista con un solo enlace puede ser felizmente la cola de varias cabezas, algo que es imposible para una lista doblemente vinculada. Por esta razón, las listas de enlace único han sido tradicionalmente la estructura de elección simple para los lenguajes funcionales.

Answer 5

Si va a eliminar un elemento en una lista vinculada, necesitará vincular el elemento anterior al siguiente elemento. Con una lista doblemente vinculada, tiene acceso rápido a ambos elementos porque tiene enlaces a ambos.

Esto supone que ya tiene un puntero al elemento que necesita eliminar y no hay ninguna búsqueda involucrada.