es.davy.ai

Preguntas y respuestas de programación confiables

¿Tienes una pregunta?

Si tienes alguna pregunta, puedes hacerla a continuación o ingresar lo que estás buscando.

  • es.davy.ai/
  • Programación /
  • Cómo copiar una lista enlazada correctamente utilizando el constructor de copia en Java?

Cómo copiar una lista enlazada correctamente utilizando el constructor de copia en Java?

11 Jul, 2023 Programación

No puedo utilizar correctamente el constructor de copia para hacer una copia de LinkedList.

Considere este ejemplo:

public class LinkedList {

    public class Node {
        Node next;
        int val;
        Node(int val) {
            this.val = val;
            next = null;
        }
    }
    public Node head;
    public Node current;
    public LinkedList() {

    }


    public LinkedList(LinkedList another) {
        this.head = another.head;
        this.current = another.current;
    }

    public boolean empty() {
        return head == null;
    }

    public void insert(int e) {

        if (empty()) {
            head = current = new Node(e);
            return;
        }
        Node currNode = new Node(e);
        Node tmp = current;
        tmp.next = currNode;
        current = currNode;


    }

    public void display() {
        Node currNode = head;
        while (currNode != null) {
            System.out.println(currNode.val);
            currNode = currNode.next;
        }
    }
}

Hice una copia de la lista enlazada usando el constructor de copia, el código en el método principal es el siguiente:

public class Main {
    public static void main(String [] args) {
        LinkedList ls = new LinkedList();
        ls.insert(5);
        ls.insert(6);
        ls.insert(7);

        LinkedList another = new LinkedList(ls);

        another.display();
        another.insert(0);
        ls.display(); // la salida esperada es 5 6 7 
    }
}

La salida del código es “5 6 7 5 7 6 0”, sin embargo, esperaba que fuera “5 6 7” porque hice una copia, no debería afectar a “ls”. ¿Qué está pasando? ¿Cómo arreglarlo para obtener la salida esperada?

Tags:  , ,

Answer

  1. Avatar for davy.ai
    davy.ai

    El problema con la implementación actual del constructor de copia es que solo copia las referencias de los nodos de la lista enlazada original a la lista enlazada copiada, lo que significa que los cambios realizados en los nodos de la lista enlazada copiada afectarán también a los nodos de la lista enlazada original.

    Para solucionar este problema, necesitamos crear una nueva instancia de cada nodo en la lista enlazada original y hacer que la lista enlazada copiada apunte a estas nuevas instancias en lugar de a las originales. Podemos lograr esto modificando el constructor de LinkedList de la siguiente manera:

    public LinkedList(LinkedList another) {
  if (another.head == null) {
    return;
  }
  Node currNode = another.head;
  Node prevNode = null;
  Node newHead = new Node(currNode.val);
  this.head = newHead;
  prevNode = newHead;
  currNode = currNode.next;
  while (currNode != null) {
    Node newNode = new Node(currNode.val);
    prevNode.next = newNode;
    prevNode = newNode;
    currNode = currNode.next;
  }
  this.current = prevNode;
}

    En este constructor modificado, primero verificamos si la lista enlazada original está vacía o no. Si está vacía, simplemente regresamos. De lo contrario, creamos una nueva instancia de nodo para cada nodo en la lista enlazada original y hacemos que la lista enlazada copiada apunte a estas nuevas instancias. También llevamos un seguimiento del último nodo en la lista enlazada copiada utilizando la variable prevNode, que actualizamos después de agregar cada nuevo nodo.

    Con esta modificación, la salida del código proporcionado será 5 6 7 0 para la lista enlazada copiada y 5 6 7 para la lista enlazada original, que es el comportamiento esperado.

Comments are closed.