Deep Copy of Cons instance of Java List interface

Question

I am implementing a immutable List interface in java, a Cons class, essentially a list of lists ie; Cons(1,2,3)= Cons(1,Cons(2,Cons(3,null)))

I am trying to create a deepcopy of a cons but have had no success

Below is the class constructor methods and intialization:

public final class Cons<T> implements List<T> {

  private final T head;
  private List<T> tail; // non-final because of take and join

  Cons(T head, List<T> tail) {
    this.head = head;
    this.tail = tail;
  }

Below is the current Copy class:

    public Cons<T> copy(Cons<T> tocopy) {
      Cons<T> test=  new Cons<T>(this.head,this.tail);
      return test;
    }
}

Below is how its being called, I have confirmed this is simple a shallow copy or refrence to this by appending a value and comparing the copy to this:

public List<T> join(List<T> other) {

      Cons<T> cp= copy(this);
      if(other instanceof Nil){
          return cp;
      }
      Cons<T> ptr= (Cons<T>) other;

      for(; ptr instanceof Cons;ptr= (Cons<T>) ptr.tail){
          if(!(ptr.tail instanceof Cons)){
              cp.append(ptr.head);
              break;
          }
          else{
              cp.append(ptr.head);
          }
      }
      return cp;
  }

In addition I have tried Cons copy = cons(this.head, this.tail),

Answer 1

I'm not sure why you made tail non-final when you said you are making an immutable cons list. Also ,tail is of type List (java.util.List?) when it should be of a type that is either Cons or Nil.

Let's fix those problems by using a sealed interface ConsList<T>, which Cons<T> and Nil<T> implement. We also make Cons<T> and Nil<T> records so that they are immutable.

sealed interface ConsList<T> permits Cons, Nil {}
record Cons<T>(T head, ConsList<T> tail) implements ConsList<T> { }
record Nil<T>() implements ConsList<T> {}

Now copy can be implemented like this:

static <T> ConsList<T> copy(ConsList<T> list) {
    Deque<T> stack = new ArrayDeque<>();
    ConsList<T> temp = list;
    while (temp instanceof Cons<T> cons) {
        stack.push(cons.head());
        temp = cons.tail();
    }
    temp = new Nil<>();
    while (!stack.isEmpty()) {
        temp = new Cons<>(stack.pop(), temp);
    }
    return temp;
}

This could also be done with recursion, but unlike functional languages like Haskell, Java doesn't have much optimisations for recursive code like that, so I don't recommend that. The stack would likely overflow for slightly larger lists.

What you will realise though, is that you don't actually need a copy method like this. In your join method, the only reason why you make a deep copy is because you call cp.append later on. Though you did not show the implementation, I can only assume it mutates cp in some way. That is not something an immutable data type should do.

Instead, you should implement join by collecting the elements of each list into a stack, and then making a joined list by popping from the stack.

// in ConsList<T> interface
default ConsList<T> join(ConsList<T> other) {
    Deque<T> stack = new ArrayDeque<>();

    // push "this"
    ConsList<T> temp = this;
    while (temp instanceof Cons<T> cons) {
        stack.push(cons.head());
        temp = cons.tail();
    }

    // push other
    temp = other;
    while (temp instanceof Cons<T> cons) {
        stack.push(cons.head());
        temp = cons.tail();
    }

    // pop everything from the stack and make a new ConsList<T>
    temp = new Nil<>();
    while (!stack.isEmpty()) {
        temp = new Cons<>(stack.pop(), temp);
    }
    return temp;
}

You can also write this with recursion which would make the code look a lot "nicer", but again, I don't recommend doing so. That said, the code duplication can be slightly refactored:

default ConsList<T> join(ConsList<T> other) {
    Deque<T> stack = new ArrayDeque<>();
    toStack(this, stack);
    toStack(other, stack);
    return fromStack(stack);
}

static <T> void toStack(ConsList<T> list, Deque<T> stack) {
    ConsList<T> temp = list;
    while (temp instanceof Cons<T> cons) {
        stack.push(cons.head());
        temp = cons.tail();
    }
}

static <T> ConsList<T> fromStack(Deque<T> stack) {
    ConsList<T> temp = new Nil<>();
    while (!stack.isEmpty()) {
        temp = new Cons<>(stack.pop(), temp);
    }
    return temp;
}