ArrayList 與 LinkedList 都是List 類型的容器，保存數據的同時也維持著它們插入元素的順序，LinkedList 提供了更多的方法來操作其中的數據，但是這并不意味著要優先使用LinkedList ,因為這兩種容器底層實現的數據結構截然不同。

ArrayList

ArrayList 底層的數據結構是數組，因為數組有下標索引，所以在查詢與設置特定數據的時候會非常快，缺點就是在插入、刪除數據時效率很低(數組在是一塊連續的內存空間，當你想要刪除或者添加元素時都需要移動內存)。

下面就結合底層的源碼進行分析：在查找元素時根據傳入的下標就可以直接返回對應的元素數據，但是在進行元素刪除與添加時會根據下標進行對應的元素拷貝，如果一個集合中有大量數據，想要刪除一個特定位置上的元素，那么這個元素后的所有元素都會進行拷貝，這個效率是相當感人的，在添加元素時還會先對原來的數組長度先進行擴容然后再進行拷貝。

//其底層的數據結構是一個Object 類型的數組transient Object[] elementData; // non-private to simplify nested class access//根據下標返回在數組中對應的數據，在返回數據之前回先調用rangeCheck(); 方法public E get(int index) {rangeCheck(index);return elementData(index); //當傳入的下標小于0 時報的異常會指向這一行代碼}//rangeCheck(); 方法用于對傳入的數組下標進行越界檢查，這里只檢查下標超出數組長度的情況private void rangeCheck(int index) {if (index >= size)throw new IndexOutOfBoundsException(outOfBoundsMsg(index));//當傳入的下標大于數組的長度時報的異常會指向這一行代碼}//修改元素的值public E set(int index, E element) {rangeCheck(index); //對下標范圍進行檢查E oldValue = elementData(index);elementData[index] = element; //改變元素的值return oldValue;}//在指定的位置添加元素public void add(int index, E element) {rangeCheckForAdd(index); //先對下標范圍檢查ensureCapacityInternal(size + 1); //對Object 數組進行擴容，這個擴容步驟分很多步就不在這里貼出來了，感興趣的話可以自己查看源碼System.arraycopy(elementData, index, elementData, index + 1,size - index); //將數組中index 之后的元素向后拷貝elementData[index] = element; //將元素插入在固定的位置上size++;}//刪除元素的方法public E remove(int index) {rangeCheck(index); //先檢查刪除元素的下標modCount++;E oldValue = elementData(index); //獲得指定下標的元素int numMoved = size - index - 1;if (numMoved > 0)System.arraycopy(elementData, index+1, elementData, index,numMoved); //index 之后的元素全部向前拷貝elementData[--size] = null; // clear to let GC do its workreturn oldValue;}

LinkedList

LinkedList 底層是一個Node 類型的雙向鏈表，在當前節點中不僅保存了元素值還保存了上一個元素和下一個元素的地址。

transient Node<E> first;transient Node<E> last; //內部類，保存了當前的元素至值以及上一個元素和下一個元素的地址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 的源碼分析： 我們發現想要獲得元素值會遍歷節點，直到找到對應節點的位置然后返回其中保存的元素值(修改操作類似)。對于刪除和插入的操作只要找到對應的節點然后改變節點的前一個節點和后一個節點的指向就可以完成任務，不存在大量元素的拷貝，所以在對元素進行刪除與插入時要比ArrayList 效率更高。

//獲取指定位置的元素值public E get(int index) {checkElementIndex(index); //對元素索引檢查return node(index).item; //返回對應位置的節點值，下面這個方法是返回值算法的實現}Node<E> node(int index) {// assert isElementIndex(index);if (index < (size >> 1)) { //右移一位相當于 size / 2,避免所有節點掃描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;}// 設置元素值public E set(int index, E element) {checkElementIndex(index); //檢查元素所以Node<E> x = node(index); //返回元素的節點E oldVal = x.item;x.item = element; //設置新的節點值return oldVal;}//在指定的位置添加元素public void add(int index, E element) {checkPositionIndex(index);if (index == size) //如果插入元素的位置等于集合的大小，那么直接在最后插入linkLast(element);elselinkBefore(element, node(index)); //先找到在index 位置上的元素節點，然后進行鏈接，對應的方法如下}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++;}//刪除對應位置上的元素public E remove(int index) {checkElementIndex(index);return unlink(node(index)); //調用unlink() 方法刪除節點}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;}

總結

ArrayList：內部數據結構是數組，查找與修改元素很快，增刪元素速度很慢–>地址空間連續，還有一點要注意的是在刪除元素的時候從后面往前刪除元素要比從前往后刪除效率更高

LinkedList:內部是雙向鏈表形式的數據結構，增刪元素的速度很快，但查找元素速度很慢，由于是雙向鏈表所以在對鏈表中間元素進行操作時效率會很低

PS：在LinkedList 內部，所有的增刪改查操作都會先找到對應的節點，所以在對LinkedList 中的元素進行操作時效率都是相當的。之所以說它查詢速度慢是指與ArrayList 相比時它沒有數組獲取元素容易，刪除元素和添加元素快是因為只要找到對應的節點然后對節點的指向進行操作就可以將數據插入與刪除，在ArrayList 中，會將元素拷貝到新的數組中，拷貝的操作與LinkedList 節點操作相比并不高效。

System.arraycopy() 方法

因為ArrayList 源碼中用到了這個方法，就在這里簡單介紹一下

public static void (Object src, int srcPos, Object dest, int destPos, int length)
src:源數組；
srcPos:源數組要復制的起始位置；
dest:目的數組；
destPos:目的數組放置的起始位置；
length:復制的長度。

舉個例子如下：如果這個方法復制的是數組對象，那么只是復制了對象的引用并不是對對象本身進行復制，所以也被稱為淺復制。

int[] array = {0,1,2,3,4,5,6}; System.arraycopy(array, 0,array,3, 3);System.out.println(Arrays.toString(array)); //復制結果為：[0, 1, 2, 0, 1, 2, 6]

可參考文章： 模擬實現ArrayList與 LinkedList

與50位技術專家面對面20年技術見證，附贈技術全景圖

總結

以上是生活随笔為你收集整理的ArrayList 与 LinkedList 底层实现的全部內容，希望文章能夠幫你解決所遇到的問題。

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