筆記: Java Collections

1. Collection Interfaces:

(from Sun Java Collection Tutorials)

2. Set --> not duplicate , List --> can duplicate,ordered.

3. Hashtable --> Map.

4. 2 種往返Collection的方法：
a. for迴圈

for (Object o : collection)
System.out.println(o);

b. Iterator
static void filter(Collection<?> c) {

for (Iterator<?> it = c.iterator(); it.hasNext(); )
if (!cond(it.next()))
it.remove();
}

5. 移除collection裡的所有null元素：
c.removeAll(Collections.singleton(null));

6. 陣列和collection的橋樑： toArray()

7. Set -->
a. HashSet--> not ordered, fast
b. TreeSet --> ordered by element value. slow
c. LinkedHashSet --> ordered
8. List -->
a. ArrayList-->
b. LinkedList-->

9. List interface:
public interface List<E> extends Collection<E> {
// Positional access
E get(int index);
E set(int index, E element); //optional
boolean add(E element); //optional
void add(int index, E element); //optional
E remove(int index); //optional
boolean addAll(int index,Collection<? extends E> c); //optional

// Search
int indexOf(Object o);
int lastIndexOf(Object o);

// Iteration
ListIterator<E> listIterator();
ListIterator<E> listIterator(int index);

// Range-view
List<E> subList(int from, int to);
}

10. Array to List：
java.utli.Arrays.asList(arr);

11. List.iterator傳回ListIterator物件。
12. ListIterator介面：
public interface ListIterator<E> extends Iterator<E> {
boolean hasNext();
E next();
boolean hasPrevious();
E previous();
int nextIndex();
int previousIndex();
void remove(); //optional
void set(E e); //optional
void add(E e); //optional
}

13. Queue 介面：
public interface Queue<E> extends Collection<E> {
boolean offer(E e); -> bounded Queue時，若已滿，傳回false。
add(E e) -> bounded Queue時，若已滿，IllegalStateException。
E peek(); -> //Queue空時，傳回Null，取出但不刪除
E element(); --> //Queue空時，NoSuchElementException，取出但不刪除
E poll(); //Queue空時，傳回Null
E remove(); //Queue空時，NoSuchElementException
}

14. Map 介面：
public interface Map<K,V> {

// Basic operations
V put(K key, V value);
V get(Object key);
V remove(Object key);
boolean containsKey(Object key);
boolean containsValue(Object value);
int size();
boolean isEmpty();

// Bulk operations
void putAll(Map<? extends K, ? extends V> m);
void clear();

// Collection Views
public Set<K> keySet();
public Collection<V> values();
public Set<Map.Entry<K,V>> entrySet();

// Interface for entrySet elements
public interface Entry {
K getKey();
V getValue();
V setValue(V value);
}
}

15. Map -->
a. HashMap
b. TreeMap
c. LinkedHashMap

16. List -- Vector
Map -- HashTable

17. 如果要用Collections.sort(list)，在List中的元素需要實做comparable介面。否則會
ClassCastException。

18. Comparable介面：
public interface Comparable<T> {
public int compareTo(T o);
}

19. exam Comparable impl: (from Sun Java Collection Tutorials)
import java.util.*;

public class Name implements Comparable<Name> {
private final String firstName, lastName;

public Name(String firstName, String lastName) {
if (firstName == null || lastName == null)
throw new NullPointerException();
this.firstName = firstName;
this.lastName = lastName;
}

public String firstName() { return firstName; }
public String lastName() { return lastName; }

public boolean equals(Object o) {
if (!(o instanceof Name))
return false;
Name n = (Name)o;
return n.firstName.equals(firstName) &&
n.lastName.equals(lastName);
}

public int hashCode() {
return 31*firstName.hashCode() + lastName.hashCode();
}

public String toString() {
return firstName + " " + lastName;
}

public int compareTo(Name n) {
int lastCmp = lastName.compareTo(n.lastName);
return (lastCmp != 0 ? lastCmp :
firstName.compareTo(n.firstName));
}
}


20. 若要使用collections.sort(e, comparator)需要實做Comparator介面：

public interface Comparator {
 int compare(T o1, T o2);
}


21. SortedSet介面：
public interface SortedSet extends Set {
 // Range-view
 SortedSet subSet(E fromElement, E toElement);
 SortedSet headSet(E toElement);
 SortedSet tailSet(E fromElement);

 // Endpoints
 E first();
 E last();

 // Comparator access
 Comparator comparator();

22. SortedMap介面：
public interface SortedMap extends Map{
 Comparator comparator();
 SortedMap subMap(K fromKey, K toKey);
 SortedMap headMap(K toKey);
 SortedMap tailMap(K fromKey);
 K firstKey();
 K lastKey();
}
}

23. implementations: (from Sun Java Collection Tutorials)

General-purpose Implementations

Interfaces	Implementations
	Hash table	Resizable array	Tree	Linked list	Hash table + Linked list
Set	HashSet		TreeSet		LinkedHashSet
List		ArrayList		LinkedList
Queue
Map	HashMap		TreeMap		LinkedHashMap