ultimo - listas simples en java

¿Insertar un nodo en una lista vinculada en tiempo constante?

Question

Estoy trabajando en una tarea que me dice que asuma que tengo una lista individualmente vinculada con un encabezado y nodos de cola. Quiere que inserte un elemento y antes de la posición p. ¿Alguien puede mirar mi código y decirme si estoy en el camino correcto? Si no, ¿me puede dar algún consejo o sugerencia (sin juego de palabras)?

tmp = new Node();
tmp.element = p.element;
tmp.next = p.next;
p.element = y;
p.next = tmp;

Creo que puedo estar equivocado porque no utilizo los nodos de encabezado y cola a pesar de que se mencionan específicamente en la descripción del problema. Estaba pensando en escribir un ciclo while para recorrer la lista hasta que encontrara p y abordar el problema de esa manera, pero eso no sería constante, ¿no?

Answer 1

Lo que no estás haciendo es vincular el elemento que estaba antes de p antes de la inserción de y a y. Entonces, mientras y se inserta antes de p, nadie está apuntando a y ahora (al menos no en el código recortado que mostró).

Solo puede insertar en tiempo constante si conoce las posiciones de los elementos entre los que debe insertar y. Si tiene que buscar esa posición, nunca podrá tener una inserción de tiempo constante en una sola lista de enlaces.

Answer 2

Solo escríbelo si te quedas atascado con un algoritmo:

// First we have a pointer to a node containing element (elm)
// with possible a next element.
// Graphically drawn as:
// p -> [elm] -> ???
tmp = new Node();
// A new node is created. Variable tmp points to the new node which
// currently has no value.
// p -> [elm] -> ???
// tmp -> [?]
tmp.element = p.element;
// The new node now has the same element as the original.
// p -> [elm] -> ???
// tmp -> [elm]
tmp.next = p.next;
// The new node now has the same next node as the original.
// p -> [elm] -> ???
// tmp -> [elm] -> ???
p.element = y;
// The original node now contains the element y.
// p -> [y] -> ???
// tmp -> [elm] -> ???
p.next = tmp;
// The new node is now the next node from the following.
// p -> [y] -> [elm] -> ???
// tmp -> [elm] -> ???

Tienes el efecto requerido, pero puede ser más eficiente y apuesto a que ahora puedes descubrirlo tú mismo.

Es más claro escribir algo como:

tmp = new Node();
tmp.element = y;
tmp.next = p;
p = tmp;

Lo cual por supuesto no funciona si p no es mutable. Pero su algoritmo falla si p == NULL.

Pero lo que quise decir es que si tienes problemas con un algoritmo, simplemente escribe los efectos. Especialmente con árboles y listas vinculadas, debe estar seguro de que todos los punteros apuntan en la dirección correcta, de lo contrario, obtendrá un gran desorden.

Answer 3

Sugerencia : la inserción en una lista vinculada solo es constante cuando la posición n = 0, o el encabezado de la lista. De lo contrario, la complejidad del caso más desfavorable es O (n) . Eso no quiere decir que no pueda crear un algoritmo razonablemente eficiente, pero siempre tendrá al menos una complejidad lineal.

Answer 4

¿Qué hay de usar el código que ya está allí? LinkedHashMap, LinkedList, LinkedHashSet. También puedes consultar el código y aprender de él.

Answer 5

La razón por la cual el encabezado y el nodo de la cola se dan en la pregunta es para actualizar la referencia del encabezado y la cola si el nodo de reemplazo que su creación pasa a ser el encabezado o la cola. En otras palabras, el nodo anterior dado es un encabezado o cola.

Answer 6

create a node ptr
ptr->info = item //item is the element to be inserted...
ptr->next = NULL
if (start == NULL) //insertion at the end...
start = ptr
else
temp = ptr
while (temp->next != NULL)
temp = temp->next
end while
end if
if (start == NULL) //insertion at the beginning...
start = ptr
else
temp = start
ptr->info = item
ptr->next = start
start = ptr
end if
temp = start //insertion at specified location...
for (i = 1; i < pos-1; i++)
if (start == NULL)
start = ptr
else
t = temp
temp = temp->next
end if
end for
t->next = ptr->next
t->next = ptr

Answer 7

En una LinkedList única, solo agregar un nodo al comienzo de la lista o crear una lista con un solo nodo tomaría O (1). O como han proporcionado el TailNode también Insertar el nodo al final de la lista tomaría O (1).

cualquier otra operación de inserción tomará O (n).