ArrayList和LinkedList都實作了List介面，有以下的不同點：
1、ArrayList是基于索引的資料介面，它的底層是陣列，它可以以O(1)時間復雜度對元素進行隨機訪問，與此對應，LinkedList是以元素串列的形式存盤它的資料，每一個元素都和它的前一個和后一個元素鏈接在一起，在這種情況下，查找某個元素的時間復雜度是O(n)，
2、相對于ArrayList，LinkedList的插入，添加，洗掉操作速度更快，因為當元素被添加到集合任意位置的時候，不需要像陣列那樣重新計算大小或者是更新索引，
3、LinkedList比ArrayList更占記憶體，因為LinkedList為每一個節點存盤了兩個參考，一個指向前一個元素，一個指向下一個元素，
ArrayList擴容：
總的來說就是分兩步：
1、擴容
把原來的陣列復制到另一個記憶體空間更大的陣列中
2、添加元素
把新元素添加到擴容以后的陣列中
無參構造：
public ArrayList() {
this.elementData = https://www.cnblogs.com/taoziBlogs/p/DEFAULTCAPACITY_EMPTY_ELEMENTDATA;
}
帶參構造：
public ArrayList(int initialCapacity) {
if (initialCapacity >0) {
this.elementData =https://www.cnblogs.com/taoziBlogs/p/new Object[initialCapacity];
}else if (initialCapacity ==0) {
this.elementData = EMPTY_ELEMENTDATA;
}else {
throw new IllegalArgumentException("Illegal Capacity: "+
initialCapacity);
}
}
在無參構造中，我們看到了在用無參構造來創建物件的時候其實就是創建了一個空陣列，長度為0
在有參構造中，傳入的引數是正整數就按照傳入的引數來確定創建陣列的大小，否則例外
接下來我們來看擴容，擴容的方法就是 add(E e)
public boolean add(E e) {
ensureCapacityInternal(size + 1); // Increments modCount!!
elementData[size++] = e;
return true;
}
private void ensureCapacityInternal(int minCapacity) {
ensureExplicitCapacity(calculateCapacity(elementData, minCapacity));
}
private static int calculateCapacity(Object[] elementData, int minCapacity) {
if (elementData =https://www.cnblogs.com/taoziBlogs/p/= DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {
return Math.max(DEFAULT_CAPACITY, minCapacity);
}
return 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 = https://www.cnblogs.com/taoziBlogs/p/Arrays.copyOf(elementData, newCapacity);
}
int newCapacity = oldCapacity + (oldCapacity >> 1);
oldCapacity >> 1 右移運算子 原來長度的一半 再加上原長度也就是每次擴容是原來的1.5倍
之前的所有都是確定新陣列的長度，確定之后就是把老陣列copy到新陣列中，這樣陣列的擴容就結束了
以上的一切都是ArrayList擴容的第一步，第二步就沒啥說的了，就是把需要添加的元素添加到陣列的最后一位
轉載請註明出處，本文鏈接：https://www.uj5u.com/houduan/249322.html
標籤：Java
上一篇：PMP知識領域