學習List接口實現類 ArrayList? Vector? LinkedList

List接口的實現類中最經常使用最重要的就是這三個：ArrayList、Vector、LinkedList。

JDK中這三個類的定義：

1、ArrayList<E>：

public class ArrayList<E> extends AbstractList<E>
??????? implements List<E>, RandomAccess, Cloneable, java.io.Serializable
{
??? private static final long serialVersionUID = 8683452581122892189L;

??? /**
???? * The array buffer into which the elements of the ArrayList are stored.
???? * The capacity of the ArrayList is the length of this array buffer.
???? */
??? private transient Object[] elementData;

??? /**
???? * The size of the ArrayList (the number of elements it contains).
???? *
???? * @serial
???? */
??? private int size;

2、 Vector<E>：
public class Vector<E>extends AbstractList<E>
??? implements List<E>, RandomAccess, Cloneable, java.io.Serializable
{
??? /**
???? * The array buffer into which the components of the vector are
???? * stored. The capacity of the vector is the length of this array buffer,
???? * and is at least large enough to contain all the vector's elements.
???? *
???? * <p>Any array elements following the last element in the Vector are null.
???? *
???? * @serial
???? */
??? protected Object[] elementData;

3、LinkedList<E>：

public class LinkedList<E>extends AbstractSequentialList<E>
??? implements List<E>, Deque<E>, Cloneable, java.io.Serializable
{?? // 在序列化這個對象的時候這個變量不會被這樣序列化
??? transient int size = 0;

??? /**
???? * Pointer to first node.
???? * Invariant: (first == null && last == null) ||
???? *??????????? (first.prev == null && first.item != null)
???? */
??? transient Node<E> first;

??? /**
???? * Pointer to last node.
???? * Invariant: (first == null && last == null) ||
???? *??????????? (last.next == null && last.item != null)
???? */
??? transient Node<E> last;

4、從這三個類定義就能夠看出一些信息：

（1）、三個都直接實現了AbstractList這個抽象類

（2）、ArrayList和Vector都實現了RandomAccess接口。而LinkedList沒有。這是什么意思呢？?????????????

?在JDK 中，RandomAccess接口是一個空接口，所以它沒有實際意義。就是一個標記，

?標記這個類支持高速隨機訪問，所以，arrayList和 vector是支持隨機訪問的，可是LinkedList不支持持?????????

（3）、serializbale接口表明他們都支持序列化。

5、以下具體說說List的這三個實現：

? （1）、 查看實現源代碼會發現這三個里面，ArrayList和Vector使用了數組的實現，相當于封裝了對數組的操作。這也正是他們可以支持高速隨機訪問的原因，多說一句，JDK中全部基于數組實現的數據結構都可以支持高速隨機訪問。

?? ArrayList和Vector的實現上差點兒都使用了同樣的算法，他們的主要差別就是ArrayList沒有對不論什么一個方法做同步處理，所以不是線程安全的；而Vector中大部分方法都做了線程同步所以是線程安全的。

? （2）、LinkedList使用的是雙向循環鏈表的數據結構。因為是基于鏈表的。所以無法法實現隨機訪問的，僅僅能順序訪問，這也正是它沒有實現RandomAccess接口的原因。

? （3）、因為ArrayList、Vector和LinkedList所採用的數據結構不同。注定他們適用的是全然不同的場景。

通過閱讀這幾個類的源代碼，我們能夠看到他們實現的不同。

ArrayList和Vector基本一樣，我們就用ArrayList和LinkedList做對照。

在末尾添加一個元素

6、ArrayList中的add方法實現例如以下：

????? /**
???? * Appends the specified element to the end of this list.
???? *將元素加入到list的最后
???? * @param e element to be appended to this list
???? * @return <tt>true</tt> (as specified by {@link Collection#add})
???? */
??? public boolean add(E e) {
??????? // 推斷容量

??????? ensureCapacityInternal(size + 1);? // Increments modCount!!
??????? elementData[size++] = e;
??????? return true;
??? }

這種方法做兩件事情，首先確保數組空間足夠大。然后在數組末尾添加元素而且通過后++使得完畢size+1

從這個代碼能夠看出，假設數組空間足夠大，那么僅僅是數組的add操作就是O(1)的性能，很高效。

7、在看看ensureCapacityInternal這種方法的實現：

?private void ensureCapacityInternal(int minCapacity) {
??????? modCount++;
??????? // overflow-conscious code。假設空間不夠則擴容也就是又一次創建一個Object[]對象
??????? if (minCapacity - elementData.length > 0)
??????????? grow(minCapacity);
??? }

8、grow(int minCapacity)方法創建數組并將原來的數據復制到新數組中

? /**
???? * Increases the capacity to ensure that it can hold at least the
???? * number of elements specified by the minimum capacity argument.
???? *
???? * @param minCapacity the desired minimum capacity
???? */
??? private void grow(int minCapacity) {
??????? // overflow-conscious code
??????? int oldCapacity = elementData.length;
??????? // 使用移位運算，提高效率

?????? int newCapacity = oldCapacity + (oldCapacity >> 1);
??????? if (newCapacity - minCapacity < 0)
??????????? newCapacity = minCapacity;
??????? if (newCapacity - MAX_ARRAY_SIZE > 0)
??????????? newCapacity = hugeCapacity(minCapacity);
??????? // minCapacity is usually close to size, so this is a win:
??????? elementData = Arrays.copyOf(elementData, newCapacity);
??? }

能夠看出。假設數組空間不夠，那么這種方法就會做數組擴容和數組復制操作，看上面，JDK利用移位運算符進行擴容計算，>>1右移一位表示除2，所以newCapacity就是擴容為原來的1.5倍。

9、這里的代碼都是JDK1.7中的實現，JDK1.7對1.6的非常多代碼做了優化。比方上面這段擴容代碼，在JDK1.6中上面的是直接除2，顯然。移位運算要更高效。

10、在看看LinkedList中的add方法：

（1）、add（E e）:

/**
???? * Appends the specified element to the end of this list.
???? *
???? * <p>This method is equivalent to {@link #addLast}.
???? *
???? * @param e element to be appended to this list
???? * @return {@code true} (as specified by {@link Collection#add})
???? */
??? public boolean add(E e) {
??????? linkLast(e);
??????? return true;
??? }
(2)、linkLast(E e) ：

??? /**
???? * 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;
??????? else
??????????? l.next = newNode;
??????? size++;
??????? modCount++;
??? }

（3）、內部類：
? 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;
??????? }
??? }

從這段add代碼能夠看出。LinkedList因為使用了鏈表。所以不須要進行擴容，直接把元素加到鏈表最后，把新元素的前驅指向之前的last元素。并把last元素指向新元素就能夠了。

這也是一個O(1)的性能。

在任何位置插入元素

11、ArrayList中的實現例如以下：

（1）、 add(int index, E element)

public void add(int index, E element) {
??????? rangeCheckForAdd(index);
???????? // 推斷容量
??????? ensureCapacityInternal(size + 1);? // Increments modCount!!
??????? System.arraycopy(elementData, index, elementData, index + 1,
???????????????????????? size - index);
??????? elementData[index] = element;
??????? size++;
??? }

（2）、ensureCapacityInternal(int minCapacity)

private void ensureCapacityInternal(int minCapacity) {
??????? modCount++;
??????? // overflow-conscious code，假設數組長度不夠則進行擴容
??????? if (minCapacity - elementData.length > 0)
??????????? grow(minCapacity);
??? }

（3）、grow(int minCapacity)

/**
???? * Increases the capacity to ensure that it can hold at least the
???? * number of elements specified by the minimum capacity argument.
???? *
???? * @param minCapacity the desired minimum capacity
???? */
??? private void grow(int minCapacity) {
??????? // overflow-conscious code
??????? int oldCapacity = elementData.length;
??????? int newCapacity = oldCapacity + (oldCapacity >> 1);
??????? if (newCapacity - minCapacity < 0)
??????????? newCapacity = minCapacity;
??????? if (newCapacity - MAX_ARRAY_SIZE > 0)
??????????? newCapacity = hugeCapacity(minCapacity);
??????? // minCapacity is usually close to size, so this is a win:
??????? elementData = Arrays.copyOf(elementData, newCapacity);
??? }

這段代碼，首先先檢查數組容量，容量不夠先擴容。然后把index之后的數組往后挪一個。最后在index位置放上新元素。因為數組是一塊連續內存空間，所以在任何位置插入。都會導致這個其后數組后挪一位的情況。須要做一次數組復制操作，非常明顯，假設有大量的隨機插入，那么這個數組復制操作開銷會非常大。并且插入的越靠前，數組復制開銷越大。

12、LinkedList中的實現：

（1）、add(int index, E element)

?/**
???? * Inserts the specified element at the specified position in this list.
???? * Shifts the element currently at that position (if any) and any
???? * subsequent elements to the right (adds one to their indices).
???? *
???? * @param index index at which the specified element is to be inserted
???? * @param element element to be inserted
???? * @throws IndexOutOfBoundsException {@inheritDoc}
???? */
??? public void add(int index, E element) {
??????? checkPositionIndex(index);

??????? if (index == size)
??????????? linkLast(element);
??????? else
??????????? linkBefore(element, node(index));
??? }

（2）、linkBefore（E e, Node<E> succ）
?/**
???? * 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;
??????? else
??????????? pred.next = newNode;
??????? size++;
??????? modCount++;
??? }

（3）、 Node<E> node(int index)

/**
???? * Returns the (non-null) Node at the specified element index.
???? */
??? Node<E> node(int index) {
??????? // assert isElementIndex(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;
??????? }
??? }

這段代碼。取到原先index處節點的前驅。變成新節點的前驅，同一時候把原先index變成新節點的后驅，這樣就完畢了新節點的插入。

這個就是鏈表的優勢。不存在數據復制操作，性能和在最后插入是一樣的。

小結：

??? 從上面的源代碼剖析能夠看出這三種List實現的一些典型適用場景，假設常常對數組做隨機插入操作，特別是插入的比較靠前，那么LinkedList的性能優勢就很明顯。而假設都僅僅是末尾插入，則ArrayList更占領優勢。假設須要線程安全。則使用Vector或者創建線程安全的ArrayList。

在使用基于數組實現的ArrayList 和Vector 時我們要指定初始容量。由于我們在源代碼中也看到了，在加入時首先要進行容量的推斷，假設容量不夠則要創建新數組。還要將原來數組中的數據拷貝到新數組中。這個過程會減低效率而且會浪費資源。

?

轉載于:https://www.cnblogs.com/mfrbuaa/p/5157768.html

總結

以上是生活随笔為你收集整理的List接口实现类－ArrayList、Vector、LinkedList集合深入学习以及源代码解析的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。