Java集合---List

List接口

List接口，成為有序的Collection也就是序列。該接口可以對清單中的每一個元素的插入位置進行精确的控制，同時使用者可以根據元素的整數索引（在清單中的位置）通路元素，并搜尋清單中的元素。例如List接口定義如下方法，實作元素指定位置的插入和通路。

add(int index, E element)
get(int index)

AbstractList 抽象類

List 接口的骨幹實作，以最大限度地減少實作“随機通路”資料存儲（如數組）支援的該接口所需的工作。

List具體實作類

Vector

類聲明如下

public class Vector<E> extends AbstractList<E>
        implements List<E>, RandomAccess, Cloneable, java.io.Serializable

構造方法如下

Constructor 1
public Vector() {
    this(10);
}

Constructor 2
public Vector(int initialCapacity) {
    this(initialCapacity, 0);
}

Constructor 
public Vector(int initialCapacity, int capacityIncrement) {
    super();
    if (initialCapacity < )
        throw new IllegalArgumentException("Illegal Capacity: "+ initialCapacity);                                             
    this.elementData = new Object[initialCapacity];
    this.capacityIncrement = capacityIncrement;
}

Constructor 4
public Vector(Collection<? extends E> c) {
    elementData = c.toArray();
    elementCount = elementData.length;
    if (elementData.getClass() != Object[].class)
        elementData = Arrays.copyOf(elementData, elementCount, Object[].class);
}

Constructor 1：建立一個容量為 10，增量為 0 的 Vector 容器，容量和增量的概念接下來會介紹。

Constructor 2：建立一個容量為形參 initialCapacity，增量為 0 的 Vector 容器。

Constructor 3：建立一個容量為形參 initialCapacity，增量為 capacityIncrement的Vector 容器。

Constructor 4：建立一個容量為集合 c 長度，增量為 0 的 Vector 容器。

上面四個構造方法中使用到了Vector定義的三個成員變量：

protected Object[] elementData;

Object類型的數組，Vector底層是數組來實作的，所有的元素都在 elementData 數組中存放

protected int elementCount;

elementCount 屬性用來記錄Vector容器中的元素個數，也就是數組 elementData 中元素的個數，而不是 elementData 數組的長度，下面是Vector size（）方法的定義，直接傳回elementCount 的值。

public synchronized int size() {
    return elementCount;
}

protected int capacityIncrement;

capacityIncrement 屬性記錄容器的增量，即容器自動擴充的時候一次性擴充的大小。

接下來看一下 Vector 類元素增加、删除、通路和疊代實作的具體細節

1 增加元素

public synchronized boolean add(E e) {
        modCount++;
        ensureCapacityHelper(elementCount + );
        elementData[elementCount++] = e;
        return true;
    }

1 synchronized:Vector在多線程環境下提供了同步機制。

2 add 方法并沒有進行null判斷，允許null元素。

modCount++：modCount 屬性在 AbstractList 中定義

protected transient int modCount = ;

modCount 是用來記錄容器被結構性修改的次數，所謂結構性修改是對容器進行了元素增加和删除等操作，下面是Vector修改和擷取元素的代碼都沒有進行 modCount++ 的操作。

public synchronized E get(int index) {
        if (index >= elementCount)
            throw new ArrayIndexOutOfBoundsException(index);
        return (E) elementData[index];
}
public synchronized E set(int index, E element) {
        if (index >= elementCount)
            throw new ArrayIndexOutOfBoundsException(index);
        Object oldValue = elementData[index];
        elementData[index] = element;
        return (E)oldValue;
}

