ArrayList和LinkedList的區別,包括原始碼分析
其實也不像大家說的那回事,主要還是根據資料量和操作有關係!
我們先從add() 方法比較
ArrayList
public boolean add(E e) { ensureCapacityInternal(size + 1);// Increments modCount!! elementData[size++] = e; return true; } //指定下標新增元素 public void add(int index, E element) { if (index > size || index < 0) throw new IndexOutOfBoundsException(outOfBoundsMsg(index)); ensureCapacityInternal(size + 1);// Increments modCount!! System.arraycopy(elementData, index, elementData, index + 1, size - index); elementData[index] = element; size++; } private void ensureCapacityInternal(int minCapacity) { if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) { minCapacity = Math.max(DEFAULT_CAPACITY, minCapacity); } ensureExplicitCapacity(minCapacity); } private void ensureExplicitCapacity(int minCapacity) { modCount++; // overflow-conscious code /* * 判斷是否擴容陣列 */ if (minCapacity - elementData.length > 0) //擴容陣列 grow(minCapacity); } 中間省略了一些方法 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); } 當ArrayList去add資料的時候 elementData[size++] = e; 先去把元素新增進去 ,因為容量肯定是夠用的 oldCapacity + (oldCapacity >> 1) 這裡面則是用到了位運算進行擴容陣列 elementData = Arrays.copyOf(elementData, newCapacity);
LikedList
public boolean add(E e) { linkLast(e); return true; } 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 void add(int index, E element) { checkPositionIndex(index); if (index == size) linkLast(element); else linkBefore(element, node(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; else pred.next = newNode; size++; modCount++; }
對於add(int index,Element element)這個方法在中間新增資料
因為ArrayList去新增資料 會移動陣列或者擴容陣列!內部實現還是根據邏輯去擴容陣列,是同陣列具有下標的。
而LikedList在新增資料的時候只是new 一個Note物件並重新修改上一節點或下一個節點。達到目的
在記憶體方面ArrayList應該是佔的塊記憶體
我這面做的一個測試,如果add(0,element)的時候
getTime = System.currentTimeMillis(); for(int i = 0; i < 900;i++){ arrayList.add(0,i); } Log.e("time", "array" + (System.currentTimeMillis() - getTime)); getTime = System.currentTimeMillis(); for(int i = 0; i < 900;i++){ linkedList.add(0,i); } Log.e("time", "linked" + (System.currentTimeMillis() - getTime)); 小資料的時候偶爾集合會較快,偶爾連結串列快,當資料量大的時候會更加明顯集合大於連結串列的新增時間。
我這面做的一個測試,如果add(size,element)的時候
小資料的時候偶爾集合會較快,大多數還是連結串列快,當資料量大的時候會更加明顯集合大於連結串列的新增時間。
我這面做的一個測試,如果add(2,element)的時候 ,也就是Index的時候 小資料的時候偶爾集合會較快,大多數還是連結串列快,大資料的話還是連結串列快的
remove對比
ArrayList
public E remove(int index) { if (index >= size) throw new IndexOutOfBoundsException(outOfBoundsMsg(index)); modCount++; E oldValue = (E) elementData[index]; int numMoved = size - index - 1; if (numMoved > 0) System.arraycopy(elementData, index+1, elementData, index, numMoved); elementData[--size] = null; // clear to let GC do its work return oldValue; } 通過下標index 執行這段程式碼 System.arraycopy(elementData, index+1, elementData, index, numMoved); 這面我舉個例子說明下 因為原碼裡面都是elementData,也就是一個數組, {0,1,2,3,4} 如果當remove的index為1的時候 走完System.arraycopy()這個方法陣列將會發生改變 {0,2,3,4,4} 然後 elementData[--size] = null; size減減 保證arrayList.size()方法的準確拿取ArrayList的size大小 並把陣列的最後一個數據設為null {0,2,3,4,null} 可見移除了下標為1的資料 作為 public static void arraycopy( Object src,//源陣列 int srcPos,//源陣列的起始位置 Object dest, //目標陣列 int destPos, //目標陣列的起始位置 int length//複製長度 ) 這個方法 當remove的時候內部實現會複製陣列index下標越小複製的陣列量越大,陣列移動也就越多 耗時越大! 這面是這麼想的 但是當ArrayList add(int index)集合的時候,卻是index越小時間越短 和上面的分析完全相反! 這面我有點蒙,希望看到文章的評論解釋下~
LikedList
public E remove(int index) { checkElementIndex(index); return unlink(node(index)); } checkElementIndex(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; } 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; } 先解釋第一個方法,Node<E> node(int index)通過此方法其實也就是和二分法差不多 通過遍歷集合拿到此下標下的Note物件 然後在通過 E unlink(Node<E> x) 這一方法 重新關聯 prev 和 next 的Note物件 並把當前的Note物件 和當前Note物件的prev和next設定 null
所以相對於remove這一方法的總結 LikedList是相對快於ArrayList的
而對於get(int index)這個方法 可想而知肯定是ArrayList比較快的,因為內部實現是陣列是有下標的,而 LikedList 是通過和二分法差不多的查詢Note物件。
最後總結下 :
add(0,element)
add(2,element)
add(size,element) ,
小資料確實ArrayList和 LikedList難以分辯誰快,因為不是確定的
但是當資料大的話還是LikedList快於ArrayList的
remove(int index),LikedList快於ArrayList
get(int index),ArrayList快於LikedList
但是對於 public static void arraycopy(
Object src,//源陣列
int srcPos,//源陣列的起始位置
Object dest, //目標陣列
int destPos, //目標陣列的起始位置
int length//複製長度
)
這個方法還是存在困惑,對於ArrayList的add(index ,element)到底是index越大越費時還是index越小費時!