序列化的時候,如果把整個數組都序列化的話,是不是就多序列化了 4 個記憶體空間。當存儲的元素數量非常非常多的時候,閑置的空間就非常非常大,序列化耗費的時間就會非常非常多。
于是,ArrayList 做了一個愉快而又聰明的決定,内部提供了兩個私有方法 writeObject 和 readObject 來完成序列化和反序列化。
private void writeObject(java.io.ObjectOutputStream s)
throws java.io.IOException {
// Write out element count, and any hidden stuff
int expectedModCount = modCount;
s.defaultWriteObject();
// Write out size as capacity for behavioral compatibility with clone()
s.writeInt(size);
// Write out all elements in the proper order.
for (int i=0; i<size; i++) {
s.writeObject(elementData[i]);
}
if (modCount != expectedModCount) {
throw new ConcurrentModificationException();
}
}
從 writeObject 方法的源碼中可以看得出,它使用了 ArrayList 的實際大小 size 而不是數組的長度(elementData.length)來作為元素的上限進行序列化。
此處應該有掌聲啊!不是為我,為 Java 源碼的作者們,他們真的是太厲害了,可以用兩個詞來形容他們——殚精竭慮、精益求精。
02、LinkedList 是如何實作的?
![](https://img.laitimes.com/img/__Qf2AjLwojIjJCLyojI0JCLicmbw5SOiJ2YkFGO0kzM3MDM3YWO0ETZ0EWNjR2N1QDNwQ2Nm9CX5d2bs92Yl1iclB3bsVmdlR2LcNWaw9CXt92Yu4GZjlGbh5yYjV3Lc9CX6MHc0RHaiojIsJye.png)
LinkedList 是一個繼承自 AbstractSequentialList 的雙向連結清單,是以它也可以被當作堆棧、隊列或雙端隊列進行操作。
public class LinkedList<E>
extends AbstractSequentialList<E>
implements List<E>, Deque<E>, Cloneable, java.io.Serializable
{
transient int size = 0;
transient Node<E> first;
transient Node<E> last;
}
LinkedList 内部定義了一個 Node 節點,它包含 3 個部分:元素内容 item,前引用 prev 和後引用 next。代碼如下所示:
private static class Node<E> {
E item;
LinkedList.Node<E> next;
LinkedList.Node<E> prev;
Node(LinkedList.Node<E> prev, E element, LinkedList.Node<E> next) {
this.item = element;
this.next = next;
this.prev = prev;
}
}
LinkedList 還實作了 Cloneable 接口,這表明 LinkedList 是支援拷貝的。
LinkedList 還實作了 Serializable 接口,這表明 LinkedList 是支援序列化的。眼睛雪亮的小夥伴可能又注意到了,LinkedList 中的關鍵字段 size、first、last 都使用了 transient 關鍵字修飾,這不又沖突了嗎?到底是想序列化還是不想序列化?
答案是 LinkedList 想按照自己的方式序列化,來看它自己實作的 writeObject() 方法:
private void writeObject(java.io.ObjectOutputStream s)
throws java.io.IOException {
// Write out any hidden serialization magic
s.defaultWriteObject();
// Write out size
s.writeInt(size);
// Write out all elements in the proper order.
for (LinkedList.Node<E> x = first; x != null; x = x.next)
s.writeObject(x.item);
}
發現沒?LinkedList 在序列化的時候隻保留了元素的内容 item,并沒有保留元素的前後引用。這樣就節省了不少記憶體空間,對吧?
那有些小夥伴可能就疑惑了,隻保留元素内容,不保留前後引用,那反序列化的時候怎麼辦?
private void readObject(java.io.ObjectInputStream s)
throws java.io.IOException, ClassNotFoundException {
// Read in any hidden serialization magic
s.defaultReadObject();
// Read in size
int size = s.readInt();
// Read in all elements in the proper order.
for (int i = 0; i < size; i++)
linkLast((E)s.readObject());
}
void linkLast(E e) {
final LinkedList.Node<E> l = last;
final LinkedList.Node<E> newNode = new LinkedList.Node<>(l, e, null);
last = newNode;
if (l == null)
first = newNode;
else
l.next = newNode;
size++;
modCount++;
}
注意 for 循環中的 linkLast() 方法,它可以把連結清單重新連結起來,這樣就恢複了連結清單序列化之前的順序。很妙,對吧?
和 ArrayList 相比,LinkedList 沒有實作 RandomAccess 接口,這是因為 LinkedList 存儲資料的記憶體位址是不連續的,是以不支援随機通路。
03、ArrayList 和 LinkedList 新增元素時究竟誰快?
前面我們已經從多個次元了解了 ArrayList 和 LinkedList 的實作原理和各自的特點。那接下來,我們就來聊聊 ArrayList 和 LinkedList 在新增元素時究竟誰快?
1)ArrayList
ArrayList 新增元素有兩種情況,一種是直接将元素添加到數組末尾,一種是将元素插入到指定位置。
添加到數組末尾的源碼:
public boolean add(E e) {
modCount++;
add(e, elementData, size);
return true;
}
private void add(E e, Object[] elementData, int s) {
if (s == elementData.length)
elementData = grow();
elementData[s] = e;
size = s + 1;
}
很簡單,先判斷是否需要擴容,然後直接通過索引将元素添加到末尾。
插入到指定位置的源碼:
public void add(int index, E element) {
rangeCheckForAdd(index);
modCount++;
final int s;
Object[] elementData;
if ((s = size) == (elementData = this.elementData).length)
elementData = grow();
System.arraycopy(elementData, index,
elementData, index + 1,
s - index);
elementData[index] = element;
size = s + 1;
}
先檢查插入的位置是否在合理的範圍之内,然後判斷是否需要擴容,再把該位置以後的元素複制到新添加元素的位置之後,最後通過索引将元素添加到指定的位置。這種情況是非常傷的,性能會比較差。
2)LinkedList
LinkedList 新增元素也有兩種情況,一種是直接将元素添加到隊尾,一種是将元素插入到指定位置。
添加到隊尾的源碼:
public boolean add(E e) {
linkLast(e);
return true;
}
void linkLast(E e) {
final LinkedList.Node<E> l = last;
final LinkedList.Node<E> newNode = new LinkedList.Node<>(l, e, null);
last = newNode;
if (l == null)
first = newNode;
else
l.next = newNode;
size++;
modCount++;
}
先将隊尾的節點 last 存放到臨時變量 l 中(不是說不建議使用 I 作為變量名嗎?Java 的作者們明知故犯啊),然後生成新的 Node 節點,并賦給 last,如果 l 為 null,說明是第一次添加,是以 first 為新的節點;否則将新的節點賦給之前 last 的 next。
public void add(int index, E element) {
checkPositionIndex(index);
if (index == size)
linkLast(element);
else
linkBefore(element, node(index));
}
LinkedList.Node<E> node(int index) {
// assert isElementIndex(index);
if (index < (size >> 1)) {
LinkedList.Node<E> x = first;
for (int i = 0; i < index; i++)
x = x.next;
return x;
} else {
LinkedList.Node<E> x = last;
for (int i = size - 1; i > index; i--)
x = x.prev;
return x;
}
}
void linkBefore(E e, LinkedList.Node<E> succ) {
// assert succ != null;
final LinkedList.Node<E> pred = succ.prev;
final LinkedList.Node<E> newNode = new LinkedList.Node<>(pred, e, succ);
succ.prev = newNode;
if (pred == null)
first = newNode;
else
pred.next = newNode;
size++;
modCount++;
}
先檢查插入的位置是否在合理的範圍之内,然後判斷插入的位置是否是隊尾,如果是,添加到隊尾;否則執行 linkBefore() 方法。
在執行 linkBefore() 方法之前,會調用 node() 方法查找指定位置上的元素,這一步是需要周遊 LinkedList 的。如果插入的位置靠前前半段,就從隊頭開始往後找;否則從隊尾往前找。也就是說,如果插入的位置越靠近 LinkedList 的中間位置,周遊所花費的時間就越多。
找到指定位置上的元素(succ)之後,就開始執行 linkBefore() 方法了,先将 succ 的前一個節點(prev)存放到臨時變量 pred 中,然後生成新的 Node 節點(newNode),并将 succ 的前一個節點變更為 newNode,如果 pred 為 null,說明插入的是隊頭,是以 first 為新節點;否則将 pred 的後一個節點變更為 newNode。