CODEWITHSUNDEEP
javaarraylistcollectionslinked-list
MikaelF
MikaelF

Reputation: 3644

Convert a LinkedList to ArrayList for faster concurrent iterating

I am well-aware of the costs of iterating LinkedList with an external index (forloop). Looking into the source code for the ListIterator returned by LinkedList#listIterator, I notice that it significantly speeds up the process by keeping track of the node it is currently using.

However, I recently came across this question, which was basically about iterating over two or more lists simultaneously, but needed to do so while keeping track of an index to transfer values to an array. In my mind, this made the use of iterators slightly redundant and more prone to human error, as individual declarations were necessary for each iterator, on top of looping and calling every single next method. This is why I tried avoiding the iterator-loop combo. Here is a possible solution to the problem:

List<Integer> listOne = new ArrayList<>();
List<Integer> listTwo = new ArrayList<>();
int[] combined = new int[(listOne.size() < listTwo.size() ? listOne.size() : listTwo.size())];
for (int i = 0; i < combined.length; i++) {
    combined[i] = listOne.get(i) + listTwo.get(i);
}

This is fine for ArrayList, but it would be a rather slow operation with LinkedList.

One possible solution would be to use the conversion constructor of ArrayList to get all the references from a LinkedList:

//convert linkedlists to arraylists
ArrayList<Integer> arrayListOne = new ArrayList<>(listOne);
ArrayList<Integer> arrayListTwo = new ArrayList<>(listTwo);
//iterate with an efficient get() operation
for (int i = 0; i < combined.length; i++) {
    combined[i] = listOne.get(i) + listTwo.get(i);
}

Since this would only call the iterator of each LinkedListonce, and then use the more efficient ArrayList#get method, is this a viable solution? Would the overhead from the conversion negate the efficiency gain? Are there any other downsides to this method?

Upvotes: 1

Views: 638

Answers (3)

Mordechai
Mordechai

Reputation: 16284

I know this is not an answer to your question specifically but i feel you can benefit from this piece of information.

Since Java 1.6, there's a new type of collection, called ArrayDeque that has the fast random access like an array, but also has the fast add/remove at the ends.

LinkedList still wins at add/remove in the middle if the list.

Upvotes: 1

Evgeniy Dorofeev
Evgeniy Dorofeev

Reputation: 136062

I think you could use iterators on LInkedLists and index for array:

    Iterator<Integer> i1 = listOne.iterator();
    Iterator<Integer> i2 = listTwo.iterator();
    for (int i = 0; i < combined.length; i++) {
        combined[i] = i1.next() + i2.next();
    }

Upvotes: 0

Andreas
Andreas

Reputation: 159135

[...] iterating over two or more lists simultaneously, but needed to do so while keeping track of an index to transfer values to an array, therefore preventing the use of iterators.

Just because you also need an index, doesn't mean you can't use an Iterator, so the "preventing the use of iterators" is an entirely incorrect assertion.

You're just doing a simple 3-way parallel iteration (2 iterators and 1 index):

List<Integer> listOne = new LinkedList<>();
List<Integer> listTwo = new LinkedList<>();
int[] combined = new int[Math.min(listOne.size(), listTwo.size())];
Iterator<Integer> iterOne = listOne.iterator();
Iterator<Integer> iterTwo = listTwo.iterator();
for (int i = 0; i < combined.length; i++) {
    combined[i] = iterOne.next() + iterTwo.next();
}

UPDATE (to answer specific questions)

Since this would only call the iterator of each LinkedList once, and then use the more efficient ArrayList#get method, is this a viable solution?

Yes, it's definitely a more viable solution. As the lists gets bigger, the exponential response time of get(index) for a LinkedList makes using get() a really bad solution.

Would the overhead from the conversion negate the efficiency gain?

No. Even at small list sizes, the sequential search performance of get(index) on a LinkedList will far outweigh any performance loss from the copying of the list.

Are there any other downsides to this method?

Copying the list first increases the memory requirements, and requires an extra (unnecessary) iteration of the data.

UPDATE (to respond to changes in the question)

[...] In my mind, this made the use of iterators slightly redundant and more prone to human error

Using multiple iterators in parallel is not redundant.

Also, all programming is prone to human errors. You should generally use the algorithm that is most appropriate / correct, rather than consider (very slight) increases in potential programming error caused by increased complexity. Sure, if one algorithm is insanely complex, and another is easy, you likely want to use the easy one, if the improvement of the complex algorithm is not worth it. But there is a reason no one uses bubble sort, even though it is super easy: Performance is really bad. In your case, the complexity of parallel iteration is minuscule.

Comparing use of multiple parallel iterators, vs. copying to ArrayList, which is more redundant? Copying to ArrayList is, because you end up iterating the data twice and you require more memory to do so.

Parallel iteration is the best solution to your problem. It uses the intended iteration mechanism of the provided List, without knowing the characteristics of the list. Iterating a List by index is inherently wrong. Lists (and other Collections) should always be iterated by the supplied Iterator (or ListIterator or Spliterator).

Also note that parallel iteration is sometimes the only option, e.g. in merge-sort, where you're not iterating the two inputs at the same speed.

Upvotes: 4

Related Questions