Java-Collections

• Java basic data type
  • ordered:
    • array
      • array
      • ArrayList
    • LinkedList
      • LinkedList
    • queue
      •  LinkedList
    • stack
      • LinkedList
  • unordered
    • Set
      • HashSet(store data  in a hash table)
      • treeSet(store data in a binary tree)
  • Map
    • HashMap(key,data)
    • TreeMap(key,data)
• 
• Collection interface
  • Contain List, Quene and Set
  • methods
    • Collection<T> coll = new ArrayList(HashSet/TreeSet)<T>();
    • int n = coll.size();
    • coll.add(T2);
    • coll.toString();
    • coll.remove(Tn);
    • coll.contains(Tx); return a boolean
    • Iterator<T> iterator = coll.iter()
      • iterator.next()
        • return the next element of iterator
        • strat from first element
      • iterator.previous
        • return the element before iterator
      • iterator.set(Ta)
        • set element point to to Ta
      • iterator.hasNext
        • return true if not the end of collection
      • iterator.haxPrevious
        • return true if not the start of collection
      • iterator.add(Ts)
        • add Ts before the element iterator point to (linkedlist only)
        • add Ts after iterator
      • iter.next
        • point to next element
      • iter.previous
        • point to previous element
      • iter.remove
        • remove the element iterator point to (linkedlist only)
      • iter used behind for-in loop
• LinkedList
  • Efficient
    • insert a node
    • remove a node
    • visit all node in order
  • inEfficient
    • random access
  • methods
    • addLast()/addFirst()
    • getLast()/getFirst()
    • removeFirst()/removeLast()
    • ListIterator<T> iterator = list.listIterator();
• Set
  • unordered
    • not support dublicate element
  • HashSet(store data  in a hash table)
    • element are grouped base on same characteristic
      • by transfer characteristic to a hashCode and compare
        • calculate a integer base on data and return it
        • Java Library contain some hashCode function
        • should compatiable with .equals() function
      • may happen different element have same hash code(collision)
        • put them into LinkedList
    • contain .equal() method to compare element
  • treeSet(store data in a binary tree)
    • set element is keeped in sorted order and arranged in a tree shape collection
    • use TreeSet when class can implement to comparable interface
    • each node on tree set have 2 child node
      • left child have small value
      • right child nhave larger value
  • Iterator can also use for Set
    • hasNext
    • next
    • add
  • methods
    • add(T)
    • contains()
    • for-in
    • remove
      • can remove a element not exist, won`t do any thing
    • toString
      • print in order inserted
• Map
  • allow to access any element in map with a “key”
    • a data can have multiple key, but each key only refers to one value
  • methods
    • put(key,data)
    • get(key)
    • remove(key)
    • for(key in map)
  • use keySet() to get a set of all keys
• Step choose a collection
  • how to access value
    • position/number/order-> LinkedList
    • key -> Map
    • whatever
  • element type and key type
    • only element -> LinkedList/Set
    • + key -> Map
  • order matter
    • base on size -> TreeMap/TreeSet
    • same order as insert -> LinkedList/ArrayList
    • what ever
  • which operation must be fast
    • search -> HashSet
    • Add/remove at first/end/middle -> LinkedList
    • only few element/ add&remove at end -> ArrayList
  • HashSet/HashMap-> hashCode function and equals function
    • implement by yourself
  • Tree -> compare elements
    • implement Comparable interface