java - doubly - linkedlist vs arraylist

¿A qué se refiere "esto" en el ejemplo de Lista enlazada?

Question

Así que estoy hojeando la entrevista Cracking the Coding para repasar algunas cuestiones de la entrevista y me encontré con esta implementación de la lista vinculada, y tal vez ha pasado un tiempo, pero está pasando por alto por completo. Entiendo la mayor parte, a excepción de una línea específica, y me está tirando. Publicaré el código a continuación (como referencia, el libro no menciona el idioma, pero parece ser Java).

class Node {
Node next = null;
int data;
public Node(int d) {
data = d;
}
void appendToTail(int d) {
Node end = new Node(d);
Node n = this;
while(n.next != null) {
n = n.next;
}
n.next = end;
}
}

Estoy un poco confundido en la línea: Node n = this - No estoy seguro de a qué se refiere esto, a menos que esté hablando del next - ¿por qué no simplemente establecerlo como null en ese caso?

Answer 1

Como esta es una lista vinculada, todos los nodos están conectados y usted tiene un nodo de inicio (raíz). Entonces cuando lo use se vería así:

Node root = new Node(6); //need an instance first
root.appendToTail(5);
root.appendToTail(3);
//6->5->3

Dado que los nodos están conectados, necesito un nodo de inicio y necesito verificar si tiene un próximo nodo cuando sí. Necesito buscar más profundamente. Cuando un nodo no tiene un próximo nodo, es el último actual y puede agregar mi nuevo nodo. Entonces esto en Java se refiere a la instancia actual de una clase. En mi ejemplo, el Nodo raíz (porque yo llamo root.appendToTail). Entonces el método buscará desde el Nodo raíz (valor 6) el próximo Nodo sin un Siguiente Nodo (el que tiene el valor 3) y lo agregará allí. Si puedo obtener una referencia secundaria y llamaría a child3.appendToTail, el método buscaría desde child3 en lugar de comenzar desde mi raíz.

Al establecer n en nulo y reescribir el tiempo para ir de aquí a continuación , tendría un problema cuando el nodo actual que utiliza appendToTail no tuviera un próximo nodo y se lanzaría una NullPointerException.

Answer 2

Como puedes ver en este código

class Node {
//
void appendToTail( int d ) {
Node *end = new Node( d );
Node n = this;
// ...
}
} 

Su Node clase tiene una referencia a un Node en su definición.

La línea: Node *end = new Node( d ); significa que dentro de un Node hay una referencia a otro nodo.

La línea Node n = this; significa dentro de un Node la referencia a ese nodo en sí , está representado por this . Ergo, n también es una referencia a dicho nodo en sí mismo.

Answer 3

Cualquier instancia de nodo puede llamar a appendToTail() .

Observe cómo antes, aquí, de hecho, Node no se agrega a la cola de la lista, lo que sucede aquí es que se crea un nuevo nodo y se agrega a la cola, no aquel en el que se invoca el método.

Para que esto suceda, primero debemos encontrar la cola de la lista dada el Node actual.

 // n is pointing to current Node
while(n.next != null) {
n = n.next;
}

Una vez que encontramos el nodo que tiene next == null, esta es la cola de la lista, por lo que ahora podemos agregar un nuevo Node a la cola:

 // n points to current tail before next line is invoked
n.next = end;

En cuanto a por qué hay línea:

 Node n = this;

Bien, ya que no existe una clase LinkedList que mantenga referencia al encabezado, usted debe poder iterar desde cualquier Nodo dado. Eso es lo que sucede aquí, comienzas la iteración desde el Nodo al que se llama appendToTail , pero ese Nodo puede ser cualquier cosa en este punto, de la cabeza a la cola.

Como nota al margen, si implementa la Lista Vinculada a mano, asegúrese de tener realmente la clase LinkedList que ofrecerá métodos como add , get , size , appendToTail y más, en lugar de ponerlos en la clase Node.

Answer 4

Esto es Java

" this " se refiere a la instancia específica de la clase en la que se realiza la llamada. En este caso, " this " se refiere al Node clase específico con el que se está tratando. Mientras que la variable " end " crea una versión nueva y separada de la clase Node que se construye utilizando la pasada " d ".

Answer 5

Node n = this; significa n referencias de objetos al objeto que está llamando a este método. Entonces, el método está girando al siguiente objeto hasta que el próximo objeto sea nulo y se asigne un nodo end al final.

Veamos

1 -- 2 -- 3 -- 4
*
|
*
obj

tiene un objeto obj que apunta al nodo 1. Cuando llama a obj.appendToTail(5)

Node end = new Node(d); //new node is created to add to the end.
Node n = this; //local n object is referenced to node 1(or obj)
while(n.next != null) {
n = n.next;
}
//n here is node 4 since there is no next node to 4
n.next = end; //node 5 is tail now

Resultado final: 1 -- 2 -- 3 -- 4 -- 5

Answer 6

this refiere a una instancia específica de un objeto de una clase. Dado que los objetos se construyen, puede haber múltiples instancias de una clase, pero el uso de this palabra clave le permite obtener una referencia a sí mismo, lo que significa una referencia a la instancia específica del objeto cuyo método se está llamando.

La lista enlazada es una colección de nodos que están, bueno, unidos entre sí. Cuando llame a appendToTail() el nodo verá todos los objetos de Nodo vinculados a sí mismo y seguirá la cadena. Para que se haga referencia a sí mismo para seguir su propia cadena, se usa this palabra clave.

También pregunta por qué null no se usa en este caso para inicializar n . Esto causaría una NullPointerException cuando n.next se llama por primera vez en la restricción de bucle, por lo que su propia referencia se utiliza como punto de partida para la iteración de la lista enlazada.

Esto (juego de palabras intencionado) puede ser un tema confuso al principio, pero use el ejemplo que proporcionó.

Node n = this;
while(n.next != null) {
n = n.next;
}

Vamos a pretender que hay 4 objetos actualmente vinculados en nuestra lista y, para simplificar, el objeto Node al que se appendToTail() es el encabezado de la lista. Aquí está el valor de referencia del Nodo n que se conserva en cada iteración de bucle del fragmento de arriba.

1. Estamos señalando a nosotros mismos - this
2. Señalando el segundo elemento en la lista vinculada. - this.next
3. Señalando el siguiente elemento - this.next.next
4. Señalando el último elemento de la lista - this.next.next.next

El ciclo finalizó por lo que actualmente es la referencia de n = this.next.next.next . Luego establecemos el siguiente valor de n (donde n apunta actualmente al final de la cadena vinculada) al nuevo objeto que creamos al principio de nuestro método, lo que lo convierte en el nuevo final de la lista. ( n.next = end ahora es equivalente a this.next.next.next.next = end ).

Edición semi-innecesaria: Esto se explica en términos de Java. Parece que alguien agregó la etiqueta C ++ después de escribir esta respuesta