那設定這個屬性的作用是什麼呢？是為了在多線程環境下以一種叫做“快速失敗”的方式通知程式疊代周遊容器失敗。下面是調用 Vector 容器的 iterator(）方法傳回的疊代器對象的具體類。

private class Itr implements Iterator<E> {
            int cursor = ;
            int lastRet = -;
            int expectedModCount = modCount;
            public boolean hasNext() {
                    return cursor != size();
            }
            public E next() {
                    checkForComodification();
                try {
                E next = get(cursor);
                lastRet = cursor++;
                return next;
                } catch (IndexOutOfBoundsException e) {
                checkForComodification();
                throw new NoSuchElementException();
                }
            }
            final void checkForComodification() {
                if (modCount != expectedModCount)
                throw new ConcurrentModificationException();
            }
     }

此類通過 expectedModCount 儲存了一個 Vector 結構化修改的次數，而在疊代過程中會不斷的調用 checkForComodification 方法，一旦發現容器被結構化修改就會抛出ConcurrentModificationException 異常。可以聯想，當線程 t1 正在疊代周遊 Vector 容器時，線程 t2 結構性修改了容器，那麼線程 t1 将立刻抛出異常，這也是所謂的“快速失敗”。

接着上面講 Vector add 方法的第二行代碼：

ensureCapacityHelper(elementCount + );

在往容器中添加元素之間需要確定容器有足夠的空間來存儲元素，即 elementData 數組還有空間存儲元素，ensureCapacityHelper 方法代碼如下：

private void ensureCapacityHelper(int minCapacity) {
        int oldCapacity = elementData.length;
        if (minCapacity > oldCapacity) {
            Object[] oldData = elementData;
            int newCapacity = (capacityIncrement > ) ? (oldCapacity + capacityIncrement)
                    : (oldCapacity * );
            if (newCapacity < minCapacity) {
                newCapacity = minCapacity;
            }
            elementData = Arrays.copyOf(elementData, newCapacity);
        }
    }

elementCount + 1 代表容器存放下目前元素需要的最小空間，如果最小空間尚且大于數組的長度，那麼必須進行動态擴容，擴容的方法如上所示。

接着 Vector add 方法的第三行代碼

這個代碼完成了元素的添加。

2 删除元素

public synchronized E remove(int index) {
        modCount++;
        if (index >= elementCount)
            throw new ArrayIndexOutOfBoundsException(index);
        Object oldValue = elementData[index];
        int numMoved = elementCount - index - ;
        if (numMoved > )
            System.arraycopy(elementData, index+, elementData, index,numMoved);
        elementData[--elementCount] = null; 
        return (E)oldValue;
     }

此處關鍵的操作，是 System.arraycopy 方法，此方法是一個 native 方法，主要完成數組元素的移動，即從 index+1 開始，每個元素往前移動一位。

因為index後面的元素都往前移動了一位，是以需要将最後一位制空，elementCount 屬性值減一。

3 通路元素

public synchronized E get(int index) {
        if (index >= elementCount)
            throw new ArrayIndexOutOfBoundsException(index);
        return (E)elementData[index];
    }

代碼簡單易懂，此處不再介紹。

4 疊代元素

Vector 沒有重寫 iterator 方法，直接繼承 AbstractList 類的iterator方法，定義如下：

public Iterator<E> iterator() {
    return new Itr();
 }

内部類 Itr 定義如下所示

private class Itr implements Iterator<E> {

        int cursor = ;
        int lastRet = -;
        int expectedModCount = modCount;
        public boolean hasNext() {
            return cursor != size();
        }
        public E next() {
            checkForComodification();
            try {
                E next = get(cursor);
                lastRet = cursor++;
                return next;
            } catch (IndexOutOfBoundsException e) {
                checkForComodification();
                throw new NoSuchElementException();
            }
        }

        public void remove() {
            if (lastRet == -)
                throw new IllegalStateException();
            checkForComodification();

            try {
                AbstractList.this.remove(lastRet);
                if (lastRet < cursor)
                    cursor--;
                lastRet = -;
                expectedModCount = modCount;
            } catch (IndexOutOfBoundsException e) {
                throw new ConcurrentModificationException();
            }
        }

        final void checkForComodification() {
            if (modCount != expectedModCount)
                throw new ConcurrentModificationException();
        }
    }

Iterator remove 操作不會引起目前線程疊代周遊失敗，因為删除元素之後重新設定了 expectedModCount 的值。

next 和 hasNext 方法簡單易懂。

3 Vector疊代周遊，按照加入元素的順序輸出所有元素。

4 Vector加入元素時并沒有進行排序。

List<Integer> vector = new Vector<Integer>();
        vector.add();
        vector.add();
        vector.add();
        vector.add();
        vector.add();
        for(Integer i: vector){
            System.out.println(i);
        }

是以代碼輸出結果為：

Vector#總結

提供同步機制
底層數組實作
可以加入null元素
元素加入時沒有進行排序
元素可以重複加入

Stack

類聲明如下

Stack通過五個操作對Vector進行擴充，允許将向量視為堆棧

empty() 測試堆棧是否為空
peek() 檢視堆棧頂部的對象，但不從堆棧中移除它
pop() 移除堆棧頂部的對象，并作為此函數的值傳回該對象
push(E item) 把項壓入堆棧頂部
search(Object o) 傳回對象在堆棧中的位置，以 1 為基數

Stack構造函數

public Stack() {
 }

隻有一個空構造函數

因為 Stack 繼承自 Vector ，是以兼備Vector所有的特性，下面我們看一下 Stack 擴充的 5 中基本操作。

1 push(E item) 将元素推入棧頂

public E push(E item) {
    addElement(item);
    return item;
}
 public synchronized void addElement(E obj) {
    modCount++;
    ensureCapacityHelper(elementCount + );
    elementData[elementCount++] = obj;
}

push 方法調用 Vector 中定義的方法将目前元素添加到Statck容器中數組的末尾，也就是棧結構對應的棧頂。

2 peek() 檢視堆棧頂部的對象，但不從堆棧中移除它

public synchronized E peek() {
        int len = size();
        if (len == )
            throw new EmptyStackException();
        return elementAt(len - );
}

public synchronized E elementAt(int index) {
        if (index >= elementCount) {
            throw new ArrayIndexOutOfBoundsException(index + " >= " + elementCount);
        }
        return (E) elementData[index];
    }

peek 方法調用 Vector 中定義的 elementAt 方法返Statck容器中數組最後一個元素，即棧頂元素。

3 pop() 移除堆棧頂部的對象，并作為此函數的值傳回該對象

public synchronized E pop() {
        E obj;
        int len = size();
        obj = peek();
        removeElementAt(len - );
        return obj;
}

pop 方法調用 Vector 方法中定義的 removeElementAt 方法删除并傳回Statck容器中數組的最後一個元素，即棧頂元素。

4 empty() 測試堆棧是否為空

public boolean empty() {
    return size() == ;
}

5 search(Object o) 傳回對象在堆棧中的位置，以 1 為基數

public synchronized int search(Object o) {
        int i = lastIndexOf(o);
        if (i >= ) {
            return size() - i;
        }
        return -;
}

從棧頂處開始檢索，即棧頂元素的傳回 1，次棧頂元素傳回 2 。

Stack<Integer> stack = new Stack<Integer>();
        stack.push();
        stack.push();
        stack.push();
        stack.push();
        stack.push();
        System.out.println(stack.search());
        System.out.println(stack.search());

Stack總結

繼承自 Vector
提供同步機制
擴充了 push、pop、 empty、peek、search 五個方法

ArrayList

類聲明如下

public class ArrayList<E> extends AbstractList<E>
        implements List<E>, RandomAccess, Cloneable, java.io.Serializable

構造方法

Constructor 1
public ArrayList() {
    this(10);
}

Constructor 
public ArrayList(int initialCapacity) {
        super();
        if (initialCapacity < )
            throw new IllegalArgumentException("Illegal Capacity: "
                    + initialCapacity);
        this.elementData = new Object[initialCapacity];
}

Constructor 3
public ArrayList(Collection<? extends E> c) {
        elementData = c.toArray();
        size = elementData.length;
        if (elementData.getClass() != Object[].class)
            elementData = Arrays.copyOf(elementData, size, Object[].class);
}

構造方法與 Vector 差不多，這裡不再贅述。

ArrayList 成員屬性

private transient Object[] elementData;

Object 類型的數組，ArrayList 底層是數組來實作的，所有的元素都在 elementData 數組中存放.

private int size;

size 屬性用來記錄 ArrayList 容器中的元素個數，也就是數組 elementData 中元素的個數，而不是 elementData 數組的長度。

接下來看一下 ArrayList 類元素增加、删除、通路和疊代實作的具體細節

1 增加元素

public boolean add(E e) {
        ensureCapacity(size + ); 
        elementData[size++] = e;
        return true;
}

這跟 Vector 的 add 方法基本上一緻，添加元素之前要確定空間夠用，然後将元素加入容器，size++。

1 no synchronized:ArrayList 不是多線程安全的。

2 add 方法并沒有進行null判斷，允許null元素。

2 删除元素

public E remove(int index) {
        RangeCheck(index);
        modCount++;
        E oldValue = (E) elementData[index];
        int numMoved = size - index - ;
        if (numMoved > )
            System.arraycopy(elementData, index + , elementData, index,
                    numMoved);
        elementData[--size] = null; 
        return oldValue;
}

跟 Vector 中定義的删除方法基本一緻，首先是越界檢查，然後數組元素移位。

3 通路元素

public E get(int index) {
    RangeCheck(index);
    return (E) elementData[index];
}

代碼簡單明了，不再贅述。

4 疊代元素

Arraylist 沒有重寫 iterator 方法，同樣使用 AbstractList 定義的方法傳回容器疊代器，跟上述的 Vector 完全一樣。

ArrayList 總結

不提供同步機制
底層數組實作
可以加入null元素
元素加入時沒有進行排序
元素可以重複加入

LinkedList

LinkedList 與 ArrayList 一樣實作 List 接口，隻是 ArrayList 是 List接口的大小可變數組的實作，LinkedList 是 List 接口連結清單的實作。基于連結清單實作的方式使得LinkedList在插入和删除時更優于ArrayList，而随機通路則比ArrayList遜色些。

AbstractSequentialList提供了 List 接口的骨幹實作，進而最大限度地減少了實作受“連續通路”資料存儲（如連結清單）支援的此接口所需的工作,進而以減少實作List接口的複雜度。

除了實作 List 接口外，LinkedList 類還為在清單的開頭及結尾 get、remove 和 insert 元素提供了統一的命名方法。這些操作允許将連結清單用作堆棧、隊列或雙端隊列。

與棧結構相關的方法

public void push(E e);
public E pop();
public E peek();

LinkedList 實作了 Deque 接口，Deque 接口繼承自 Queue 接口，LinkedList中與單端對列相關的此方法

boolean add(E e);
E poll();
E peek();

LinkedList與雙端隊列相關的方法

雙端隊列：即在隊列兩端都可以 insert 和 remove：insertLast、insertFirst，removeLast、removeFirst 含有棧和隊列的功能，如去掉 insertLast、removeLast，那就跟棧一樣了；如去掉insertLast、removeFirst，那就跟隊列一樣了。

public void addFirst(E e) ;
public void addLast(E e);
public E removeFirst();
public E removeLast();

1 LinkedList 提供了棧、隊列及雙端隊列資料結構的實作。

LinkedList

類聲明

public class LinkedList<E>
    extends AbstractSequentialList<E>
    implements List<E>, Deque<E>, Cloneable, java.io.Serializable

LinedList 構造方法

Constructor1

public LinkedList() {
    header.next = header.previous = header;
}

Constructor2

public LinkedList(Collection<? extends E> c) {
    this();
    addAll(c);
}

在介紹構造方法之前首先看一下 LinkedList 的成員屬性

private transient Entry<E> header = new Entry<E>(null, null, null);
private transient int size = ;

size 屬性記錄 LinkedList 容器的尺寸

header 屬性是一個 LinkedList 内部類 Entry 類型，接下來看一下 Entry 類的定義

private static class Entry<E> {
        E element;
        Entry<E> next;
        Entry<E> previous;
        Entry(E element, Entry<E> next, Entry<E> previous) {
            this.element = element;
            this.next = next;
            this.previous = previous;
        }
}

element 是元素的值

next 是目前元素後繼的引用

previous 是目前元素前驅的引用

接下來繼續探讨 LinkedList 的構造方法

Constructor2 中顯示調用 Constructor1 方法，Constructor1 執行了這樣一條語句

header.next = header.previous = header;

初始化成員屬性 header,為下面添加元素做準備

Java集合---List

接下來看一下 LinkedList 類元素增加、删除、通路和疊代實作的具體細節

1 增加元素

public boolean add(E e) {
    addBefore(e, header);
    return true;
}

private Entry<E> addBefore(E e, Entry<E> entry) {
    Entry<E> newEntry = new Entry<E>(e, entry, entry.previous);
    newEntry.previous.next = newEntry;
    newEntry.next.previous = newEntry;
    size++;
    modCount++;
    return newEntry;
}

Entry<E> newEntry = new Entry<E>(e, entry, entry.previous);

建立一個新的元素節點。

Java集合---List

接下來的幾行代碼完成新元素的添加

newEntry.previous.next = newEntry;
newEntry.next.previous = newEntry;
size++;
modCount++;

為了更清楚的展示，在向 LinkedList 中添加一個元素 B

Java集合---List

2 LinkedList 底層使用循環雙連結清單實作。

3 元素添加時沒有進行排序。

4 元素添加時沒有提供同步機制。

5 沒有限制 null 元素的添加。

2 删除元素

public E remove() {
    return removeFirst();
}
public E removeFirst() {
    return remove(header.next);
}
private E remove(Entry<E> e) {
    if (e == header)
        throw new NoSuchElementException();

    E result = e.element;
    e.previous.next = e.next;
    e.next.previous = e.previous;
    e.next = e.previous = null;
    e.element = null;
    size--;
    modCount++;
    return result;
}

删除操作，簡單明了，隻不過是在循環雙連結清單上進行元素前驅和後繼引用的設定，但要明确一點，header 并不是容器中的有效元素，因為其 element 為 null。它隻是一個輔助元素。

3 通路操作

public E get(int index) {
     return entry(index).element;
}
private Entry<E> entry(int index) {
   if (index <  || index >= size)
        throw new IndexOutOfBoundsException("Index: "+index+ ", Size: "+size);
    Entry<E> e = header;
    if (index < (size >> )) {
        for (int i = ; i <= index; i++)
            e = e.next;
    } else {
        for (int i = size; i > index; i--)
            e = e.previous;
    }
    return e;
}

get 方法調用 entry 方法來定位目标元素在LinkedList中的位置，因為 LinkedList 底層雙循環連結清單實作的，是以可以根據 index 參數的大小從前往後檢索、或者從後往前檢索。

4 疊代操作

LinkedList 沒有重寫 iterator 方法，繼承 AbstractSequentialList 中定義的 iterator 方法，下面看一下 AbstractSequentialList 中的 iterator 方法的定義

public Iterator<E> iterator() {
     return listIterator();
}
public ListIterator<E> listIterator(final int index) {
    if (index< || index>size())
      throw new IndexOutOfBoundsException("Index: "+index);
    return new ListItr(index);
}

iterator 方法調用 listIterator 方法，最後生成一個 ListItr 類型的疊代器，下面是 ListItr 類型的定義

private class ListItr extends Itr implements ListIterator<E> {
        ListItr(int index) {
            cursor = index;
        }

        public boolean hasPrevious() {
            return cursor != ;
        }

        public E previous() {
            checkForComodification();
            try {
                int i = cursor - ;
                E previous = get(i);
                lastRet = cursor = i;
                return previous;
            } catch (IndexOutOfBoundsException e) {
                checkForComodification();
                throw new NoSuchElementException();
            }
        }

        public int nextIndex() {
            return cursor;
        }

        public int previousIndex() {
            return cursor - ;
        }

        public void set(E e) {
            if (lastRet == -)
                throw new IllegalStateException();
            checkForComodification();

            try {
                AbstractList.this.set(lastRet, e);
                expectedModCount = modCount;
            } catch (IndexOutOfBoundsException ex) {
                throw new ConcurrentModificationException();
            }
        }

        public void add(E e) {
            checkForComodification();

            try {
                AbstractList.this.add(cursor++, e);
                lastRet = -;
                expectedModCount = modCount;
            } catch (IndexOutOfBoundsException ex) {
                throw new ConcurrentModificationException();
            }
        }
}

ListItr 擴充了如下方法

public boolean hasPrevious();
public E previous();
public int nextIndex();
public int previousIndex();
public void set(E e);
public void add(E e);

這裡我們不在讨論上述六種方法，隻關心與疊代緊密相關的 hashNext和next方法，但是在 ListItr 類中沒有發現這兩個方法。因為 ListItr 繼承自 Itr（在 AbstractList 中定義）類，是以 hashNext 和 next 方法跟上面講述 Vector 疊代時一緻。

LinkedList 總結

底層是循環雙聯表實作
沒有提供同步機制
允許 null 元素
加入元素時沒有進行排序
直接繼承自 AbstractSequentialList
元素可以重複加入

Java集合---List

Java集合---List

List接口

AbstractList 抽象類

List具體實作類

Vector

Vector#總結

Stack

Stack總結

ArrayList

ArrayList 總結

LinkedList

LinkedList 總結

繼續閱讀

關于Gradle配置的小結

Java小案例——随機數猜測随機數猜測

nginx location中斜線的位置的重要性

27 Best Free Eclipse Plug-ins for Java Developer to be ProductiveCode Quality PluginsText Editor PluginsDependency ManagementVersion Control Integration PluginsFramework Development Continuous Integration Related PluginsOther Utility Plugins

Java String.format方法的簡單使用

neo4j之cypher使用文檔

GitHub連夜封殺！這份阿裡 10W 字内部 Java 字面試手冊到底有多強？

spark/scala關于【資源檔案】加載方法概述外部檔案加載方案測試資源檔案打包入jar包中小結

mybatis_入門程式Mybatis入門

AOP程式設計_Android優雅權限架構(1)概念基礎，2021金三銀四前言正文大綱正文

Effective Java 8:通用程式設計

OOM三種類型

工廠模式-三種類型

【遞歸】高效率求2的n次幂

win10本地scala和spark安裝安裝scala安裝spark

scala (3) Function 和 Method