ArrayList vs LinkedList
LinkedList and ArrayList are two different implementations of the List interface.
LinkedList internally has implementation with a doubly-linked list and ArrayList implements it with a dynamically re-sizing array.
So, let’s talk about the implementation of each list.
ArrayList is used to do random read access fast, so we can grab any element in constant time. But adding or removing from anywhere but the end requires shifting all the latter elements to previous chunk of memory to make an opening or fill the gap. Also, if we add more elements than the capacity of the underlying array, a new array (1.5 times the size) is allocated (initially the size is 10), 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.
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 we 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.
LinkedList allows us to do constant-time insertions or removals using iterators, but only sequential access of elements. In other words, we can walk the list forwards or backwards, but finding a position in the list takes time proportional to the size of the list. Java doc 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/4) on average, though O(1) for index=0.
Real time comparison of Array, ArrayList, Deque, Linked List. (times in nanosecond) -
Hope, you must have started getting idea of where should we use which data structure( arraylist and linkedlist). So let’s have a look on benefit of using each data structure.
Benefits of LinkedList over ArrayList:-
The main benefits of using a linkedList arise when we 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 arrayList, 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/2) 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 is when we 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.
Benefits of ArrayList over LinkedList:-
If we have large lists, let’s 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. ArrayList don't have this overhead. However, arrayList takes up as much memory as is allocated for the capacity, regardless of whether elements have actually been added.
So, Exactly which one we should use at what condition?
So depending on the operations we intend to do, we should choose the implementations accordingly. Iterating over either kind of List is practically equally cheap. (Iterating over an ArrayList is technically faster, but unless we’re doing something really performance-sensitive, we shouldn't worry about this -- they're both constants.)
Let’s go through some scenarios :-
As someone who has been doing operational performance engineering on very large scale SOA web services for about a decade, I would prefer the behaviour of LinkedList over ArrayList. While the steady-state throughput of LinkedList is worse and therefore might lead to buying more hardware — the behaviour of ArrayList under pressure could lead to apps in a cluster expanding their arrays in near synchronicity and for large array sizes could lead to lack of responsiveness in the app and an outage, while under pressure, which is catastrophic behaviour.
Similarly, we can get better throughput in an app from the default throughput tenured garbage collector, but once we get java apps with 10GB heaps we can wind up locking up the app for 25 seconds during a Full GCs which causes timeouts and failures in SOA apps and blows our SLAs if it occurs too often. Even though the CMS collector takes more resources and does not achieve the same raw throughput, it is a much better choice because it has more predictable and smaller latency.
ArrayList is only a better choice for performance if all you mean by performance is throughput and we can ignore latency.
<script src=”https://gist.github.com/govindaraj/e0db08a46cd044fc06f14e7568ff01d1.js”></script>
