I can't properly use the copy constructor to make a copy of LinkedList.

Consider this example:

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;
        }
    }
}

I made a copy of linked list using copy constructor, code in main is below:

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(); // expected output is 5 6 7 
    }
}

The output of the code is 5 6 7 5 7 6 0, however I expected it to be 5 6 7 because I made copy, it won't affect ls. What's going in? How to fix that to get the expected output?

CodePudding user response：

Something like

public LinkedList(const LinkedList& another) {
    this->head = this->current = another.copy()
}

private LinkedList copy( const LinkedList& another ) {
    Node last_node = null;
    Node new_first = null;
    for ( Node next_node = another->head; next_node != null; 
          next_node = next_node->Next ) {
        Node new_node = new Node( next_node );
        if ( new_first == null )
            new_first = new_node;
        if ( last_node != null )
            last_node.Next = new_node
        last_node = next_node;
     }
     return new_first;
}

NOTE that I also changed the signature of the copy constructor; in general, the argument should be a const reference. Also, my simple solution contains a storage leak, since it isn't deleting the current nodes of "this" before copying from another.

CodePudding user response：

Hello and welcome to stackoverflow community

Here is a solution to your post:

You can modify the LinkedList constructor as below:

    public LinkedList(LinkedList another) {
        Node previous = another.head;
        Node temp = null;
        // represent a reference to the head of the new linkedList
        Node first = null;
    while (previous != null) {
        Node node = new Node(previous.val);
        if (first == null) {
            first = node;
            temp = first;
        } else {
            temp.next = node;
            temp = temp.next;
        }

        previous = previous.next;
    }

        // set the head
        this.head = first;
        // Temp hold a reference of the last node of the another passed as parameter
        this.current = temp;

}

I added comments to the main method to show the linked list content before and after insertion:

        public static void main(String [] args) {
        LinkedList ls = new LinkedList();
        ls.insert(5);
        ls.insert(6);
        ls.insert(7);
        System.out.println("------------ begin display initial list ls");
        ls.display();
        System.out.println("------------ end display initial list ls");

        LinkedList another = new LinkedList(ls);

        System.out.println("------------ begin display another list before insert");
        another.display();
        System.out.println("------------ end display another list before insert");
        System.out.println("------------ Insert 0 in another linked list");

        another.insert(0);

        System.out.println("------------ begin display another list after insert");
        another.display();
        System.out.println("------------ end display another list after insert");
        System.out.println("--------Initial list must not be modified------------");
        ls.display(); // expected output is 5 6 7
        System.out.println("--------end------------");
    }

This is the result in console

 ------------ begin display initial list ls
 5
 6
 7
 ------------ end display initial list ls
 ------------ begin display another list before insert
 5
 6
 7
 ------------ end display another list before insert
 ------------ Insert 0 in another linked list
 ------------ begin display another list after insert
 5
 6
 7
 0
 ------------ end display another list after insert
 --------Initial list must not be modified------------
 5
 6
 7
 --------end------------

We have the expected result.