Java: Pass by reference / ListIterator.add()

Question

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;
    private 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?

You're certain that `OdpList.listIterator()` returns an instance of `OdpIterator`, right? — Michael Myers, Oct 15 '09 at 16:32
Can you post the `contains` method also? I'm not seeing a problem with what you have there. — Michael Myers, Oct 15 '09 at 17:29
I'm assuming this is for learning purposes, but otherwise a LinkedList would be better. And by the way, I found the problem; it was a simple bug (which is a good argument for using a class that *already* works instead of rolling your own). — Michael Myers, Oct 15 '09 at 17:46
yeah, the only reason I'm rolling my own is for my own learning. — Nick Heiner, Oct 15 '09 at 18:05
"Java passes all Objects by reference. It passes primitives by value." Java does not pass objects and in all cases Java uses pass by value. — , Jan 25 '10 at 00:14
Well, it doesn't pass by value. It passes a copy of reference to the object. — StKiller, Dec 02 '11 at 08:50

score 6 · Accepted Answer · answered Oct 15 '09 at 17:45

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!

score 2 · Answer 2 · edited May 23 '17 at 10:27

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:

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"

you deserve more than the one upvote this question had (2nd was mine) — thatidiotguy, Feb 06 '14 at 18:48

score 0 · Answer 3 · answered Oct 15 '09 at 16:32

0

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.

answered Oct 15 '09 at 16:32

Matt Moriarity

697
5
13

Please read http://www.javaranch.com/campfire/StoryCups.jsp and http://www.javaranch.com/campfire/StoryPassBy.jsp. Java does not pass Objects. It passes reference types by value. – Michael Lloyd Lee mlk Oct 15 '09 at 16:40
I'm not sure the distinction is important in this case. You are correct, the reference itself is a copy so you can't assign back to the same memory address. But in this case he just wants to be able to manipulate the list and have it be working on the same list that was passed in. – Matt Moriarity Oct 15 '09 at 16:43
Java _ONLY_ does pass by value! – Johannes Weiss Oct 15 '09 at 17:04

score 0 · Answer 4 · answered Oct 15 '09 at 16:37

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.

score 0 · Answer 5 · answered Oct 15 '09 at 16:37

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!

rtperson · Answer 6 · 2009-10-15T17:33:37.277

0

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.

edited Oct 15 '09 at 17:33

answered Oct 15 '09 at 17:23

rtperson

11,632
4
29
36

Generics are not broken, autoboxing is. That's why I have it as a warning in my Eclipse IDE – Alexander Pogrebnyak Oct 15 '09 at 17:28
This answer is wrong on three levels. Firstly: Any time a primitive is converted into an Object, autoboxing is invoked. Secondly: Since 42 is between 0 and 128, the boxed value is guaranteed to be cached. Thirdly: The caching doesn't matter if `.equals()` is being called (as it should be in any reasonable implementation of `.contains()`). – Michael Myers Oct 15 '09 at 17:32
(Holding off on downvote for now in case there is a reasonable explanation.) – Michael Myers Oct 15 '09 at 17:33
autoboxing will happen at compile time. The code will be equialent to `iter.add( new Integer(42) )` and `list.contains( new Integer(42) )`. The problem I think is that `OdpList.contains` is totally broken. By contract it should work with anything, including `Object`. – Alexander Pogrebnyak Oct 15 '09 at 17:37
@Alexander: Autoboxing actually uses `.valueOf()` instead of always constructing a new object, but yeah. The real problem is the `contains()` method, not Java. – Michael Myers Oct 15 '09 at 17:48
@mmyers - I'm going over the best set of rules for autoboxing I can find (http://jcp.org/aboutJava/communityprocess/jsr/tiger/autoboxing.html) and I don't see support for your first and second points (both of which, I'll admit, are new to me). Can you find a reference in support of your points, or are they simply typical JVM behavior? I'm not trying to be dense -- I'm genuinely interested. – rtperson Oct 15 '09 at 17:54
For my first point, how else could a primitive be passed to a method expecting an object? There's only one way to turn a primitive into an object, and that's boxing. (I could go deep into the JLS to find out just what kind of conversion is being performed to get a variable into a method parameter, but I'm too lazy to do it just for a comment.) For caching, see http://java.sun.com/docs/books/jls/third_edition/html/conversions.html#5.1.7 (the range is actually -128 to 127 for ints). – Michael Myers Oct 15 '09 at 18:12

score 0 · Answer 7 · answered Oct 15 '09 at 17:24

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.

Java: Pass by reference / ListIterator.add()

7 Answers7