Datastructure Java

List :

ArrayList and LinkedList

List is a ordered collection.

Can contain duplicate elements

You can access element in a list by their integer indexes.

ArrayList is the default choice. Offer constant time positional access, quite fast.

Consider LinkedList for frequently add elements to the beginning of the List or iterate over the List and delete elements from its interior. These are constant time operation in the LinkedList and linear operation in ArrayList.

Positional access is much slower in LinkedList. Linear time for LinkedList and constant time for the ArrayList.

Set :

HashSet and TreeSet

• A collection that CANNOT contain duplicate elements.


• Used to represent cards in a poker hand or processes running on a machine


• HashSet is much faster but no ordering guarantees. This is mostly used.


• TreeSet is in order iteration . What you entered will be in same sequence while iteration FIFO


• Default initial capacity is 101. Should set it twice the size that you expect the Set to grow.
  Set s = new HashSet(17); Here intial capacity is set to 17


• Load factor is the tuning parameter. Default is (.75) when the number of entries exceeds the product of the load factor and the current capacity the capacity is doubled. Higher value decrease the space overhead, but increase the time it takes to look up an entry.

Map :

HashMap and TreeMap

• Map is an Object that maps key to values.


• Maps CANNOT contain duplicate keys


• HashMap is not ordered , TreeMap is ordered analogous to List.

Synchronized Collections

• HashTable and Vector are fully synchronized Classes in the collections framework are not synchronized by default.


• Wrapper classes add functionality to the standard Collection (interface) implementation.


• Factory method defined in the Collections class(not to be confused with the Collection interface).

public static Collection synchronizedCollection(Collection c);

public static Set synchronizedSet(Set s);

public static List synchronizedList(List list);

public static Map synchronizedMap(Map m);

public static SortedSet synchronizedSortedSet(SortedSet s);

public static SortedMap synchronizedSortedMap(SortedMap m);

• Iterate over synchronized collection , you have to manually synchronise the iteration operation. Failing to use this idiom can result in non-deterministic behavior.
  

Collection c = Collections.synchronizedCollection(myCollection);
Synchronized(c){
Iterator i = c.iterator(); // it should be inside synchronized block
While(i.hasNext()){
System.out.println(i.next());
}

Algorithms

• sort and binarySearch available in Collections class as static method.
  
  public static int binarySearch(List list, Object key);
  public static int binarySearch(List list, Object key,Comparator c);
  
  public static void sort(List list);
  public static void sort(List list, Comparator c);
  

References : http://java.sun.com/docs/books/performance/1st_edition/html/JPAlgorithms.fm.html
(Read more on this link. This blog is summary sun java)