When to Use a List Over an Array in Java

When to use a List over an Array in Java?

I see the question as being the opposite-

When should you use an Array over a List?

Only you have a specific reason to do so (eg: Project Constraints, Memory Concerns (not really a good reason), etc.)

Lists are much easier to use (imo), and have much more functionality.

Note: You should also consider whether or not something like a Set, or another datastructure is a better fit than a List for what you are trying to do.

Each datastructure, and implmentation, has different pros/cons. Pick the ones that excel at the things that you need to do.

If you need get() to be O(1) for any item? Likely use an ArrayList, Need O(1) insert()? Possibly a Linked List. Need O(1) contains()? Possibly a Hashset.

TLDR: Each data structure is good at some things, and bad at others. Look at your objectives and choose the data structure that best fits the given problem.

Edit:

One thing not noted is that you're
better off declaring the variable as
its interface (i.e. List or Queue)
rather than its implementing class.
This way, you can change the
implementation at some later date
without changing anything else in the
code.

As an example:

List<String> myList = new ArrayList<String>(); 

vs

List<String> myList = new LinkedList<String>(); 

Note that myList is a List in both examples.
--R. Bemrose

When to use a linked list over an array/array list?

Linked lists are preferable over arrays when:

1. you need constant-time insertions/deletions from the list (such as in real-time computing where time predictability is absolutely critical)

2. you don't know how many items will be in the list. With arrays, you may need to re-declare and copy memory if the array grows too big

3. you don't need random access to any elements

4. you want to be able to insert items in the middle of the list (such as a priority queue)

Arrays are preferable when:

1. you need indexed/random access to elements

2. you know the number of elements in the array ahead of time so that you can allocate the correct amount of memory for the array

3. you need speed when iterating through all the elements in sequence. You can use pointer math on the array to access each element, whereas you need to lookup the node based on the pointer for each element in linked list, which may result in page faults which may result in performance hits.

4. memory is a concern. Filled arrays take up less memory than linked lists. Each element in the array is just the data. Each linked list node requires the data as well as one (or more) pointers to the other elements in the linked list.

Array Lists (like those in .Net) give you the benefits of arrays, but dynamically allocate resources for you so that you don't need to worry too much about list size and you can delete items at any index without any effort or re-shuffling elements around. Performance-wise, arraylists are slower than raw arrays.

Array or List in Java. Which is faster?

I suggest that you use a profiler to test which is faster.

My personal opinion is that you should use Lists.

I work on a large codebase and a previous group of developers used arrays everywhere. It made the code very inflexible. After changing large chunks of it to Lists we noticed no difference in speed.

Lists vs Arrays - when to use what?

If in doubt, using a List is likely to be a better choice even if you know the length.

Using an array can be better for performance, but you need to be an expert to know when this is a good idea, and when it just makes your solution more complicated.

BTW: There is no such thing as dynamic arrays in Java.

When to use LinkedList over ArrayList in Java?

Summary ArrayList with ArrayDeque are preferable in many more use-cases than LinkedList. If you're not sure — just start with ArrayList.

---

TLDR, in ArrayList accessing an element takes constant time [O(1)] and adding an element takes O(n) time [worst case]. In LinkedList inserting an element takes O(n) time and accessing also takes O(n) time but LinkedList uses more memory than ArrayList.

LinkedList and ArrayList are two different implementations of the List interface. LinkedList implements it with a doubly-linked list. ArrayList implements it with a dynamically re-sizing array.

As with standard linked list and array operations, the various methods will have different algorithmic runtimes.

For LinkedList<E>

• get(int index) is O(n) (with n/4 steps on average), but O(1) when index = 0 or index = list.size() - 1 (in this case, you can also use getFirst() and getLast()). One of the main benefits of LinkedList<E>
• add(int index, E element) is O(n) (with n/4 steps on average), but O(1) when index = 0 or index = list.size() - 1 (in this case, you can also use addFirst() and addLast()/add()). One of the main benefits of LinkedList<E>
• remove(int index) is O(n) (with n/4 steps on average), but O(1) when index = 0 or index = list.size() - 1 (in this case, you can also use removeFirst() and removeLast()). One of the main benefits of LinkedList<E>
• Iterator.remove() is O(1). One of the main benefits of LinkedList<E>
• ListIterator.add(E element) is O(1). One of the main benefits of LinkedList<E>

^{Note: Many of the operations need n/4 steps on average, constant number of steps in the best case (e.g. index = 0), and n/2 steps in worst case (middle of list)}

For ArrayList<E>

• get(int index) is O(1). Main benefit of ArrayList<E>
• add(E element) is O(1) amortized, but O(n) worst-case since the array must be resized and copied
• add(int index, E element) is O(n) (with n/2 steps on average)
• remove(int index) is O(n) (with n/2 steps on average)
• Iterator.remove() is O(n) (with n/2 steps on average)
• ListIterator.add(E element) is O(n) (with n/2 steps on average)

