在上一節(jié)中，介紹了Java集合的整體情況。從這節(jié)開始，將介紹具體的類。這里不單單介紹類的用法，還會(huì)試圖從源碼的角度分析類的實(shí)現(xiàn)。這一節(jié)將介紹List接口及實(shí)現(xiàn)類，即列表中的鏈表LinkedList和數(shù)組列表ArrayList。

1 List接口及抽象類

List接口擴(kuò)展自Collection接口，這個(gè)接口設(shè)計(jì)了一些適合列表操作的方法。List是一個(gè)有序集合，元素可以添加到容器中某個(gè)特定的位置。

使用javac編譯List.java源碼后，可以使用javap反編譯源碼獲得接口的具體信息，如下是調(diào)用后的結(jié)果：

Compiled from "List.java" public interface java.util.List<E> extends java.util.Collection<E> {public abstract int size();public abstract boolean isEmpty();public abstract boolean contains(java.lang.Object);public abstract java.util.Iterator<E> iterator();public abstract java.lang.Object[] toArray();public abstract <T> T[] toArray(T[]);public abstract boolean add(E);public abstract boolean remove(java.lang.Object);public abstract boolean containsAll(java.util.Collection<?>);public abstract boolean addAll(java.util.Collection<? extends E>);public abstract boolean addAll(int, java.util.Collection<? extends E>);public abstract boolean removeAll(java.util.Collection<?>);public abstract boolean retainAll(java.util.Collection<?>);public void replaceAll(java.util.function.UnaryOperator<E>);public void sort(java.util.Comparator<? super E>);public abstract void clear();public abstract boolean equals(java.lang.Object);public abstract int hashCode();public abstract E get(int);public abstract E set(int, E);public abstract void add(int, E);public abstract E remove(int);public abstract int indexOf(java.lang.Object);public abstract int lastIndexOf(java.lang.Object);public abstract java.util.ListIterator<E> listIterator();public abstract java.util.ListIterator<E> listIterator(int);public abstract java.util.List<E> subList(int, int);public java.util.Spliterator<E> spliterator(); }List接口提供了這些方法，大部分是Abstract的，但也有一部分不是，這部分方法是JDK 1.8 新增的default方法，比如sort方法。

List接口提供了隨機(jī)訪問方法，比如get(int)方法，但是List并不管這些方法都某個(gè)特定的實(shí)現(xiàn)是否高效。為了避免執(zhí)行成本較高的隨機(jī)訪問操作，Java SE 1.4 引入了一個(gè)標(biāo)記接口RandomAccess。這個(gè)接口沒有任何方法，但可以用來檢測(cè)一個(gè)特定的集合是否支持高效的隨機(jī)訪問：

if(c instanceof RandomAccess) {use random access algorighm } else {use sequential access algorithm }ArrayList就實(shí)現(xiàn)了這個(gè)接口。

List接口中的例行方法在抽象類AbstractList中實(shí)現(xiàn)了，這樣就不需要在具體的類中實(shí)現(xiàn)，比如isEmpty方法和contains方法等。這些例行方法比較簡單，含義也明顯。對(duì)于隨機(jī)訪問元素的類（比如ArrayList），優(yōu)先繼承這個(gè)抽象類。

在AbstractList抽象類中，有一個(gè)重要的域，叫modCount：

protected transient int modCount = 0;

這個(gè)域可以用來跟蹤列表結(jié)構(gòu)性修改的次數(shù)，什么是結(jié)構(gòu)性修改呢？就是改變列表長度的修改，比如增加、刪除等。對(duì)于只修改某個(gè)節(jié)點(diǎn)的值不算結(jié)構(gòu)性修改。

這個(gè)域在后面的迭代器中非常有用。迭代器可以使用這個(gè)域來檢測(cè)并發(fā)修改問題，這個(gè)問題會(huì)在LinkedList類中介紹。

抽象類AbstractSequentialList實(shí)現(xiàn)了List接口中的一些方法，對(duì)于順序訪問元素的類（比如LinkedList），優(yōu)先繼承這個(gè)抽象類。

2 鏈表：LinkedList

鏈表是一個(gè)大家非常熟悉的數(shù)據(jù)結(jié)構(gòu)。鏈表解決了數(shù)組列表插入和刪除元素效率太低的問題，鏈表的插入和刪除就非常高效。

