Java: Interleave two integer based arraylists -> good approach?

Question

Homework: Looking for better strategy, or approach rather than complete code.

I'v got two arrayLists of integers under two conditions:

the first list is bigger than the second
the second list is larger than the first

My goal was to interleave elements of list2, into list1 under both conditions. I've created a method that does this, but I feel like I could be doing something better.

Here is the expected result for condition 1. Note that after the elements of list2 are exhausted, we leave the elements of list1 in place:

list1: [10, 20, 30, 40, 50, 60, 70]
list2: [4, 5, 6, 7]
Combined: [10, 4, 20, 5, 30, 6, 40, 7, 50, 60, 70]

Here is the expected result for condition 2. Since list2 has more elements, we append these elements to list1 after list1 is exhausted:

list1: [10, 20, 30, 40]
list2: [4, 5, 6, 7, 8, 9, 10, 11]
Combined: [10, 4, 20, 5, 30, 6, 40, 7, 8, 9, 10, 11]

My code uses an if-else statement to process both conditions. I then use an iterator to go through elements of list2 and insert them in list1.

public static void main(String[] Args)
{
    ArrayList<Integer> numbers = new ArrayList<Integer>();
    numbers.add(10);
    numbers.add(20);
    numbers.add(30);
    numbers.add(40);
    //numbers.add(50);
    //numbers.add(60);
    //numbers.add(70);

    ArrayList<Integer> numbers2 = new ArrayList<Integer>();

    numbers2.add(4);
    numbers2.add(5);
    numbers2.add(6);
    numbers2.add(7);
    numbers2.add(8);
    numbers2.add(9);
    numbers2.add(10);
    numbers2.add(11);

    System.out.println("list1: " + numbers);
    System.out.println("list2: " + numbers2);

    interleave(numbers, numbers2);

    System.out.println();
    System.out.println("Combined: " + numbers);
}

public static void interleave(ArrayList<Integer> list1, ArrayList<Integer> list2)
{
    //obtain an iterator for the collection
    Iterator<Integer> itr2 = list2.iterator();

    //loop counter
    int count = 1;

    //handle based on initial size of lists
    if(list1.size() >= list2.size())
    {
       //loop through the first array and add elements from list 2 after each element
       while(itr2.hasNext())
       {
           //insert elements from list2
           list1.add(count, itr2.next());

           //make sure elements are getting added at 1, 3, 5, 7, 9, etc
           count = count + 2;
       }
    }
    else if(list1.size() < list2.size())
    {
       //loop through the first array and add elements from list 2 after each element
       while(itr2.hasNext())
       {
           if(count <= list1.size())
           {
               //insert elements from list2
               list1.add(count, itr2.next());

               //make sure elements are getting added at 1, 3, 5, 7, 9, etc
               count = count + 2;
           }
           else
           {
               //fill in the remainder of the elements from list2 to list1
               list1.add(itr2.next());
           }
       }
    }
}

Patrick M · Accepted Answer · 2014-07-21 23:50:31Z

6

Do you like this solution?

public static void main(final String[] args) {
    ArrayList<Integer> numbers = new ArrayList<Integer>();
    numbers.add(10); numbers.add(20); numbers.add(30); numbers.add(40);
    //numbers.add(50); numbers.add(60); numbers.add(70);

    ArrayList<Integer> numbers2 = new ArrayList<Integer>();
    numbers2.add(4); numbers2.add(5); numbers2.add(6); numbers2.add(7);
    numbers2.add(8); numbers2.add(9); numbers2.add(10); numbers2.add(11);

    System.out.println("list1: " + numbers);
    System.out.println("list2: " + numbers2);
    List<Integer> interleaved = interleave(numbers, numbers2);

    System.out.println("\nCombined: " + interleaved);
}

public static List<Integer> interleave(
    final List<Integer> list1,
    final List<Integer> list2
) {
    List<Integer> result
        = new ArrayList<Integer>(list1.size() + list2.size());

    Iterator<Integer> it1 = list1.iterator();
    Iterator<Integer> it2 = list2.iterator();
    while (it1.hasNext() || it2.hasNext()) {
        if (it1.hasNext()) {
            result.add(it1.next());
        }
        if (it2.hasNext()) {
            result.add(it2.next());
        }
    }
    return result;
}

edited Jul 21, 2014 at 23:50

Patrick M

11.1k9 gold badges75 silver badges105 bronze badges

answered Jan 27, 2013 at 20:18

MrSmith42

10.2k6 gold badges41 silver badges52 bronze badges

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

3 Comments

John Dvorak Over a year ago

@assylias I understand that as "code sample optional (but must be readadble)" rather than "code sample strictly forbidden".

MrSmith42 Over a year ago

