Why does the last 2 elements gets repeated in the following implementation of double-ended list?

user_14105067 0
Viewed 43

This is the Main class with main method for generating a double-ended list, remove and display its elements.

public class Main {
    Link first, last;

    public static void main(String args[]) {
    
        Main ob = new Main();

        Link arr[] = {
            new Link(1), new Link(2), new Link(3)
        };
        int len = 3;

        for(int i=0;i<len;i++)
            ob.insertFirst(arr[i]);
        System.out.print("Data in the list: ");
        while(ob.first!=null)
            System.out.print(ob.removeAndReturn()+", ");

        for(int i=0;i<len;i++)
            ob.insertLast(arr[i]);
        System.out.print("\nData in the list: ");
        while(ob.first!=null)
            System.out.print(ob.removeAndReturn()+", ");
    
    }

    void insertFirst(Link arg) {
        if(isEmpty())
            last = arg;
        arg.next = first;
        first = arg;
    }
    // This removeAndReturn() method returns the Object data the link is holding and removes that Link from the list
    Object removeAndReturn() {
        Object ret = null;
        try {
            ret = first.data;
            if(first.next==null)
                last = null;
            first = first.next;
        }catch(NullPointerException NPe) {
            System.out.println("You are referring to a null.\nLinked List is empty.");
        }
        return ret;
    }

    void insertLast(Link arg) {
        if(isEmpty())
            first = arg;
        else
            last.next = arg;
        last = arg;
    }

    boolean isEmpty() {
        return first==null;
    }
}


class Link {
    Object data;
    Link next;
    Link(Object data) {
        this.data = data;
    }
}

When executing, it gives the following output:

Data in the list: 3, 2, 1,

Data in the list: 1, 2, 3, 2, 3, 2, 3, 2, 3, 2, 3, 2, 3, 2, 3, 2, 3, 2, ... {truncated}

Here the last two elements gets repeated in the output. I tried nullifying both the Link variables first and last before calling ob.insertLast(arr[i]) but it gives the same output.

Update:

  • private keywords are removed from the complete method signature for methods in the Main class other than main(String args[]) method and rmF() method is changed to removeAndReturn().
nodes data-structures list algorithm java
1 Answers

The main problem in your code lies in the fact that you're using the exact same nodes (the ones within the arr) to fill your list with head and tail insertions.

In fact, once you perform your first head insertion, those nodes have been linked to each other like this:

(3) => (2) => (1) => null

So, when you're performing your second insertion, you have that node 1 points to node 2, node 2 points to node 3, and theoretically node 3 should point to null since it's supposed to be the last element. However, node 3's next field is still pointing to node 2 from the previous insertion. This creates a loop where node 2 and node 3 keep pointing at each other; thus yielding the infinite loop you're experiencing.

(1) => (2) => <= (3)

To fix your problem you could either reset the next field of your nodes before re-using them (poor solution) or work with the actual data you need to structure rather than the nodes. In fact, the user of your class shouldn't be bothered with the details of your implementation and should only care about the info to be stored/represented (in your case int numbers).

This is a possible solution to your problem:

public class Main {
    Link first, last;

    public static void main(String args[]) {

        Main ob = new Main();

        //Array of int not of links
        int[] arr = {1, 2, 3};
        int len = 3;

        for (int i = 0; i < len; i++)
            ob.insertFirst(arr[i]);

        System.out.print("Data in the list: ");
        while (ob.first != null)
            System.out.print(ob.removeAndReturn() + ", ");

        for (int i = 0; i < len; i++)
            ob.insertLast(arr[i]);

        System.out.print("\nData in the list: ");
        while (ob.first != null)
            System.out.print(ob.removeAndReturn() + ", ");

    }

    //------ CORRECTION ------ 
    //The method should receive the info the user needs to store.
    //It will then be up to you to represent it as a Link or whatever
    //internal structure you're going to use tomorrow. Don't bind the
    //user to your internal implementation.
    //------------------------
    void insertFirst(int arg) {
        //Generating a new node (or link) based on the given info
        Link l = new Link(arg);

        if (isEmpty())
            last = l;
        l.next = first;
        first = l;
    }

    // This removeAndReturn() method returns the Object data the link is holding and removes that Link from the list
    Object removeAndReturn() {
        Object ret = null;
        try {
            ret = first.data;
            if (first.next == null)
                last = null;
            first = first.next;
        } catch (NullPointerException NPe) {
            System.out.println("You are referring to a null.\nLinked List is empty.");
        }
        return ret;
    }

    //-------- CORRECTION --------
    //same explanation given above
    //----------------------------
    void insertLast(int arg) {
        //Generating a new node (or link) based on the given info
        Link l = new Link(arg);

        if (isEmpty())
            first = l;
        else
            last.next = l;
        last = l;
    }

    boolean isEmpty() {
        return first == null;
    }
}

Lastly, Do not capture RuntimeException. These are unchecked exceptions, not checked. You should investigate on their origin rather than simply catching them. What you've written is a bad practice.

https://docs.oracle.com/javase/tutorial/essential/exceptions/runtime.html

As @JayC667 has already said, you could improve some designing and naming of your class, methods and variables. There are some conventions, especially when talking about data structures. For example:

  • Your class is called Main but it describes a List, a name like MyList would have been better.

  • Your utility class, Link, could have been placed within MyList as a static nested class and probably named Node (it's a better fit).

  • Some of your methods' names were a bit too cryptic. Self-explanatory names will better help the users of your class.

  • Avoid accessing the internal state of another object from outside (list.first != null). Methods should be your way to go to interrogate an object's state.

  • Using generic types could have been a better implementation than just Object as generics provide: strict checks at compile time, avoid casting a more type safety, the ability to re-use the same code for different data types.

https://docs.oracle.com/javase/tutorial/java/generics/why.html

Here is a link to an implementation with the suggestions made above:

https://www.jdoodle.com/iembed/v0/s7C

user_44156250
Related