Iterate through Linked List in Java

Question

Say, I have two references to an Object in a LinkedList List1:

LinkedList<Object> List1 = new LinkedList<Object>();
Object first;
Object last;

I don't want to use the list index of these objects to refer to them, because the length of my list changes. I think this would not work. Now I want to iterate through the sublist defined by first and last, where first defines the beginning of the sublist in List1 and last defines the end of the sublist in List1.

My problem now is that AFAIK I can't do something like

while (current != last){
// do something
current = someiterator.next();
}

because I'm comparing two objects that in general will point to different locations. Furthermore, I also can't compare the references by their value, because the list may have one value appearing several times. So how can I iterate through this sublist of List1?

Answer 1

You could use something like

list1.sublist(list1.indexOf(first), list1.indexOf(last))

---

Ok, I think I understand your question better now. The above method will use the .equals method and thus not compare references. Here is probably a better solution for you:

import java.util.*;
public class Test {
 public static void main(String[] args) {
 String first = "beta";
 String last = "delta";
 List<String> list1 = new LinkedList<String>();
 list1.add("alpha");
 list1.add(first);
 list1.add("gamma");
 list1.add(last);
 list1.add("epsilon");
 boolean firstFound = false;
 for (String s : list1) {
 if (firstFound || (firstFound = s == first))
 System.out.println(s);
 if (s == last)
 break;
 }
 }
}

• ptikobj: okay, but since first and last are really objects (no primitive types), list1.indexOf(first) should return the "first" object I assigned it to (in some other method). Will it definitely return the "right" "first" object?
• ptikobj: thing is, indexOf(someobject) returns the first occurence of some object in List1. In my case however, there may be several objects with the same value. Since I'm new to Java, my question is rather: does Java treat those objects with the same value as different objects?
• aioobe: ah, updated my answer. s == first will compare objects based on reference.
• ptikobj: Thanks for your detailed answer, but I think my main problem was answered by Michael Borgwandt. I will make use of the sublist method, however.
• Sergei Tachenov: And JavaDoc explicitly says that indexOf() "returns the lowest index i such that (o==null ? get(i)==null : o.equals(get(i)))" so it compares objects by value, provided that equals() is implemented properly. So you have both options here.

Answer 2

No, your comparison while (current != last) will work fine. In Java, objects live on the heap and you only work with references. Comparing two references using == returns true iff they refer to the same object, which seems to be exactly what you want.

• ptikobj: okay, so if I do something like last = List1.get(2) and then later compare last against some iterator, like "while (current != last)" then the comparison should compare the two objects i really want to compare?
• ptikobj: I think there was something I didn't realize: If you do something like Object a = b; then a will hold the reference to object b, right? and since a holds the reference to b, i can do something like while(a != current). Initially, I thought that a=b would assign the object or the value of b to a. However, the value is only assigned to a if b is a primitive. And if b is an object, then a will only hold b's reference. Thanks for all your answers, I think I got it now.
• Michael Borgwardt: @ptikobj: The object doesn't really have a name. Neither a nor b "is" the object. Instead, both hold references to the object, and therefore have the same value when compared with ==
• ptikobj: another question: usually, a LinkedList doesn't contain objects with the same reference, right? (except I explicitly add items with the same reference to the list). If it doesn't contain objects with the same reference, then I can safely use indexOf, as proposed by aioobe.
• Michael Borgwardt: @ptikobj: only if the objects don't override the equals() method of java.lang.Object, because that's what indexOf() uses.

Answer 3

If you cannot rely neither on == nor .equals(), I don't see how you could possibly define a sublist...

• ptikobj: I mean, what I actually want is something like a pointer (as in C++) to first and a pointer to last. These pointer should remain the same and still point to the element I assigned them to in the first place.

Answer 4

One way is not to add the objects directly, but to create a wrapper, so you will have

 List<WrapperObject<Object>> aList = new LinkedList<WrapperObject<Object>>();

Now you can verify the equality of the entries by checking the wrappers instead of the wrapped objects.

Answer 5

You should use Object.equals() to compare your objects. If your Objects are real Objects and not primitive or Strings (they equal if their value equals) you should be able to do so:

 boolean start = false;
 for(Object o : list){
 if(o.equals(first){
 start = true;
 }else if(o.equals(last)){
 break;
 }
 if(start){
 // do something
 }
 }

Or rather use the answer of aioobe