0

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?

Improve this question
6
  • 1
    You're certain that OdpList.listIterator() returns an instance of OdpIterator, right? Commented Oct 15, 2009 at 16:32
  • Can you post the contains method also? I'm not seeing a problem with what you have there. Commented Oct 15, 2009 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). Commented Oct 15, 2009 at 17:46
  • yeah, the only reason I'm rolling my own is for my own learning. Commented Oct 15, 2009 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. Commented Jan 25, 2010 at 0:14

7 Answers 7

Reset to default
6

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!

Improve this answer
Sign up to request clarification or add additional context in comments.

Comments

2

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"
Improve this answer

2 Comments

@mlk, typo up top: "enchanted" should be "enhanced"?
you deserve more than the one upvote this question had (2nd was mine)
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.

Improve this answer

3 Comments

Please read javaranch.com/campfire/StoryCups.jsp and javaranch.com/campfire/StoryPassBy.jsp. Java does not pass Objects. It passes reference types by value.
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.
Java ONLY does pass by value!
0

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.

Improve this answer

Comments

0

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!

Improve this answer

Comments

0

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.

Improve this answer

Comments

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.

Improve this answer

7 Comments

Generics are not broken, autoboxing is. That's why I have it as a warning in my Eclipse IDE
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()).
(Holding off on downvote for now in case there is a reasonable explanation.)
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: Autoboxing actually uses .valueOf() instead of always constructing a new object, but yeah. The real problem is the contains() method, not Java.
|

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.