^{Note: Many of the operations need n/2 steps on average, constant number of steps in the best case (end of list), n steps in the worst case (start of list)}

LinkedList<E> allows for constant-time insertions or removals using iterators, but only sequential access of elements. In other words, you can walk the list forwards or backwards, but finding a position in the list takes time proportional to the size of the list. Javadoc says "operations that index into the list will traverse the list from the beginning or the end, whichever is closer", so those methods are O(n) (n/4 steps) on average, though O(1) for index = 0.

ArrayList<E>, on the other hand, allow fast random read access, so you can grab any element in constant time. But adding or removing from anywhere but the end requires shifting all the latter elements over, either to make an opening or fill the gap. Also, if you add more elements than the capacity of the underlying array, a new array (1.5 times the size) is allocated, and the old array is copied to the new one, so adding to an ArrayList is O(n) in the worst case but constant on average.

So depending on the operations you intend to do, you should choose the implementations accordingly. Iterating over either kind of List is practically equally cheap. (Iterating over an ArrayList is technically faster, but unless you're doing something really performance-sensitive, you shouldn't worry about this -- they're both constants.)

The main benefits of using a LinkedList arise when you re-use existing iterators to insert and remove elements. These operations can then be done in O(1) by changing the list locally only. In an array list, the remainder of the array needs to be moved (i.e. copied). On the other side, seeking in a LinkedList means following the links in O(n) (n/2 steps) for worst case, whereas in an ArrayList the desired position can be computed mathematically and accessed in O(1).

Another benefit of using a LinkedList arises when you add or remove from the head of the list, since those operations are O(1), while they are O(n) for ArrayList. Note that ArrayDeque may be a good alternative to LinkedList for adding and removing from the head, but it is not a List.

Also, if you have large lists, keep in mind that memory usage is also different. Each element of a LinkedList has more overhead since pointers to the next and previous elements are also stored. ArrayLists don't have this overhead. However, ArrayLists take up as much memory as is allocated for the capacity, regardless of whether elements have actually been added.

The default initial capacity of an ArrayList is pretty small (10 from Java 1.4 - 1.8). But since the underlying implementation is an array, the array must be resized if you add a lot of elements. To avoid the high cost of resizing when you know you're going to add a lot of elements, construct the ArrayList with a higher initial capacity.

If the data structures perspective is used to understand the two structures, a LinkedList is basically a sequential data structure which contains a head Node. The Node is a wrapper for two components : a value of type T [accepted through generics] and another reference to the Node linked to it. So, we can assert it is a recursive data structure (a Node contains another Node which has another Node and so on...). Addition of elements takes linear time in LinkedList as stated above.

An ArrayList is a growable array. It is just like a regular array. Under the hood, when an element is added, and the ArrayList is already full to capacity, it creates another array with a size which is greater than previous size. The elements are then copied from previous array to new one and the elements that are to be added are also placed at the specified indices.

How do I know whether to use an array or an arraylist?

• Use array when you know the exact size of the collection and you don't expect to add/remove elements.

• Use List (ArrayList) when you don't know the exact size of the collection and you expect to alter it at some point.

• If you're using Java8, there is the Stream API, which helps to significantly reduce the boilerplate code when working with collections. This is another plus for ArrayList (and all Collections and Maps).

More info:

• Arrays vs ArrayList in performance

Java - List or Array?

I think a good rule of thumb would be to use Lists unless you NEED an Array (for memory/performance reasons). Otherwise Lists are typically easier to maintain and thus less likely to cause future bugs.

Lists provide more flexibility/functionality in terms of auto-expansion, so unless you are either pressed for memory (and can't afford the overhead that Lists create) or do not mind maintaining the Array size as it expands/shrinks, I would recommend Lists.

Try not to micromanage the code too much, and instead focus on more discernible and readable components.

Why is it preferred to use Lists instead of Arrays in Java?

You should generally prefer to choose the right data structure for the job. You need to understand your task at hand as well as all the different options you have and how they compare in terms of iteration, and searching, and adding, removing, and inserting data. In general, you need to understand how the data structure accesses and manipulates memory and choose the best data structure based on how you anticipate your application will be used.

Obviously, it isn't always clear-cut. But you can understand the ideals for different data structures.

For example, purely static, fixed length data in which you'll only iterate, without a need for search, is ideal for an array. It's common to use such arrays in cipher algorithms. If the data is static but instead of iterating, you need to search, you might want some type of tree structure. If you want fast insertion, hashing is probably the ideal. If the data changes often, you want a structure that is efficient at changing its size, like a list.

Of course, there's many variations and combinations of data structures designed to solve all kinds of specific problems. The reason there are so many is because of the importance they play in writing efficient programs. Anyway, my point is, learn about data structures. Understand the ideal situations for each and then you'll be able to decide or design suitable data structures for any task.

---

Related Topics