目錄
基本介紹
有什么不同??
ArrayList的擴(kuò)容機制
ArrayLIst的基本使用
ArrayList和Vector
基本介紹
還記得我們的java集合框架嗎, 我們來復(fù)習(xí)一下, 如圖:
? ? ? ? ?可以看出來 ArrayList和LinkedList 都是具體類, 他們都是接口List的實現(xiàn)類.
但是他們底層的邏輯是不同的, 相信學(xué)過這個的應(yīng)該大概有個映像吧, 如下圖:
????????可以看出來, ArrayList是向內(nèi)存申請一塊連續(xù)的數(shù)組空間進(jìn)行存儲, 在數(shù)組的存儲形式的基礎(chǔ)上進(jìn)行鏈表的增刪改查, 而LinkedList則是每次添加元素的時候就向系統(tǒng)申請一塊內(nèi)存, 不用就直接釋放, 他們雖然在內(nèi)存上不是連續(xù)的, 但是在邏輯上他們是連在一起的.
有什么不同??
- ?底層實現(xiàn)不同, ArrayList是基于動態(tài)數(shù)組的數(shù)據(jù)結(jié)構(gòu), 而LInkedLIst是基于雙向鏈表的數(shù)據(jù)結(jié)構(gòu)
- 隨機訪問的性能不同, Arraylist的隨機訪問性能是由于LinkedList的, 因為ArrayList可以根據(jù)下標(biāo)來直接訪問, 類似于數(shù)組, 時間復(fù)雜度為O(1), 但是LinkedList的隨機訪問時間復(fù)雜度為O(n), 因為他需要遍歷整個鏈表才能找到指定的元素
- 插入和刪除不同, 對于插入和刪除, LInkedList要明顯由于ArrayList, 因為LInkedList的摻入和刪除操作時間復(fù)雜度為O(1), 例如插入, 我們可以直接在鏈表的頭部進(jìn)行插入或者是通過一個元素來記錄最后一個結(jié)點的位置, 然后直接在最后一個結(jié)點進(jìn)行尾插, 刪除是相同的操作, 因此時間復(fù)雜度為O(1), 但是對于ArrayList就不同了, ArrayList的插入和刪除需要移動插入位置的元素的后面的所有元素, 最壞的情況需要移動ArrayList的所有元素, 因此時間復(fù)雜度為O(n)
但是需要注意的是, 其實他們插入的平均時間復(fù)雜度是一樣的, 接下來我們來探討一下, 他們兩個的平均時間復(fù)雜度:
- 對于ArrayList的插入的平均時間復(fù)雜度, 它想要插入一個數(shù)字, 雖然是直接指定插入的地方, 也就是他的一個隨機插入的性質(zhì), 但是它還需要對后面的元素進(jìn)行一個挪動, 運氣不好的話, 就需要挪動整個數(shù)組, 時間復(fù)雜度最壞的情況下是O(n), 最壞的情況下是O(1), 平均下來就是O(n/2), 我們?nèi)サ粝禂?shù), 也就是O(n)
- 對于LinkedList來說, 他進(jìn)行插入, 需要遍歷鏈表,從頭到尾遍歷, 好的情況就是在頭的時候就便利到了, 時間復(fù)雜度為O(1), 壞的情況下需要遍歷完整個鏈表, 時間復(fù)雜度最壞的情況就是O(n),平均下來就是O(n/2) ,去掉系數(shù)就是O(n)
? ? 所以對于我們真是運用鏈表的場景, 沒有說他們兩個哪個時間復(fù)雜度, 或者是性能更好, 只能是在不同的情況下適應(yīng)不同的場景.?
小結(jié):
????????ArrayList 和 LinkedList 都是 List 接口的實現(xiàn)類，但它們的底層實現(xiàn)（結(jié)構(gòu)）不同、隨機訪問的性能和添加/刪除的效率不同。如果是隨機訪問比較多的業(yè)務(wù)場景可以選擇使用 ArrayList，如果添加和刪除比較多的業(yè)務(wù)場景可以選擇使用 LinkedList。
????????ArrayList適用于需要快速隨機訪問元素的場景，因為它的底層是基于數(shù)組實現(xiàn)的，可以通過下標(biāo)直接訪問元素。但是，當(dāng)需要頻繁插入或刪除元素時，由于需要移動元素，效率較低。
????????LinkedList適用于需要頻繁插入或刪除元素的場景，因為它的底層是基于鏈表實現(xiàn)的，插入或刪除元素只需要改變指針指向，效率較高。但是，當(dāng)需要隨機訪問元素時，由于需要遍歷鏈表，效率較低。
????????因此，根據(jù)具體的場景需求，選擇合適的集合類可以提高程序的效率。
ArrayList的擴(kuò)容機制
我們首先創(chuàng)建一個ArrayList如圖:
import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;
public class Test {
public static void main(String[] args) {
List<Integer> arrayList = new ArrayList<>(); // 第0步:創(chuàng)建基于鏈表的List
arrayList.add(1); // 1 添加元素
arrayList.add(2); // 2 添加元素
arrayList.add(3); // 3 添加元素
arrayList.add(4); // 4 添加元素
arrayList.add(5); // 5 添加元素
arrayList.add(6); // 6 添加元素
arrayList.add(7); // 7 添加元素
arrayList.add(8); // 8 添加元素
arrayList.add(9); // 9 添加元素
System.out.println("hello"); // 打印
}
}第0步, 初始化:
ArrayList的構(gòu)造方法如下:
/**
* Constructs an empty list with the specified initial capacity.
*
* @param initialCapacity the initial capacity of the list
* @throws IllegalArgumentException if the specified initial capacity
* is negative
*/
public ArrayList(int initialCapacity) {
if (initialCapacity > 0) {
this.elementData = new Object[initialCapacity];
} else if (initialCapacity == 0) {
this.elementData = EMPTY_ELEMENTDATA;
} else {
throw new IllegalArgumentException("Illegal Capacity: "+
initialCapacity);
}
}
/**
* Constructs an empty list with an initial capacity of ten.
*/
public ArrayList() {
this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA;
}
/**
* Constructs a list containing the elements of the specified
* collection, in the order they are returned by the collection's
* iterator.
*
* @param c the collection whose elements are to be placed into this list
* @throws NullPointerException if the specified collection is null
*/
public ArrayList(Collection<? extends E> c) {
elementData = c.toArray();
if ((size = elementData.length) != 0) {
// c.toArray might (incorrectly) not return Object[] (see 6260652)
if (elementData.getClass() != Object[].class)
elementData = Arrays.copyOf(elementData, size, Object[].class);
} else {
// replace with empty array.
this.elementData = EMPTY_ELEMENTDATA;
}
}
里面有三個重載的構(gòu)造方法, 簡單來說就是:
- 無參構(gòu)造:?Obeject數(shù)組elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA;
- 給定初始容量:?
①當(dāng) 傳入的初始容量initialCapacity > 0為真時，創(chuàng)建一個大小為initialCapacity的空數(shù)組，并將引用賦給elementData；
②當(dāng) 傳入的初始容量initialCapacity = 0為真時，將空數(shù)組EMPTY_ELEMENTDATA賦給elementData；
③當(dāng) 傳入的初始容量initialCapacity < 0為真時，直接拋出IllegalArgumentException異常。
此處我們傳入的initialCapacity為空, 也就是無參構(gòu)造方法, 如下:
transient Object[] elementData;
private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {};
public ArrayList() {
this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA;
}
?????????在構(gòu)造方法中，它將DEFAULTCAPACITY_EMPTY_ELEMENTDATA賦值給elementData，這個DEFAULTCAPACITY_EMPTY_ELEMENTDATA是一個空的Object數(shù)組，而elementData就是ArrayList實際存儲數(shù)據(jù)的容器。
?第1步, 添加元素1:
觸發(fā):
public boolean add(E e) {
ensureCapacityInternal(size + 1); // Increments modCount!!
elementData[size++] = e;
return true;
}ensureCapacityInternal為確認(rèn)初始化容量:
進(jìn)入ensureCapacityInternal:
private void ensureCapacityInternal(int minCapacity) {
ensureExplicitCapacity(calculateCapacity(elementData, minCapacity));
}隨后進(jìn)入calculateCapacity計算最低所需容量:
private static int calculateCapacity(Object[] elementData, int minCapacity) {
if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {
return Math.max(DEFAULT_CAPACITY, minCapacity);
}
return minCapacity;
}????????此處的minCapacity為 size + 1, 翻譯過來也就是最低所需的容量, 研究發(fā)現(xiàn), 如果是空數(shù)組(剛開始使用無參構(gòu)造方法的時候)就返回DEFAULT_CAPACITY, 值為10.
? ? ? ? 當(dāng)elementData != DEFAULTCAPACITY_EMPTY_ELEMENTDATA 的時候, 直接返回minCapacity.
????????隨后進(jìn)入ensureExplicitCapacity(int minCapacity)方法:
private void ensureExplicitCapacity(int minCapacity) {
modCount++;
// overflow-conscious code
if (minCapacity - elementData.length > 0)
grow(minCapacity);
}modCount++，這是用來記錄數(shù)組被修改次數(shù)的變量，我們先不管它.?minCapacity為計算出來的最小所需容量, elementData.length為當(dāng)前容量,如果最小所需容量大于當(dāng)前容量, 就需要擴(kuò)容, 然后進(jìn)入grow方法:
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);
}????????老的容量為當(dāng)前容量,新的容量為老的容量的1.5倍,如果新的容量–最小所需容量<О那么新的容量就等于最小所需容量,如果新的容量-當(dāng)前數(shù)組最大的容量限制>0,那么就進(jìn)入hugeCapacity方法,然后使用copyOf方法進(jìn)行數(shù)據(jù)遷移.將老的數(shù)據(jù)遷移到新的容量的數(shù)組中
總結(jié)一下:
? ? ? ? 我們使用無參構(gòu)造方法的時候, 就會創(chuàng)建一個底層為空的數(shù)組的鏈表, 此時size 為0, 然后向里面添加元素的時候, 此時的minCapacity為 size + 1 = 1, 在calculateCapacity方法中返回了DEFAULT_CAPACITY(10), 然后進(jìn)入ensureExplicitCapacity(10), 此時的minCapacity = 10 > 當(dāng)前容量 = 0, 所以進(jìn)行初始擴(kuò)容(elementData = Arrays.copyOf(elementData, newCapacity)), 將容量擴(kuò)充到10, 也就是elementData/length == 10, 隨后的插入, 只要沒有超過10, 那就可以直接插入, 如果容量滿了, 那么就進(jìn)行1.5倍擴(kuò)容.
ArrayLIst的基本使用
import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;
public class Test {
public static void main(String[] args) {
ArrayList<Integer> arrayList = new ArrayList<>(); // 第0步:創(chuàng)建基于鏈表的List
// add(int x) 直接向元素末尾位置添加x
arrayList.add(1);
// get(int index) 方法, 返回下標(biāo)為index的元素
int a = arrayList.get(0);
System.out.println(a);
// add(int index, int element); 向指定位置插入元素
arrayList.add(1,3);
// size(); 獲取當(dāng)前元素的個數(shù)
int size = arrayList.size();
// remove(int index); 刪除下標(biāo)為index 的元素
arrayList.remove(0);
// 判斷arrList是否為空, 如果為空就返回true, 否則返回false;
arrayList.isEmpty();
// set(int index, int element); 將index 下標(biāo)的元素設(shè)置為 element
arrayList.set(0,5);
}
}LInkedList與之類似
ArrayList和Vector
? ? ? ? ArrayList和Vector都實現(xiàn)了List接口. 代碼演示如圖:
import java.util.ArrayList;
import java.util.Vector;
public class Main {
public static void main(String[] args) {
ArrayList<String> arrayList = new ArrayList<>();
Vector<String> vector = new Vector<>();
// 添加元素
arrayList.add("Java");
arrayList.add("Python");
arrayList.add("C++");
vector.add("Java");
vector.add("Python");
vector.add("C++");
// 獲取元素
System.out.println(arrayList.get(0));
System.out.println(vector.get(0));
// 刪除元素
arrayList.remove(0);
vector.remove(0);
// 獲取元素個數(shù)
System.out.println(arrayList.size());
System.out.println(vector.size());
}
}
但它們有以下區(qū)別：
- 線程安全性：Vector 是線程安全的，而 ArrayList 不是。所以在多線程環(huán)境下，應(yīng)該使用 Vector。
- 性能：由于 Vector 是線程安全的，所以它的性能通常比 ArrayList 差。在單線程環(huán)境下，ArrayList 比 Vector 快。
- 初始容量增長方式：當(dāng)容量不足時，ArrayList 默認(rèn)會增加 50% 的容量，而 Vector 會將容量翻倍。這意味著在添加元素時，ArrayList 需要更頻繁地進(jìn)行擴(kuò)容操作，而 Vector 則更適合于存儲大量數(shù)據(jù)。
Vector的grow方法
????????綜上所述，如果不需要考慮線程安全問題，并且需要高效的存取操作，則 ArrayList 是更好的選擇；如果需要考慮線程安全以及更好的數(shù)據(jù)存儲能力，則應(yīng)該選擇 Vector。文章來源：http://www.zghlxwxcb.cn/news/detail-664068.html
文章來源地址http://www.zghlxwxcb.cn/news/detail-664068.html
到了這里，關(guān)于java面試基礎(chǔ) -- ArrayList 和 LinkedList有什么區(qū)別, ArrayList和Vector呢?的文章就介紹完了。如果您還想了解更多內(nèi)容，請在右上角搜索TOY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！
