今天開始更新Java集合類相關(guān)博客，暫時(shí)打算分為List,Set,Map三個(gè)部分講解，先出一個(gè)原型博客然后迭代更新（PS:依稀記得某些算法博客我也是這么說的然后原型寫完就沒后續(xù)了.......）。在講最簡單的List之前，先介紹下Collection接口的所有相關(guān)類的層次結(jié)構(gòu)。
1. 集合類的層次關(guān)系
Java類的集合關(guān)系如圖：
具體而言,Collection相關(guān)的類關(guān)系如下：
- Collection<--List<--Vector
- Collection<--List<--ArrayList
- Collection<--List<--LinkedList
- Collection<--Set<--HashSet
- Collection<--Set<--HashSet<--LinkedHashSet
- Collection<--Set<--SortedSet<--TreeSet
- Collection<--Queue
- Map<--SortedMap<--TreeMap
- Map<--HashMap
2. List接口簡介
List是有序的Collection，有以下幾個(gè)特性：
- 元素可以使用索引去訪問，類似于Java的數(shù)組。
- 具有列表的功能，元素的順序是按照添加的先后排序的。
- 允許重復(fù)元素和null元素。
3. List的常用方法
// C增：初始化，以ArrayList()為例
List list = new ArrayList();
// C增：向列表的尾部追加指定的元素
list.add("lwc");
// C增：在列表的指定位置插入指定元素
list.add(1, "nxj");
// C增：追加指定 collection 中的所有元素到此列表的結(jié)尾
list.addAll(new ArrayList());
// U更：用指定元素替換列表中指定位置的元素
list.set(0, "lp");
// R查：如果列表包含指定的元素,則返回true
list.contains("nxj");
// R查：如果列表包含指定 collection 的所有元素,則返回 true
list.containsAll(new ArrayList());
// R查：比較指定的對(duì)象與列表是否相等
list.equals(new ArrayList());
// R查：返回列表中指定位置的元素
list.get(0);
// R查：返回列表的哈希碼值
list.hashCode();
// R查：返回列表中首次出現(xiàn)指定元素的索引,如果列表不包含此元素,則返回 -1
list.indexOf("lwc");
// R查：返回列表中最后出現(xiàn)指定元素的索引,如果列表不包含此元素,則返回 -1
list.lastIndexOf("lwc");
// R查：如果列表不包含元素,則返回 true
list.isEmpty();
// R查：返回包含列表中的所有元素的Object[]數(shù)組
list.toArray();
// R查：返回包含列表中所有元素的數(shù)組，可以用參數(shù)指定對(duì)象類型
list.toArray(new String[] { "a", "b" });
// R查：返回列表中的元素?cái)?shù)
list.size();
// R查：返回列表中指定的fromIndex(包括)和toIndex(不包括)之間的視圖，即其中內(nèi)容仍為原List對(duì)象中內(nèi)容，若更改會(huì)影響原List對(duì)象。
list.subList(1, 2);
// D刪：移除列表中指定位置的元素
list.remove(0);
// D刪：移除列表中出現(xiàn)的首個(gè)指定元素
list.remove("lwc");
// D刪：從列表中移除指定 collection 中包含的所有元素
list.removeAll(new ArrayList());
// D刪：從列表中移除所有元素
list.clear();
4. List實(shí)例
4.1. Vector
Vector是基于數(shù)組的List，相當(dāng)于給數(shù)組添加了一些方便調(diào)用的功能。因此，它難以避免一些數(shù)組的限制，且性能也不會(huì)超過數(shù)組。Vector和ArrayList的區(qū)別是Vector中各方法是synchronized修飾的方法。而ArrayList中各方法沒有synchronized修飾。因而，Vector是線程安全的而ArrayList不是，這也是它們最大的區(qū)別。
4.2. ArrayList
和Vector一樣是基于數(shù)組的一種List結(jié)構(gòu)，和Vector相比，由于其方法沒有被synchronized修飾，因此有著更好的性能，但是在多線程環(huán)境下需要十分小心。
4.3. Vector和ArrayList的擴(kuò)容
由于Vector和ArrayList是基于數(shù)組的，當(dāng)數(shù)組的容量不夠時(shí)（默認(rèn)的初始容量是10，可以通過構(gòu)造器自己設(shè)置），將會(huì)發(fā)生1.5倍擴(kuò)容。易知如果擴(kuò)容長度為2倍，那么新的數(shù)組無法利用擴(kuò)容時(shí)釋放的舊數(shù)組內(nèi)存。當(dāng)然，選擇2倍在時(shí)間上要優(yōu)于1.5倍。
4.4. LinkedList
不同于ArrayList和Vector，LinkedList如其名是不基于數(shù)組而是基于鏈接表的。因此，LinkedList的性能是不受數(shù)組限制的。LinkedList的節(jié)點(diǎn)構(gòu)成如下：
private static class Node<E> {
E item;
Node<E> next;
Node<E> prev;
Node(Node<E> prev, E element, Node<E> next) {
this.item = element;
this.next = next;
this.prev = prev;
}
}
我們可以看到，LinkedList基于一個(gè)雙向鏈接表，因此，當(dāng)進(jìn)行List中間位置的刪除/添加工作時(shí)，LinkedList不會(huì)像ArrayList一樣需要改動(dòng)整個(gè)數(shù)組，僅僅對(duì)相關(guān)節(jié)點(diǎn)進(jìn)行改動(dòng)即可。但同時(shí)，在進(jìn)行查詢?nèi)蝿?wù)時(shí)，LinkedList的性能將劣于ArrayList。
