List吝梅，根據(jù)名字我們知道是有序的元素集合换薄。先貼一張集合的關(guān)系圖。這里我們分析LinkedList與ArrayList椎椰。
Collection結(jié)構(gòu)
LinkedList與ArrayList
它們都實(shí)現(xiàn)了List接口奠旺。但是內(nèi)部實(shí)現(xiàn)上有些區(qū)別蜘澜，我們具體看下。
LinkedList以鏈表的方式實(shí)現(xiàn)
ArrayList內(nèi)部以數(shù)組方式實(shí)現(xiàn)
插入操作
默認(rèn)順序插入
按照默認(rèn)順序插入响疚，兩者耗費(fèi)的時(shí)間都是O(1)鄙信。
// LinkedList add操作
public boolean add(E e) {
linkLast(e);
return true;
}
// 新建一個(gè)節(jié)點(diǎn)。然后讓最后一個(gè)節(jié)點(diǎn)指向新加入的節(jié)點(diǎn)
// 如果最后一個(gè)為空忿晕，那么這是第一個(gè)新插入的節(jié)點(diǎn)
// 否則装诡，節(jié)點(diǎn)按鏈表方式接在后面
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;
// 增加大小，增加修改次數(shù)
size++;
modCount++;
}
// ArrayList插入
public boolean add(E e) {
// 確保數(shù)組的容量足夠践盼。這個(gè)方法感興趣可以看一下鸦采。
ensureCapacityInternal(size + 1); // Increments modCount!!
elementData[size++] = e;
return true;
}
指定index插入元素
ArrayList的最壞情況下性能為O(n)，最好情況下為O（1）
LinkedList在任何情況下都是O(1)
// LinkedList
public void add(int index, E element) {
checkPositionIndex(index);
if (index == size)
linkLast(element);
else
linkBefore(element, node(index));
}
// LinkedList節(jié)點(diǎn)的查找方法
Node<E> node(int index) {
// 不斷的遍歷索引的位置咕幻。
// 如果index 為小于size的一半渔伯，從頭遍歷
// index 大于size的一半，從尾部索引
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;
}
}
// 直接修改要插入
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++;
}
//ArrayList 谅河。
//需要調(diào)用 System.arraycopy 擴(kuò)充數(shù)組咱旱，數(shù)組中的元素都往后挪一個(gè)位置，在底層實(shí)現(xiàn)上應(yīng)該是進(jìn)行了(n-index)次的賦值操作绷耍。
public void add(int index, E element) {
rangeCheckForAdd(index);
ensureCapacityInternal(size + 1); // Increments modCount!!
System.arraycopy(elementData, index, elementData, index + 1,
size - index);
elementData[index] = element;
size++;
}
刪除操作
刪除元素，與插入本質(zhì)上是類似的鲜侥，有興趣可以閱讀JDK內(nèi)部實(shí)現(xiàn)方式褂始。
ArrayList的刪除操作最差情況下性能為O(n)，最好為O(1),刪除最后一個(gè)元素的時(shí)候性能為O(1)
LinkedList刪除任何元素的性能都為O(1)
搜索元素
ArrayList的搜索性能為O(1)
LinkedList的搜索性能差一些描函，最差為O(n/2)
//LinkedList的搜索
public E get(int index) {
checkElementIndex(index);
return node(index).item;
}
Node<E> node(int index) {
// assert isElementIndex(index);
// 需要進(jìn)行鏈表的遍歷
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;
}
}
// ArrayList搜索
public E get(int index) {
rangeCheck(index);
return elementData(index);
}
//直接從數(shù)組的下標(biāo)拿到元素即可崎苗。
E elementData(int index) {
return (E) elementData[index];
}
注意事項(xiàng)
LinkedList與ArrayList的源碼非常容易閱讀，沒什么難度舀寓。這里我們說一下它們的使用事項(xiàng)胆数。
- LinkedList因?yàn)橐瑫r(shí)維護(hù)鄰居節(jié)點(diǎn)的兩個(gè)指針，內(nèi)存消耗大于ArrayList互墓。
- 在頻繁的插入和刪除的時(shí)候必尼，可以考慮使用LinkedList
- 在頻繁的搜索的時(shí)候，考慮使用ArrayList
- 它們都不是非線程安全的。
想要獲取線程安全的List
List list = Collections.synchronizedList(new ArrayList());
...
synchronized(list) {
Iterator i = list.iterator(); // 必須在 synchronized 塊中
while (i.hasNext())
foo(i.next());
}
最后
文中可能有描述不正確的地方判莉，如果有的話歡迎指出豆挽。不過LinkedList與ArrayList是數(shù)據(jù)結(jié)構(gòu)中很基礎(chǔ)的結(jié)構(gòu)，JDK源碼讀起來也很簡單券盅，可以試著讀一下帮哈。
