markvgti markvgti - 3 months ago 13
Java Question

Which implementation to use when creating a List from Iterable

I find myself frequently doing the following:

Iterator<A> itr = iterableOfA.getIterator();
List<B> list = new ArrayList<>(); // how about LinkedList?
while (itr.hasNext()) {
B obj = iter.next().getB();
list.add(obj);
}
someMethod(list); // this method takes an Iterable


I have no idea just how many elements are likely to be in
iterableOfA
— could be 5, could be 5000. In this case, would
LinkedList
be a better implementation to use here (since
list.add(obj)
would then be O(1))? As it stands, if
iterableOfA
has 5000 elements, this will lead to many resizings of backing array of
list
.

Other option is to do:

Iterator<A> itr = iterableOfA.getIterator();
int size = Iterables.size(iterableOfA); // from Guava
List<B> list = new ArrayList<>(size);
// and the rest...


This means double iteration of
iterableOfA
. Which option would be best when the size of the iterable is unknowns and can vary wildly:


  1. Just use
    ArrayList
    .

  2. Just use
    LinkedList
    .

  3. Count the elements in
    iterableOfA
    and allocate an
    ArrayList
    .



Edit 1



To clarify some details:


  1. I am optimizing primarily for performance and secondarily for memory usage.

  2. list
    is a short-lived allocation as at the end of the request no code should be holding a reference to it.



Edit 2



For my specific case, I realized that
someMethod(list)
doesn't handle an iterable with greater than 200 elements, so I decided to go with
new ArrayList<>(200)
which works well enough for me.

However, in the general case I would have preferred to implement the solution outlined in the accepted answer (wrap in a custom iterable, obviating the need for allocating a list).

All the other answers gave valuable insight into how suitable
ArrayList
is compared to
LinkedList
, so on behalf of the general SO community I thank you all!

Answer

I would completely skip copying the elements to a new collection.

We have utility code for easily wrapping Iterators into Iterables and Filter for converting between types, but the gist of it is:

final Iterable<A> iofA ... ;
Iterable<B> iofB = new Iterable<B>() {
  public Iterator<B> iterator() {
    return new Iterator<B>() {
      private final Iterator<A> _iter = iofA.iterator();
      public boolean hasNext() { return _iter.hasNext(); }
      public B next() { return _iter.next().getB(); }
    };
  }
};

No additional storage, etc. necessary.