List接口及其實現類 · 小機的專屬后端開發筆記本

## List接口繼承Collection接口的一個接口，就是傳統的線性表的結構，實現該接口的結構存儲的數據不唯一（值不唯一，類型是唯一的），同時數據按照添加的順序進行排列。其主要擴展Collection的方法有： ~~~ ?public interface List<E> extends Collection<E> { ? ? ?// 元素進行排序 ? ? ?default void sort(Comparator<? super E> c) { ? ? ? ? ?Object[] a = this.toArray(); ? ? ? ? ?Arrays.sort(a, (Comparator) c); ? ? ? ? ?ListIterator<E> i = this.listIterator(); ? ? ? ? ?for (Object e : a) { ? ? ? ? ? ? ?i.next(); ? ? ? ? ? ? ?i.set((E) e); ? ? ? ? } ? ? } ? ? ? ? ? ?// 獲取某個下標的元素 ? ? ?E get(int index); ? ? ? ? ? ?// 修改某個下標的元素 ? ? ?E set(int index, E element); ? ? ? ? // 判斷元素是否存在 ? ? ?// 從頭開始，并返回第一相同元素的索引 ? ? ?int indexOf(Object o); ? ? ?// 從后面開始，并返回第一個相同元素的索引 ? ? ?int lastIndexOf(Object o); ? ? ? ? ? ?// 快速創建List對象的靜態方法 ? ? ?static <E> List<E> of() { ? ? ? ? ?return (List<E>) ImmutableCollections.ListN.EMPTY_LIST; ? ? } ? ? ?static <E> List<E> of(E e1) { ? ? ? ? ?return new ImmutableCollections.List12<>(e1); ? ? } ? ? ?// 還有好幾個重載的方法 ? ? ? ?} ~~~   ***** 下面是List的常見實現類： ### Vector 底層用數組存儲，里面的方法都是線程安全的，現版本基本別拋棄了，不建議使用。 ~~~ ?public class Vector<E> extends AbstractList<E> ? ? ?implements List<E>, RandomAccess, Cloneable, java.io.Serializable { ? ? ?// 1. 重要的屬性 ? ? ?// 用數組結構來保存數據 ? ? ?protected Object[] elementData; ? ? ?// 數組中元素的個數 ? ? ?protected int elementCount; ? ? ?// 擴容時數組增長的大小，如果該值小于等于0時會默認增長一倍 ? ? ?protected int capacityIncrement; ? ? ? ? ? ?//----------------------------------------------------- ? ? ?// 2.構造函數 ? ? ?public Vector() { ? ? ? ? ?// 無參構造默認數組初始化大小為10 ? ? ? ? ?this(10); ? ? } ? ? ?public Vector(int initialCapacity) { ? ? ? ? ?// 默認擴容因子為0，因此在擴容的時候會增長數組長度的一倍 ? ? ? ? ?this(initialCapacity, 0); ? ? } ? ? ?public Vector(int initialCapacity, int capacityIncrement) { ? ? ? ? ?// 最終都會調用這個 ? ? ? ? ?super(); ? ? ? ? ?if (initialCapacity < 0) ? ? ? ? ? ? ?throw new IllegalArgumentException("Illegal Capacity: "+ ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? initialCapacity); ? ? ? ? ?this.elementData = new Object[initialCapacity]; ? ? ? ? ?this.capacityIncrement = capacityIncrement; ? ? } ? ? ? ? ? ?// ------------------------------------------- ? ? ?// 3. 常見操作 ? ? ?// 添加元素，修改到底層數組結構內容的有如下兩個方法： ? ? ?// 私有的，供其他add方法調用，往s的位置添加 ? ? ?private void add(E e, Object[] elementData, int s) { ? ? ? ? ?if (s == elementData.length) ? ? ? ? ? ? ?// 超出底層數組大小需要擴容 ? ? ? ? ? ? ?elementData = grow(); ? ? ? ? ?elementData[s] = e; ? ? ? ? ?elementCount = s + 1; ? ? } ? ? ?// 插入操作，往index位置插入 ? ? ?public synchronized void insertElementAt(E obj, int index) { ? ? ? ? ?if (index > elementCount) { ? ? ? ? ? ? ?// 插入范圍在0~elementCount ? ? ? ? ? ? ?throw new ArrayIndexOutOfBoundsException(index ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? + " > " + elementCount); ? ? ? ? } ? ? ? ? ?// AbstractList中聲明的用來記錄結構被修改的次數，可以用于增強for循環中刪除數組元素報錯的情況。 ? ? ? ? ?modCount++; ? ? ? ? ?final int s = elementCount; ? ? ? ? ?Object[] elementData = this.elementData; ? ? ? ? ?if (s == elementData.length) ? ? ? ? ? ? ?elementData = grow(); ? ? ? ? ?// 將index開始的元素移動到index+1后，使用native方法，性能更高 ? ? ? ? ?System.arraycopy(elementData, index, ? ? ? ? ? ? ? ? ? ? ? ? ? elementData, index + 1, ? ? ? ? ? ? ? ? ? ? ? ? ? s - index); ? ? ? ? ?elementData[index] = obj; ? ? ? ? ?elementCount = s + 1; ? ? } ? ? ? ? ? ?// 獲取元素 ? ? ?public synchronized E get(int index) { ? ? ? ? ?if (index >= elementCount) ? ? ? ? ? ? ?throw new ArrayIndexOutOfBoundsException(index); ?? ? ? ? ? ?return elementData(index); ? ? } ? ? ?E elementData(int index) { ? ? ? ? ?return (E) elementData[index]; ? ? } ? ? ? ? ? ?// 移除元素 ? ? ?public synchronized E remove(int index) { ? ? ? ? ?modCount++; ? ? ? ? ?if (index >= elementCount) ? ? ? ? ? ? ?throw new ArrayIndexOutOfBoundsException(index); ? ? ? ? ?E oldValue = elementData(index); ?? ? // 要移動元素的數量，如果是index為最后一個元素則不用移除操作 ? ? ? ? ?int numMoved = elementCount - index - 1; ? ? ? ? ?if (numMoved > 0) ? ? ? ? ? ? ?// 將index+1的位置往前移動即可刪除 ? ? ? ? ? ? ?System.arraycopy(elementData, index+1, elementData, index, ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? numMoved); ? ? ? ? ?elementData[--elementCount] = null; // Let gc do its work ?? ? ? ? ? ?return oldValue; ? ? } ? ? ? ? ? ?// 移除所有元素 ? ? ?public void clear() { ? ? ? ? ?removeAllElements(); ? ? } ? ? ?public synchronized void removeAllElements() { ? ? ? ? ?final Object[] es = elementData; ? ? ? ? ?for (int to = elementCount, i = elementCount = 0; i < to; i++) ? ? ? ? ? ? ?es[i] = null; ? ? ? ? ?modCount++; ? ? } ? ? ? ? // -------------------------------------- ? ? ?// 擴容操作 ? ? ?private Object[] grow() { ? ? ? // 至少擴容大于1個元素 ? ? ? ? ?return grow(elementCount + 1); ? ? } ? ? ?private Object[] grow(int minCapacity) { ? ? ? ? ?int oldCapacity = elementData.length; ? ? ? ? ?// 獲取新的數組長度，當擴容因子為0的時候擴展為原來的1倍大小 ? ? ? ? ?int newCapacity = ArraysSupport.newLength(oldCapacity, ? ? ? ? ? ? ?minCapacity - oldCapacity, capacityIncrement > 0 ? capacityIncrement : oldCapacity); ? ? ? ? ?return elementData = Arrays.copyOf(elementData, newCapacity); ? ? } ?} ~~~   ***** ### ArrayList 底層用數組存儲，與Vector相比，ArrayList的操作不是線程安全的，其他基本與Vector相同。 ~~~ ?public class ArrayList<E> extends AbstractList<E> ? ? ? ? ?implements List<E>, RandomAccess, Cloneable, java.io.Serializable ?{ ?? ? ? ?/** ? ? ? * 默認初始化數組元素的大小 ? ? ? */ ? ? ?private static final int DEFAULT_CAPACITY = 10; ?? ? ? ?/** ? ? ? * 創建沒有元素的ArrayList的話所有ArrayList共享這個對象，節約空間 ? ? ? */ ? ? ?private static final Object[] EMPTY_ELEMENTDATA = {}; ?? ? ? ?/** ? * 沒有指定初始化容量時使用，可以用于標識在添加第一個元素的時候需要擴容的大小 ? ? ? */ ? ? ?private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {}; ?? ? ? ?/** ? ? ? * 底層數組結構，通過上面兩個全局靜態的常量可以發現，當初始化容量為0或者不指定的時候這是一個延遲創建的對象，知道真正添加元素的時候才創建 ? ? ? */ ? ? ?transient Object[] elementData; ?? ? ? ?/** ? ? ? * 元素個數 ? ? ? */ ? ? ?private int size; ? ? ? ? ? ?// 構造方法 ? ? ?public ArrayList(int initialCapacity) { ? ? ? ? ?if (initialCapacity > 0) { ? ? ? ? ? ? ?this.elementData = new Object[initialCapacity]; ? ? ? ? } else if (initialCapacity == 0) { ? ? ? ? ? ? ?// 容量為0的時候不創建對象 ? ? ? ? ? ? ?this.elementData = EMPTY_ELEMENTDATA; ? ? ? ? } else { ? ? ? ? ? ? ?throw new IllegalArgumentException("Illegal Capacity: "+ ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? initialCapacity); ? ? ? ? } ? ? } ?? ? ? ?/** ? ? ? * 不指定初始化容量的時候在第一次添加元素時會初始化10個元素大小的數組 ? ? ? */ ? ? ?public ArrayList() { ? ? ? ? ?this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA; ? ? } ? ? ? ? ? ?/** 其他操作和vector相比差不多，主要是擴容機制不太一樣，ArrayList沒有擴容因子，因此在一般情況都是擴容當前長度的1/2大小的； ? ? ?有個特殊的情況就是如果當初始化容量為0的時候第一次添加元素的時候只會擴容一個元素 ? ? ?*/ ? ? ?private Object[] grow(int minCapacity) { ? ? ? ? ?int oldCapacity = elementData.length; ? ? ? ? ?if (oldCapacity > 0 || elementData != DEFAULTCAPACITY_EMPTY_ELEMENTDATA) { ? ? ? ? ? ? ?int newCapacity = ArraysSupport.newLength(oldCapacity, ? ? ? ? ? ? ? ? ?minCapacity - oldCapacity, oldCapacity >> 1);// 右移 ? ? ? ? ? ? ?return elementData = Arrays.copyOf(elementData, newCapacity); ? ? ? ? } else { ? ? ? ? ? ? ?return elementData = new Object[Math.max(DEFAULT_CAPACITY, minCapacity)]; ? ? ? ? } ? ? } ?} ~~~ ArrayList的擴容機制有點特殊的點在于當沒有指定初始容量或者初始容量為0的時候在第一次添加數據的時候就會進入擴容邏輯，是延遲創建對象的： 1. 初始容量為0時第一次添加元素創建1個長度的底層數組。 2. 沒有指定初始容量時第一次添加元素創建默認長度為10的底層數組。 3. 初始化容量指定為0時，第一次添加元素的數組長度會擴容為1。 Vector和ArrayList的異同： 1. 正常情況下底層數組初始大小都為10。 2. Vector可以指定初始的擴容因子，并且在沒有指定的情況下默認擴容一倍大小；而ArrayList不能指定擴容因子的大小，正常情況下每次擴容原來的1/2。 3. Vector的操作都是同步的，使用synchronized關鍵字進行修飾，而ArrayList的操作并不是同步的。 4. ArrayList在初始化容量為0或者沒有指定初始化容量的時候做了一些優化，可以實現延遲創建對象的效果。   ***** ### LinkedList 底層用雙向鏈表存儲數據 ~~~ ?public class LinkedList<E> ? ? ?extends AbstractSequentialList<E> ? ? ?implements List<E>, Deque<E>, Cloneable, java.io.Serializable ?{ ? ? ?// 元素數量 ? ? ?transient int size = 0; ? // 指向頭節點 ? ? ?transient Node<E> first; ? ? ?// 指向尾節點 ? ? ?transient Node<E> last; ? ? ? ? ? ?// 空構造 ? ? ?public LinkedList() { ? ? } ? ? ? ? ? ?// Node結構如下 ? ? ?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; ? ? ? ? } ? ? } ? ? ? ? ? ?// ------------------------------------------ ? ? ?// 常見操作 ? ? ?// 1. 添加節點 ? ? ?public void addFirst(E e) { ? ? ? ? ?// 頭插 ? ? ? ? ?linkFirst(e); ? ? } ? ? ?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; ? ? ? ? ?else ? ? ? ? ? ? ?f.prev = newNode; ? ? ? ? ?size++; ? ? ? ? ?modCount++; ? ? } ? ? ? ? ? ?public void addLast(E e) { ? ? ? ? ?// 尾插 ? ? ? ? ?linkLast(e); ? ? } ? ? ?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; ? ? ? ? ?else ? ? ? ? ? ? ?l.next = newNode; ? ? ? ? ?size++; ? ? ? ? ?modCount++; ? ? } ? ? ? ? ? ?public boolean add(E e) { ? ? ? ? ?// add默認使用尾插 ? ? ? ? ?linkLast(e); ? ? ? ? ?return true; ? ? } ? ? ? ? ? ? ? ? ?// 查詢操作 ? ? ?Node<E> node(int index) { ? ? ? ? ?// 前一半位置從頭開始查， ? ? ? ? ?if (index < (size >> 1)) { ? ? ? ? ? ? ?Node<E> x = first; ? ? ? ? ? ? ?for (int i = 0; i < index; i++) ? ? ? ? ? ? ? ? ?x = x.next; ? ? ? ? ? ? ?return x; ? ? ? ? } else { ? ? ? ? ? ? ?// 后一半位置從尾開始查 ? ? ? ? ? ? ?Node<E> x = last; ? ? ? ? ? ? ?for (int i = size - 1; i > index; i--) ? ? ? ? ? ? ? ? ?x = x.prev; ? ? ? ? ? ? ?return x; ? ? ? ? } ? ? } ? ? ? ? ? ?// 算了...其他就需要再看吧，下面這些都是隊列的相關操作，注意其實現了Dequeu ? ? ?public E peek() {} // 獲取第一個元素 ? ? ?public E poll() {} // 刪除第一個元素并返回 ? ? ?public E remove() {} // 移除第一個元素 ? ? ?public void push(E e) {} ?// 插入第一個元素的位置 ? ? ?public E pop() {} // 彈出第一個元素 ?} ~~~ 從源代碼可以看出LinkedList是一個雙端鏈表，不僅可以作為鏈表使用，還可以作為隊列使用。   參考： JDK1.8源碼