鏈表將每個(gè)對(duì)象存放在獨(dú)立的節(jié)點(diǎn)中。Java中的LinkedList鏈表，每個(gè)節(jié)點(diǎn)除了有后序節(jié)點(diǎn)的引用外，還有一個(gè)前序節(jié)點(diǎn)的引用，也就是說，LinkedList是一個(gè)雙向鏈表。

LinkedList類有三個(gè)域，分別是大小、頭結(jié)點(diǎn)和尾節(jié)點(diǎn)：

transient int size; transient Node<E> first; transient Node<E> last;
還有兩個(gè)構(gòu)造器，一個(gè)無參構(gòu)造器和一個(gè)含參構(gòu)造器：

public java.util.LinkedList(); public java.util.LinkedList(java.util.Collection<? extends E>);
其中無參構(gòu)造器構(gòu)造一個(gè)空的鏈表，含參構(gòu)造器根據(jù)傳進(jìn)來的一個(gè)集合構(gòu)造一個(gè)鏈表。

2.1 Node<E>內(nèi)部類

LinkedList類中，定義了一個(gè)Node<E>內(nèi)部類來表示一個(gè)節(jié)點(diǎn)。這個(gè)類的定義如下：

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;} }這是一個(gè)靜態(tài)內(nèi)部類，也沒有對(duì)外部的引用，這個(gè)類有三個(gè)域：值，前序節(jié)點(diǎn)的引用，后序節(jié)點(diǎn)的引用，也有一個(gè)構(gòu)造方法，定義很簡單。

如果要?jiǎng)?chuàng)建一個(gè)Node節(jié)點(diǎn)，可以這樣：

Node<E> node=new Node<>(pre,item,next);
其中，pre和next分別是前序節(jié)點(diǎn)和后序節(jié)點(diǎn)的引用。

2.2 鏈表操作的基本方法

既然是鏈表，就少不了鏈表節(jié)點(diǎn)的添加與刪除。在LinkedList類中，提供了六個(gè)基本的鏈表操作的方法，這些方法都對(duì)鏈表的結(jié)構(gòu)進(jìn)行修改，因此會(huì)改變AbstractList類中的modCount域，這六個(gè)方法如下：

private void linkFirst(E);//在鏈表頭部添加給定值的節(jié)點(diǎn)作為頭結(jié)點(diǎn) void linkLast(E);//在鏈表尾部添加一個(gè)給定值的節(jié)點(diǎn)作為尾節(jié)點(diǎn) void linkBefore(E, java.util.LinkedList$Node<E>);//在給定的節(jié)點(diǎn)前插入一個(gè)節(jié)點(diǎn) private E unlinkFirst(java.util.LinkedList$Node<E>);//刪除頭結(jié)點(diǎn)，并返回頭結(jié)點(diǎn)的值 private E unlinkLast(java.util.LinkedList$Node<E>);//刪除尾節(jié)點(diǎn)，并返回尾節(jié)點(diǎn)的值 E unlink(java.util.LinkedList$Node<E>);//刪除給定的節(jié)點(diǎn)這些方法都是私有的（或包內(nèi)私有的），因此可以稱為工具方法，LinkedList類中的所有結(jié)構(gòu)性修改操作都是基于這六個(gè)方法實(shí)現(xiàn)的。

這六個(gè)方法都是鏈表的基本操作，代碼比較簡單，不過給出實(shí)現(xiàn)可以看看源碼實(shí)現(xiàn)者的寫法，對(duì)于自己編程還是有幫助的：