You will always need to iterate through both lists. No way to avoid this. You can only try to make the code as easy to understand as possible.

Pat K Over a year ago

This is one of those "I can't believe its really this simple."

assylias · Accepted Answer · 2013-01-27 20:13:22Z

2

A few comments:

I would probably have returned a new List instead of arbitrarily modifying one of them
The new algorithm is then simpler:
- create a new empty list
- loop on a counter from 0 to the min of the two lists' sizes and interleave
- when you are done, check if one of the lists has more items and add them (for example with a combination of addAll and subList)
- return the list
If you don't need to mutate the two original lists, you can declare them in a shorter way with: List<Integer> numbers = Arrays.asList(10, 20, 30, 40); - note that it creates a fixed-size list so you can't add or remove
With your current code, instead of duplicating things you could have something like: List listSmall, listBig; if (list1.size() < list2.size()) { listSmall = list1; listBig = list2; } else { /* the opposite */} - then you know that listSmall is the small one and you only need one loop.

answered Jan 27, 2013 at 20:13

assylias

330k84 gold badges680 silver badges806 bronze badges

1 Comment

Pat K Over a year ago

The problem basically says to modify the original, but yeah I'll go ahead and return a list. Excellent points.

Mark Peters · Accepted Answer · 2013-01-27 20:39:34Z

Here's another way of thinking about this problem, and a way that would just as easily extend to 3 lists.

First, recognize that the hard part to solve here is iteration, not creating the new list. Creating a new list from an iterable is trivial.

So imagine we have a method like this:

public <T> Iterable<T> interleave(Iterable<? extends T>... lists) {
    return new Iterable<T>() {
       @Override
       public Iterator<T> iterator() {
           return new InterleavingIterator<T>(lists);
       }
    };
}

What we need to make is an Iterator<T> that cycles through each iterator one at a time. That's the perfect job for a queue (fifo)! Your iterator could look something like this:

class InterleavingIterator<T> implements Iterator<T> {

    private final Queue<Iterator<? extends T>> iterators = new LinkedList<>();

    public InterleavingIterator(Iterable<? extends T>> iteratables) {
        for ( Iterable<T> iterable : iterables ) {
           Iterator<T> iterator = iterable.iterator();
           if ( iterator.hasNext() ) {
              this.iterators.add(iterator);
           }
        }
    }

    public boolean hasNext() {
        return !iterators.isEmpty();
    }

    public T next() {
        Iterator<T> nextIterator = iterators.poll();
        T result = nextIterator.next();
        if ( nextIterator.hasNext() ) {
           iterators.add(nextIterator);
        }
        return result;
    }
}

In short, every time the next element is requested, the iterator at the top of the queue is popped, the result of next() is returned, and if the iterator still has elements (hasNext()) it is put to the back of the queue.

This works exactly the same for any number of lists, and doesn't need any icky condition checking.

To create a new list with it, you could just do:

List<Integer> combined = new ArrayList<Integer>(interleave(list1, list2));

Aguid · Accepted Answer · 2018-08-24 23:16:53Z

0

I propose the following code:

private static List<Integer> joinTwoLists(List<Integer> a, List<Integer> b) {
    final boolean aIsBigger = a.size() > b.size();
    final List<Integer> joined = new ArrayList<>(aIsBigger ? a : b);
    final AtomicInteger index = new AtomicInteger(1);
    for (Integer value : aIsBigger ? b : a) {
        joined.add(index.getAndAdd(2), value);
    }
    return joined;
}

edited Aug 24, 2018 at 23:16

answered Aug 24, 2018 at 22:53

Aguid

1,0634 gold badges11 silver badges25 bronze badges

Comments

CuongHoang2k1 · Accepted Answer · 2020-02-21 19:50:57Z

0

This is my approach.

public static void interleave(ArrayList<Integer> a1, ArrayList<Integer> a2) {
    int start = 0;
    int i;
    int size = a1.size();
    for (i = 1; i < a1.size(); i += 2) {
        if (start < a2.size()) {
            a1.add(i, a2.get(start++));
        }
    }
    while (a1.size() < (size + a2.size())) {
        a1.add(i++, a2.get(start++));
    }

}

edited Feb 21, 2020 at 19:50

answered Feb 21, 2020 at 19:45

CuongHoang2k1

11 bronze badge

Collectives™ on Stack Overflow

Java: Interleave two integer based arraylists -> good approach?

5 Answers 5

3 Comments

1 Comment

Comments

Comments

Comments

Your Answer

Linked

Hot Network Questions

Collectives™ on Stack Overflow

5 Answers 5

3 Comments

1 Comment

Comments

Comments

Comments

Your Answer

Sign up or log in

Post as a guest

Linked

Related