A more efficient way to code this program

This Program WAS homework. We have already finished it and are good to go. I was wondering if there is a more streamlined way of writing this program? The program is called Interleave and what it does is take two ArrayLists and combine them so that every other element in the first one is from the second ArrayList. Sounds simple, and it was, we used the Iterator to go through and add the necessary elements. But the code is BLOCKY. It seems to me that there has to be a better way to write this, right? Thanks in advance.

import java.util.*;

public class Interleave
{

public static void main(String[] args)
{

    ArrayList<Integer> a1 = new ArrayList<Integer>();
    Collections.addAll(a1, 10, 20, 30);

    ArrayList<Integer> a2 = new ArrayList<Integer>();
    Collections.addAll(a2, 4, 5, 6, 7, 8, 9);

    System.out.println(a1);
    System.out.println(a2);

    System.out.println(interleave(a1, a2));

    ArrayList<String> list = new ArrayList<String>();
    String[] words =
    { "how", "are", "you?" };

    for (String s : words)
    {
        list.add(s);
    }

}

public static ArrayList<Integer> interleave(ArrayList<Integer> a1,
        ArrayList&l开发者_如何学JAVAt;Integer> a2)
{
    Iterator<Integer> it = a2.iterator();
    int i = 1;
    while (it.hasNext())
    {
        int val = it.next();
        if (a1.size() >= i)
        {
            a1.add(i, val);
        } else
        {
            a1.add(val);
        }
        i += 2;
    }
    return a1;

}

}

public static ArrayList<Integer> interleave(ArrayList<Integer> a1, ArrayList<Integer> a2)
{
    Iterator<Integer> it1 = a1.iterator();
    Iterator<Integer> it2 = a2.iterator();
    ArrayList<Integer> output = new ArrayList<Integer>();

    while (it1.hasNext() || it2.hasNext())
    {
        if (it1.hasNext()) { output.add( it1.next() ); }
        if (it2.hasNext()) { output.add( it2.next() ); }
    }

    return output;    
}

Efficiency is more important than how the code looks. Every time you add an element at index i, every element after that index needs to be moved up by one index by the ArrayList, since it uses an array as its underlying data structure. This code would be a lot more efficient if it used a LinkedList which avoids this problem, or if you created a third array of size (first array + second array) and just added the elements to that one. Then again, you also have to consider space, so making another array increases space requirements.

Even if you stick with your current approach, you should increase the capacity of the array BEFORE adding all the elements. That way, the array's capacity will already be large enough to add all of the elements from the other array, and it won't (potentially) need to be increased multiple times.

Hope that helps.

edit:

You could also reconfigure your array in advance such that every second spot was already empty, which would save you from the array shifting problem that I described earlier.

Right now, your interleave function assumes a specific list implementation (ArrayList) and a specific type that it must contain (Integer). You can generalize this function by using generics:

public static <T> List<T> interleave(List<T> first, List<T> second)
{
    Iterator<T> it = second.iterator();
    int i = 1;
    while (it.hasNext()) {
        T val = it.next();
        if (first.size() >= i)
            first.add(i, val);
        else
            first.add(val);
        i += 2;
    }

    return first;
}

I don't think you can reduce the amount of code much. It probably can't be made to be too much faster either. I would however suggest some other improvements:

1. It's not a good practice to mutate an object that you pass in if you're returning another one.
2. You could just use List instead of ArrayList so any type of List can be passed in.
3. You could use generics to not make it specific to a list of Integer.

These combined would yield something like this:

public static <T> List<T> interleave(List<T> a1, List<T> a2) {
    List<T> list = new ArrayList<T>(a1.size() + a2.size());
    Iterator<T> it1 = a1.iterator();
    Iterator<T> it2 = a2.iterator();

    while (it1.hasNext() || it2.hasNext()) {
        if (it1.hasNext()) {
            list.add(it1.next());
        }
        if (it2.hasNext()) {
            list.add(it2.next());
        }
    }

    return list;
}