/*** Links e as first element.*/private void linkFirst(E e) {final Node<E> f = first;final Node<E> newNode = new Node<>(null, e, f);first = newNode;if (f == null)last = newNode;elsef.prev = newNode;size++;modCount++;}/*** Links e as last element.*/void linkLast(E e) {final Node<E> l = last;final Node<E> newNode = new Node<>(l, e, null);last = newNode;if (l == null)first = newNode;elsel.next = newNode;size++;modCount++;}/*** Inserts element e before non-null Node succ.*/void linkBefore(E e, Node<E> succ) {// assert succ != null;final Node<E> pred = succ.prev;final Node<E> newNode = new Node<>(pred, e, succ);succ.prev = newNode;if (pred == null)first = newNode;elsepred.next = newNode;size++;modCount++;}/*** Unlinks non-null first node f.*/private E unlinkFirst(Node<E> f) {// assert f == first && f != null;final E element = f.item;final Node<E> next = f.next;f.item = null;f.next = null; // help GCfirst = next;if (next == null)last = null;elsenext.prev = null;size--;modCount++;return element;}/*** Unlinks non-null last node l.*/private E unlinkLast(Node<E> l) {// assert l == last && l != null;final E element = l.item;final Node<E> prev = l.prev;l.item = null;l.prev = null; // help GClast = prev;if (prev == null)first = null;elseprev.next = null;size--;modCount++;return element;}/*** Unlinks non-null node x.*/E unlink(Node<E> x) {// assert x != null;final E element = x.item;final Node<E> next = x.next;final Node<E> prev = x.prev;if (prev == null) {first = next;} else {prev.next = next;x.prev = null;}if (next == null) {last = prev;} else {next.prev = prev;x.next = null;}x.item = null;size--;modCount++;return element;}

2.3 列表迭代器：ListIterator接口

鏈表是一個(gè)有序集合，每個(gè)對(duì)象的位置十分重要。LinkedList.add方法只是將節(jié)點(diǎn)加到尾部，然而對(duì)于鏈表的操作還有很大一部分需要將節(jié)點(diǎn)添加到鏈表中間。由于迭代器是秒數(shù)集合中的位置的，所以這種依賴位置的添加方法將由迭代器負(fù)責(zé)。只有對(duì)自然有序的集合使用迭代器添加元素才有意義。比如，對(duì)于無序的集合set，在Iterator接口中就沒有add方法。相反的，在集合類庫中提供了ListIterator接口，其中就有add方法：

interface ListIterator<E> extends Iterator<E> {void add(E element);... }與Collection接口中的add方法不同，這個(gè)方法不返回boolean類型的值，因?yàn)樗俣ㄌ砑硬僮骺偸歉淖冩湵怼?

另外，除了hasNext和next方法，ListIterator接口還提供了下面的兩個(gè)方法：

E previous(); boolean hasPrevious();這兩個(gè)方法用來反向遍歷鏈表，previous也像next一樣，返回越過的對(duì)象。

LinkedList類的listIterator方法返回一個(gè)迭代器對(duì)象：

ListIterator<String> iter=list.listIterator();在介紹接口時(shí)我們知道，不能實(shí)例化一個(gè)接口對(duì)象，但可以聲明一個(gè)接口對(duì)象然后引用一個(gè)實(shí)現(xiàn)了該接口的類的實(shí)例。那么listIterator方法返回的就必然是一個(gè)類的實(shí)例，而這個(gè)類也必然實(shí)現(xiàn)了這個(gè)接口，問題是，這個(gè)類是什么？

這個(gè)類其實(shí)是LinkedList的一個(gè)內(nèi)部類，即ListItr：

Compiled from "LinkedList.java" class java.util.LinkedList$ListItr implements java.util.ListIterator<E> {private java.util.LinkedList$Node<E> lastReturned;private java.util.LinkedList$Node<E> next;private int nextIndex;private int expectedModCount;final java.util.LinkedList this$0;java.util.LinkedList$ListItr(java.util.LinkedList, int);public boolean hasNext();public E next();public boolean hasPrevious();public E previous();public int nextIndex();public int previousIndex();public void remove();public void set(E);public void add(E);public void forEachRemaining(java.util.function.Consumer<? super E>);final void checkForComodification(); }上面也是使用javap反編譯的結(jié)果。可以看到，這個(gè)內(nèi)部類實(shí)現(xiàn)了ListIterator接口，并實(shí)現(xiàn)了這個(gè)接口的方法。

這正是理解迭代器的關(guān)鍵。我們知道，迭代器可以看做是一個(gè)位置，這個(gè)位置在兩個(gè)節(jié)點(diǎn)的中間，也就是說，對(duì)于一個(gè)大小為n的鏈表，迭代器的位置有n+1個(gè)：

| a | b | ...| z |

在這個(gè)例子中，鏈表表示26個(gè)字母，迭代器的位置就有27個(gè)。

