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 you have a large list of sorted elements, either an arraylist or a linkedlist. suppose to That you do a binary search on the L ist. 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 LinkedList: import java.util *; public class ListDemo1 {static final int N = 10000; static List values; // make List of increasing Integer values static {Integer vals [] = new Integer [N];. Random rn = new random ();
For (int i = 0, currval = 0; i . Scenario In this demo, a program repeatedly inserts elements at the beginning of a list The code looks like this:.. Import java.util *; public class ListDemo2 {static final int N = 50000; // time how long it takes to Add // n Objects to a list static long timelist (list LST) {long start = system.currenttimemillis (); object obj = new object (); for (int i = 0; i s look at some internal details of how ArrayList and LinkedList are implemented in Java 2 SDK, Standard Edition v 1.4. These details are not part of the external specification of these classes, but are illustrative of how such classes work internally. The LinkedList class has a private internal class defined like this: private static class Entry {Object element; Entry next; Entry previous;} Each Entry object references a list element, along with the next and previous elements in the LinkedList - in other words, a doubly- linked list. A LinkedList of 1000 elements will have 1000 Entry objects linked together, referencing the actual list elements. There is significant space overhead in a LinkedList structure, given all these Entry objects. An ArrayList has a backing Object array to store the elements. This Array Starts with a Capacity of 10. When a Array Needs To Grow, The New Capacity IS Comput As: New CaPacity = (Oldcapacity * 3) / 2 1; Notice that the array capacity grows each time by 50% about. This means that if you have an ArrayList with a large number of elements, there will be a significant amount of space wasted at the end. This waste is intrinsic to the way ArrayList works . If there was no spare capacity, the array would have to be reallocated for each new element, and performance would suffer dramatically. Changing the growth strategy to be more aggressive (such as doubling the size at each reallocation) would result in slightly better performance , but it would waste more space. If you know how many elements will be in an ArrayList, you can specify the capacity to the constructor. you can also call the trimToSize method after the fact to reallocate the internal array. This gets rid of the wasted space. So far, this discussion has assumed that either an ArrayList or a LinkedList is "right" for a given application. But sometimes, other choices make more sense. for example, consider the very common situation whe Re you have a list of key / value pairs, and you would like to retrieve a value for a given key. You Could Store THE PAIRS IN N N x 2 Object Array. To Find The Right Pair, You Could Do A Sequential Search on The key value. this approach works, and is a useful choice for very small lists (SAY 10 Elements Or Less), But it doesn ' t scale to big lists. Another approach is to sort the key / value pairs by ascending key value, store the result in a pair of ArrayLists, and then do a binary search on the keys list. This approach also works, and is very fast . Yet another approach is to not use a list structure at all, but instead use a map structure (hash table), in the form of a HashMap. Which is faster, a binary search on an ArrayList, or a HashMap? Here's a final example that compares these two: import java.util *; public class ListDemo3 {static final int N = 500000; // Lists of keys and values static List keys; static List values; // fill the keys list with ascending order key /. / values and fill the values list with // corresponding value (-key) static {integer keyvec [] = new integer [n]; integer valueVec [] = new integer [n]; random rn = new random (); for INT i = 0, currval = 0; i System.currenttimemillis (); for (int i = 0; i
