USING ArrayList AND LINKEDLIST
ArrayList and LinkedList are two Collections classes used for storing lists of object references. For example, you could have an ArrayList of Strings, or a LinkedList of Integers. This tip compares the performance of ArrayList and LinkedList, and offers some suggestions about which of these classes is the right choice in a given situation.
The first key point is that an ArrayList is backed by a primitive Object array. Because of that, an ArrayList is much faster than a LinkedList for random access, that is, when accessing arbitrary list elements using the get method. Note that the get method is implemented for LinkedLists, but it requires a sequential scan from the front or back of the list. This scan is very slow. For a LinkedList, there''s no fast way to access the Nth element of the list.
Consider the following example. Suppose you have a large list of sorted elements, either an ArrayList or a LinkedList. Suppose too that you do a binary search on the list. The standard binary search algorithm starts by checking the search key against the value in the middle of the list. If the middle value is too high, then the upper half of the list is eliminated. However, if the middle value is too low, then the lower half of the list is ignored. This process continues until the key is found in the list, or until the lower bound of the search becomes greater than the upper bound.
Here''s a program that does a binary search on all the elements in an ArrayList or a Lin