這里也是把迭代器形象化為光標(biāo)，next方法就是光標(biāo)移到下一個(gè)位置，飯后返回剛剛越過的元素，同理previous也是一樣，只不過是左移一個(gè)位置，然后返回剛剛越過的元素。下面是這兩個(gè)方法的代碼：

public E next() {checkForComodification();if (!hasNext())throw new NoSuchElementException();lastReturned = next;next = next.next;nextIndex++;return lastReturned.item; }public E previous() {checkForComodification();if (!hasPrevious())throw new NoSuchElementException();lastReturned = next = (next == null) ? last : next.prev;nextIndex--;return lastReturned.item; }這兩個(gè)方法首先調(diào)用checkForComodifcation方法檢查并發(fā)修改問題。前面說過，AbstractList的modCount記錄了鏈表的修改次數(shù)，而每一個(gè)迭代器都通過下面的字段維護(hù)一個(gè)獨(dú)立的計(jì)數(shù)器：

private int expectedModCount = modCount;這個(gè)域初始化為類的modCount修改次數(shù)。而checkForComodification檢查迭代器自己維護(hù)的計(jì)數(shù)器是否和類的modCount相等，如果不等，就會(huì)拋出一個(gè)ConcurrentModificationException。

并發(fā)修改檢查通過后，會(huì)調(diào)用hasNext或hasPrevious方法檢查是否有待訪問的元素。ListItr類有一個(gè)nextIndex域：

private int nextIndex;這個(gè)域維護(hù)迭代器的當(dāng)前位置，當(dāng)然，對(duì)于LinkedList來說，由于迭代器指向兩個(gè)元素中間，所以可以同時(shí)產(chǎn)生兩個(gè)索引：nextIndex方法返回下一次調(diào)用next方法時(shí)返回元素的整數(shù)索引；previousIndex返回下一次調(diào)用previous方法時(shí)返回元素的索引，這個(gè)索引比nextIndex小1。

hasNext和hasPrevious方法就是檢查nextIndex和previousIndex是否在正確范圍來確實(shí)是否有待訪問元素的。

ListItr類還有兩個(gè)域：

private Node<E> lastReturned; private Node<E> next;lastReturned用來保存上次返回的節(jié)點(diǎn)，next就是迭代器位置的下一個(gè)元素，也可以看做光標(biāo)的下一個(gè)元素（下一個(gè)元素總是光標(biāo)的右面那個(gè)元素）。調(diào)用next方法后，光標(biāo)右移一位，越過next域保存的節(jié)點(diǎn)，然后更新這兩個(gè)域的值，即剛才的next變?yōu)閘astReturned，next就是再下一個(gè)元素，然后nextIndex增1。

previous相對(duì)于next操作來說相當(dāng)于光標(biāo)左移一位，在更新lastReturned和next時(shí)，需要考慮next是否為null。如果next為null，說明在沒執(zhí)行previous時(shí)，迭代器在最后一個(gè)位置，所以執(zhí)行previous后，next應(yīng)該是鏈表的尾節(jié)點(diǎn)last；如果next不是null，那么next更新為next的前序節(jié)點(diǎn)。而lastReturned為光標(biāo)剛越過的元素，即現(xiàn)在的next節(jié)點(diǎn)，這時(shí)，lastReturned和next節(jié)點(diǎn)指向同一個(gè)元素。

ListItr類有三個(gè)可以修改鏈表的方法：add、remove和set。其中add和remove會(huì)改變迭代器的位置，因?yàn)檫@兩個(gè)方法修改了鏈表的結(jié)構(gòu)；而set方法不會(huì)修改迭代器的位置，因?yàn)樗恍薷逆湵淼慕Y(jié)構(gòu)。

這三個(gè)方法的代碼如下：

public void remove() {checkForComodification();if (lastReturned == null)throw new IllegalStateException();Node<E> lastNext = lastReturned.next;unlink(lastReturned);if (next == lastReturned)next = lastNext;elsenextIndex--;lastReturned = null;expectedModCount++; }public void set(E e) {if (lastReturned == null)throw new IllegalStateException();checkForComodification();lastReturned.item = e; }public void add(E e) {checkForComodification();lastReturned = null;if (next == null)linkLast(e);elselinkBefore(e, next);nextIndex++;expectedModCount++; }值得注意的是remove方法。在每次調(diào)用remove方法后，都會(huì)將lastReturned置為null。也就是說，如果連續(xù)調(diào)用remove方法，第二次調(diào)用就會(huì)拋出一個(gè)IllegalStateException異常。因此，remove操作必須跟在next或previous操作之后。

