Java: Pass by reference / ListIterator.add()

Java doesn't pass variables by reference. In that case, how do data structures like ListIterator make changes to their corresponding list?

Here is an example iterator I am writing:

public class OdpIterator<E> implements ListIterator<E> {

    private OdpList<E> list;
    pr开发者_如何学Pythonivate int cursor;

    public OdpIterator(OdpList<E> list) {
        this.list = list;
    }

    @Override
    public void add(E arg0) {
        list.add(arg0);
    }

But then when I try to change list through add(), it doesn't change the underlying list, so the following test fails:

OdpList<Integer> list = new OdpList<Integer>();
ListIterator<Integer> iter = list.listIterator();
iter.add(42);
assertTrue(list.contains(42));

OdpList add: I believe that it is correct, as it passes its unit tests.

@Override
public boolean add(E arg0) {
    ListCell<E> cell = new ListCell<E>(arg0);

    if (size() > 0) { //if something is already in the list
        tail.setNext(cell);
        tail = cell;
    }
    else {
        head = cell;
        tail = cell;
    }
    return true;
}

ListCell constructor:

public class ListCell<T> {
    public ListCell(T arg0) {
        this.datum = arg0;
        next = null;
    }
}

OdpList listIterator:

@Override
public ListIterator<E> listIterator() {
    return new OdpIterator<E>(this);
}

OdpList contains:

@Override
public boolean contains(Object arg0) {
    return indexOf(arg0) == -1;
}

@Override
public int indexOf(Object arg0) {
    return findAfter(head, arg0, 0);
}

private int findAfter(ListCell<E> o, Object search, int soFar) {
    if (o == null) {
        return -1;
    }
    if (o.getDatum() == null && search != null) {
        return findAfter(o.getNext(), search, soFar + 1);           
    }
    if ((o.getDatum() == null && search == null) || o.getDatum().equals(search)) {
        return soFar;
    }

    return findAfter(o.getNext(), search, soFar + 1);
}

How do I do this? Or am I misunderstanding how iterators work?

---

I almost hate to say this after all the mental exercises people have been going through, but... the problem is simply a typo.

@Override
public boolean contains(Object arg0) {
    return indexOf(arg0) == -1;
}

should be

@Override
public boolean contains(Object arg0) {
    return indexOf(arg0) != -1;
}

contains was returning true only if the object was not in the list!

---

The reason it works is Java passes reference types about. They are passed by value and this is a source of confusion for many. In my opinion this confusion is then enhanced when people start saying Java passing objects by reference and primitives by value. Even more so if you ever use a language that does support both.

So below I've gone off on one a little and described the best I can how it works.

---

Java passes reference types by value. Java Ranch has two great articles describing this:

1. Cup Size -- a story about variables
2. Pass-by-Value Please (Cup Size continued)

I have also posted about this here using ASCII art. Let us do so again.

We have the method:

void test(StringBuilder fred) {
    fred.append("Fred");
}

And the following code:

StringBuilder b = new StringBuilder();
test(b);

---

StringBuilder b = new StringBuilder();

In memory this gives something like:

b -- > ""

---

test(b);

This then creates a new variable "b", but this variable points to the same string buffer.

In memory this gives something like:

b -- +
     +-> ""
fred-+

---

fred.append("Fred");

While "fred" and "b" are different variables, the point to the same thing. So changing "fred" also changes "b".

In memory this gives something like:

b -- +
     +-> "Fred"
fred-+

---

 }

Now "fred" drops out of scope and is eaten.

b -- > "Fred"

---

This differs from "pass by reference" in that PBR b and fred become one. In the example above it would have little difference, except anywhere something looks like:

b -- +
     +-> "Fred"
fred-+

in PBR it looks like: b, fred --> "Fred"

PBR really shows itself when you try to change where "fred" points too. If we alter the method to:

void test(StringBuilder fred) {
    fred = new StringBuilder("Fred");
}

we can see the difference.

---

StringBuilder b = new StringBuilder();

In memory this gives something like:

b -- > ""

---

test(b);

For Passing reference types by value we get something like:

b -- +
     +-> ""
fred-+

but for PBR we get:

b, fred--> ""

---

    fred = new StringBuilder("Fred");

Now we will see the difference. In Pass Reference By Value (what Java supports) we get:

b --> ""

fred--> "Fred"

See how we have now broken the link between them. In PBR however we keep the link.

           "" // Old string builder now float in memory all lost and alone.
b, fred--> "Fred"

---

Java passes all Objects by reference. It passes primitives by value.

Your code should change the underlying list. I would check your OdpList class for the problem.

---

Some of the code is missing—the definition of OdpList—so it's hard to say what is happening here. The code that is shown looks correct. In the list implementation, I'd expect to see something like this:

public ListIterator<T> listIterator() {
  return new OdpIterator<T>(this);
}

Java doesn't pass references, but it does pass references by value. So there should be no problem in modifying the list, as long as its reference is available.

---

Why should list.listIterator() return an OdpIterator (no code of OdpList seen)? And who says "Java doesn't pass variables by reference"? All instance parameters are passed by value, but a reference to an object is a pointer copied to be passed by value. Refering this copy will always change the original object!

---

First of all, you are not passing primitive int type by value. You are passing autoboxed Integer objects created in-place by reference. There are many good reasons to stay away from autoboxing.

Without looking at full OdpList listing it's hard to tell, but on examination of OdpList.add, looks like internally you have a list of ListCells, not a list of Integers. So in a sense you are looking for an orange in a basket of apples.

---

I think the issue here isn't with the iterator itself, but with the underlying generics and associated type erasure. Throw autoboxing on top of this, and you have a recipe for pain. Take a look at your test code:

OdpList<Integer> list = new OdpList<Integer>();
ListIterator<Integer> iter = list.listIterator();
iter.add(42);
assertTrue(list.contains(42));

Then look at this page and here for some insight into what's really going on. Generic types are used by the compiler and then ignored by the runtime environment.

You're instantiating a list with type Integer, but at runtime, it's impossible for the JVM to suss out exactly what's in the list iterator. It's like your explicit instantiation never happened, so you're stuck with a generic object. This means the auto-magic autoboxing of 42 is never going to happen, since that behavior is tied to the Integer class. In fact, your JVM is probably treating the 42 in "list.contains(42)" as a reference to an object of type Object, which explains why the test fails.

Counter-intuitive? Yes. Sloppy? Yep. Frustrating? Tremendously. Examples like this are the reason why so many people say generics are broken in Java.