Android adapter: using Linkedlist vs Arraylist

Question

I'm using a RecycleView with a Gridlayoutmanager. My app loads a lot of items when the user scrolls down.

LinkedList has a good performance when adding new elements, while my ArrayList would need to get constantly resized.

But I'm not sure about what RecycleView does in the background which would work better with an ArrayList and/or a LinkedList.

My adapter would be:

public class PhotosAdapter extends RecyclerView.Adapter<PhotosAdapter.PhotosViewHolder> {

    private Context context;

    private List<Photo> items;

    public PhotosAdapter(Context context, List<Photo> items) {
        this.context = context;
        this.items = items;
    }

    //other code here

    public void addAll(List<Photo> newItems) {
        int beforeSize = items.size()-1;
        items.addAll(newItems);
        notifyItemRangeInserted(beforeSize, newItems.size());
    }

}

So when I create a new empty adapter I can either do this:

new PhotosAdapter(getContext(), new ArrayList<Photo>());

or this:

new PhotosAdapter(getContext(), new LinkedList<Photo>());

And when adding new elements simply:

adapter.addAll(myPhotos);

So would a LinkedList work better in this case? What about RecycleView's optimalized scrolling? Does that work better with an ArrayList or a LinkedList?

Luka Jacobowitz · Answer 1 · 2016-02-14T12:40:15.107

5

Now the first question should be are you optimizing prematurely? Is this a critical part of your app and are you having performance problems?

Anyway ArrayLists will give you better performance in most situations. I'd recommend using it as default and only using linked lists if you want to insert data into the middle of the list.

Yes, ArrayLists need to resize the array when they get too big, but in most cases this won't offset the advantages you get.

Remember that get(int index) is O(n) when using LinkedLists vs O(1) when using ArrayLists. If you're really concerned about adding lots of elements often, you can give the ArrayList a large initial capacity so it won't have to resize too often.

Check out this talk from Bjarne Stroustrup if you're interested. https://www.youtube.com/watch?v=YQs6IC-vgmo

edited Feb 14 '16 at 12:40

answered Feb 14 '16 at 12:33

Luka Jacobowitz

22,795
5
39
57

Wouldn't adding new elements constantly affecting performance? If you use an ArrayList it needs to resize it's underlying array when adding new elements. With LinkedList thats not a problem. – breakline Feb 14 '16 at 12:34
That's true, but how often is that really going to happen? How many new items are going to be added realistically? Most likely if it's not more than a thousand it's not going to make a significant difference. – Luka Jacobowitz Feb 14 '16 at 12:43
Probably. I'm not having performance issues, was just wondering since I inject the List type from outside it could be any kind of implementation. – breakline Feb 14 '16 at 13:18
It's definitely a valid question, that I've asked myself in the past. Here's another question on that topic. http://stackoverflow.com/questions/322715/when-to-use-linkedlist-over-arraylist – Luka Jacobowitz Feb 14 '16 at 13:19

score 0 · Answer 2 · answered Feb 14 '16 at 12:48

It doesn't matter. Plus, you can always just try both of them and measure the performance.

More likely, the issue lies with something else:

Are you retrieving the data on a background thread?
Are new items being added in between existing items? Or only at the end? If it's only at the end you could try pre-fetching the items when the user is close to the bottom. (Again, by firing off a background thread and listening for a callback)
Are your child views complicated?
Since the code mentions using List, I'm guessing it's a recyclerView with images. The problem could be bitmaps being constantly allocated (and deallocated) memory.

In any case, I recommend profiling. A difference as minuscule as using ArrayList instead of LinkedList doesn't matter in all but the most extreme cases. See what your garbage collector is doing. Look at which method takes the longest to run, try to find what's slowing down your app the most.

Android adapter: using Linkedlist vs Arraylist

2 Answers2