Install Eclipse WTP build 2.0 and JadClipse

Eclipse WTP build 2.0 requires Java 1.5 installed.

To install JadClipse, first follow the instructions on this page.

Note: make sure the class files you want to decompile is on your classpath.

Java 101

ArrayList and LinkedList

Speed

• An ArrayList is backed by a primitive Object array. Because of that, an ArrayList is much faster than a LinkedList for random access.


• 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 if ignored.


• LinkedList is a bad choice in this situation. The binary search algorithm inherently uses random access, and LinkedList does not support fast random access. The time to do a random access in a LinkedList is proportional to the size of the list. By comparison, random access in an ArrayList has a fixed time.


• If you have lots of element inserting and deleting, LinkedList is a better choice.


• When an element is added to the beginning of an ArrayList, all of the existing elements must be pushed back, which means a lot of expensive data movement and copying. By contrast, adding an element to the beginning of a LinkedList simply means allocating an internal record for the element and then adjusting a couple of links. Adding to the beginning of a LinkedList has fixed cost, but adding to the beginning of an ArrayList has a cost that's proportinal to the list size.

Space

• 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 a 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 the array needs to grow, the new capacity is computed as:
  newCapacity = (oldCapacity *3)/2 +1


• Notice that the array capacity grows each time by about 50%. 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.

Summary

• Appending elements to the end of a list has a fixed averaged cost for both ArrayList and LinkedList. For ArrayList, appending typically involves setting an internal array location to the element reference. but occasionally results in the array being reallocated. For LinkedList, the cost of uniform and involves allocating an internal Entry object.


• Inserting or deleting elements in the middle of an ArrayList implies that the rest of the list must be moved. Inserting or deleting elements in the middle of a LinkedList has fixed cost.


• A LinkedList does not support efficient random access.


• An ArrayList has space overhead in the form of reserve capacity at the end of the list. A LinkedList has significant space overhead per element.


• Sometimes a Map structure is a better choice than a List.

ref