現(xiàn)在已經(jīng)介紹了ListIterator接口的基本方法，可以從前后兩個(gè)方向遍歷鏈表中的元素，并可以添加、刪除元素。

記住一點(diǎn)：鏈表的任意位置添加與刪除節(jié)點(diǎn)的操作是ListIterator迭代器提供的，類本身的add方法只能在結(jié)尾添加。

2.4 隨機(jī)訪問

在Java類庫中，還提供了許多理論上存在一定爭議的方法。鏈表不支持快速隨機(jī)訪問。如果要查看鏈表中的第n個(gè)元素，就必須從頭開始，越過n-1個(gè)元素，沒有捷徑可走。鑒于這個(gè)原因，在程序需要采用整數(shù)索引訪問元素時(shí)，一般不選用鏈表。

盡管如此，LinkedList類還提供了一個(gè)用來訪問某個(gè)特定元素的get方法：

LinkedList<String> list=...; String s=list.get(n);當(dāng)然，這個(gè)方法的效率不太高。絕不應(yīng)該使用這種讓人誤解的隨機(jī)訪問方法來遍歷鏈表。下面的代碼效率極低：

for(int i=0;i<list.size();i++) {dosomething with list.get(i); }

每次查找一個(gè)元素都要從頭開始重新搜索。LinkedList對(duì)象根本不做任何緩存位置信息的處理。

其實(shí)，在LinkedList類中，get方法會(huì)判斷當(dāng)前的位置距離頭和尾哪一端更近，然后判斷從左向右遍歷還是從右向左遍歷。

2.5 例子

下面的代碼演示了LinkedList類的基本操作。它簡單的創(chuàng)建兩個(gè)鏈表，將它們合并在一起，然后從第二個(gè)鏈表中每間隔一個(gè)元素刪除一個(gè)元素，最后測(cè)試removeAll方法：

import java.util.*; public class LinkedListTest {public static void main(String[] args) {List<String> a=new LinkedList<>();a.add("A");a.add("C");a.add("E");List<String> b=new LinkedList<>();b.add("B");b.add("D");b.add("F");b.add("G");ListIterator<String> aIter=a.listIterator();Iterator<String> bIter=b.iterator();while(bIter.hasNext()){if(aIter.hasNext())aIter.next();aIter.add(bIter.next());}System.out.println(a);bIter=b.iterator();while(bIter.hasNext()){bIter.next();if(bIter.hasNext()){bIter.next();bIter.remove();}}System.out.println(b);a.removeAll(b);System.out.println(a);} }結(jié)果如下：

3 數(shù)組列表：ArrayList

前面介紹了List接口和實(shí)現(xiàn)了這個(gè)接口的LinkedList類。List接口用于描述一個(gè)有序集合，并且集合中每個(gè)元素的位置十分重要。有兩種訪問元素的協(xié)議：一種是用迭代器，另一種使用get和set方法隨機(jī)訪問每個(gè)元素。后者不適用于鏈表，但對(duì)數(shù)組很有用。集合類庫提供了一個(gè)大家非常熟悉的ArrayList類，這個(gè)類也實(shí)現(xiàn)了List接口。ArrayList類封裝了一個(gè)動(dòng)態(tài)再分配的對(duì)象數(shù)組。

Java集合類庫中還有一個(gè)動(dòng)態(tài)數(shù)組：Vector類。不過這個(gè)類的所有方法是同步的，可以由兩個(gè)線程安全的訪問一個(gè)Vector對(duì)象。但是，如果一個(gè)線程訪問Vector，代碼要在同步上消耗大量的時(shí)間。而ArrayList方法不是同步的，因此，如果不需要同步時(shí)使用ArrayList。

在ArrayList詳解中詳細(xì)介紹了類的實(shí)現(xiàn)及方法的使用。

總結(jié)

以上是生活随笔為你收集整理的Java集合(二)：List列表的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。