ArrayList
Java的ArrayList是一個動態(tài)擴(kuò)容的數(shù)組弟跑，開發(fā)中最常用的數(shù)據(jù)結(jié)構(gòu)之一；
特點
1.具有數(shù)組的快速隨機(jī)訪問能力防症，根據(jù)索引查找訪問元素只需O(1);
2.ArrayList中的操作不是線程安全的孟辑，多線程請考慮Vector或者CopyOnWriteArrayList.
3.關(guān)于ArrayList重點關(guān)注下新增元素引起的擴(kuò)容或者刪除哎甲、插入元素引發(fā)的數(shù)組元素移位邏輯：
//先看下數(shù)組的末尾追加add函數(shù)如何處理擴(kuò)容：
public boolean add(E e) {
//新增元素首先需要計算當(dāng)前數(shù)組的容量是否夠再塞入一個元素(size為當(dāng)前數(shù)組實際元素個數(shù))
ensureCapacityInternal(size + 1);
elementData[size++] = e; //容量保證之后，直接末尾新增
return true;
}
private static int calculateCapacity(Object[] elementData, int minCapacity) {
if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {
//這里的判斷體現(xiàn)了默認(rèn)構(gòu)造的數(shù)組初始容量為DEFAULT_CAPACITY=10
return Math.max(DEFAULT_CAPACITY, minCapacity);
}
return minCapacity;
}
private void ensureCapacityInternal(int minCapacity) {
ensureExplicitCapacity(calculateCapacity(elementData, minCapacity));
}
private void ensureExplicitCapacity(int minCapacity) {
modCount++;
//數(shù)組沒有足夠的空間饲嗽，需要調(diào)用grow擴(kuò)容
if (minCapacity - elementData.length > 0)
grow(minCapacity);
}
/**
* 擴(kuò)容邏輯是每次增加原有容量的一半即到1.5*oldCapacity炭玫；
* 1.5倍還是不夠則直接擴(kuò)容到申請的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);
}
//最終使用Arrays copyOf函數(shù)貌虾，創(chuàng)建新容量的數(shù)組并且將原有數(shù)組整個copy到新數(shù)組
public static <T,U> T[] copyOf(U[] original, int newLength, Class<? extends T[]> newType) {
@SuppressWarnings("unchecked")
T[] copy = ((Object)newType == (Object)Object[].class)
? (T[]) new Object[newLength]
: (T[]) Array.newInstance(newType.getComponentType(), newLength);
System.arraycopy(original, 0, copy, 0,
Math.min(original.length, newLength));
return copy;
}
//再看下數(shù)組指定位置插入：
public void add(int index, E element) {
rangeCheckForAdd(index);
ensureCapacityInternal(size + 1); // Increments modCount!!
//前面容量保證邏輯跟上面一致
//多一次copy為將index及其后的所有元素础嫡，整體后移到index+1，空出index這個位置給新增元素
System.arraycopy(elementData, index, elementData, index + 1,
size - index);
elementData[index] = element;
size++;
}
//刪除元素對象酝惧，會使用元素的equal方法進(jìn)行比較查找
public boolean remove(Object o) {
if (o == null) {
for (int index = 0; index < size; index++)
if (elementData[index] == null) {
fastRemove(index);
return true;
}
} else {
for (int index = 0; index < size; index++)
if (o.equals(elementData[index])) {
fastRemove(index);
return true;
}
}
return false;
}
ArrayList總結(jié)：
ArrayList默認(rèn)構(gòu)造容量為10，可指定容量構(gòu)造或者通過集合構(gòu)造相應(yīng)容量的數(shù)組伯诬；
新增元素可能引起的擴(kuò)容邏輯：嘗試1.5倍擴(kuò)容晚唇，若是1.5倍依然夠則直接擴(kuò)容到新增元素所需的最小容量，擴(kuò)容引發(fā)創(chuàng)建新的容量大小數(shù)組并且將數(shù)組元素整體copy到新數(shù)組的開銷盗似。
刪除或者指定位置新增：引發(fā)額外的數(shù)組元素整體copy移位開銷哩陕。
刪除元素對象使用equal方法進(jìn)行比較.
LinkedList
LinkedList也是非常常用的數(shù)據(jù)結(jié)構(gòu)，在java的實現(xiàn)是一個雙向的鏈表：
LinkedList結(jié)構(gòu)圖
1.雙向鏈表赫舒，快速增刪悍及，查詢&隨機(jī)訪問效率低
2.線程不安全
3.遍歷操作，推薦使用foreach & 迭代器Iterator遍歷接癌，get(int index)效率低
//從節(jié)點的結(jié)構(gòu)看出來包含next心赶、prev兩個分別指向前一節(jié)點和后一節(jié)點的引用可以看出LinkedList是一個雙向鏈表的實現(xiàn).
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;
}
}
//持有了鏈表的頭結(jié)點、尾結(jié)點方便快速訪問操作鏈表的頭缺猛、尾
transient Node<E> first;
transient Node<E> last;
linkList.addFirst(e);
linkList.addLast(e);
linkList.removeFirst();
linkList.removeLast();
linkList.getLast();
linkList.getFirst();
public void push(E e) {
addFirst(e);
}
public E pop() {
return removeFirst();
}
//看下指定位置插入node的實現(xiàn)：
public void add(int index, E element) {
checkPositionIndex(index);
if (index == size)
linkLast(element);
else
linkBefore(element, node(index));
}
//這個node(index)函數(shù)返回index處的node節(jié)點
Node<E> node(int index) {
//如果index<0.5*size從頭結(jié)點往后查找,否則從尾結(jié)點往前查找
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;
}
}
為何通過get(index)效率低缨叫？
//對于數(shù)組使用這種for + i的遍歷非常常見而且也沒啥毛病，數(shù)組隨機(jī)索引訪問O(1)
for(int i=0; i<length; i++) {
arrayList[i];
}
//若是用于LinkedList荔燎，看看linkedList的get(i)實現(xiàn)就會發(fā)現(xiàn)每次都需要從頭指針或尾指針開始往計算索引值耻姥，list越長效率越低
public E get(int index) {
checkElementIndex(index);
return node(index).item;
}
Node<E> node(int 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;
}
}
foreach在編譯的時候編譯器會自動將對for這個關(guān)鍵字的使用轉(zhuǎn)化為對目標(biāo)的迭代器的使用
三種遍歷方式效率分析：https://www.cnblogs.com/gsm340/p/9243916.html
LinkedList總結(jié)：
LinkedList就是一個線程不安全的雙向鏈表，并且記錄了鏈表的頭和尾有咨，提供了大量的頭和尾的操作方法琐簇。在首位節(jié)點插入、刪除時間復(fù)雜度O(1)座享，指定位置插入或者訪問查找指定元素都需要O(n)
HashMap
算了---> HashMap新起一篇文章來寫吧
參考內(nèi)容
CSDN - 淺談ArrayList動態(tài)擴(kuò)容
Java LinkedList的實現(xiàn)原理圖文詳解
