Java容器解析——ArrayList
Java容器解析——LinkedList
Java容器解析——Hashtable
1 LinkedList類定義
LinkedList 是一個繼承于AbstractSequentialList的雙向鏈表啊犬。其定義如下：
public class LinkedList<E>
extends AbstractSequentialList<E>
implements List<E>, Deque<E>, Cloneable, java.io.Serializable {
由定義可以看出：
LinkedList<E>,支持泛型
實現(xiàn)Deque接口召衔，說明可以當(dāng)做隊列
實現(xiàn)Serializable接口, 可序列化
實現(xiàn)Cloneable接口
2 屬性值
//集合元素數(shù)量
transient int size = 0;
//鏈表頭節(jié)點
transient Node<E> first;
//鏈表尾節(jié)點
transient Node<E> last;
節(jié)點結(jié)構(gòu)定義
private static class Node<E> {
E item;//元素值
Node<E> next;//后置節(jié)點
Node<E> prev;//前置節(jié)點
Node(Node<E> prev, E element, Node<E> next) {
this.item = element;
this.next = next;
this.prev = prev;
}
}
由節(jié)點的結(jié)構(gòu)可以看出翔冀，LinkedList是雙向鏈表結(jié)構(gòu)柠并。
3 構(gòu)造函數(shù)
1 無參數(shù)構(gòu)造函數(shù)
public LinkedList() {
}
2 使用集合創(chuàng)建
public LinkedList(Collection<? extends E> c) {
this();
addAll(c);
}
addAll()方法
public boolean addAll(Collection<? extends E> c) {
//以size為插入位置索引贝奇，插入集合c中所有元素
return addAll(size, c);
}
public boolean addAll(int index, Collection<? extends E> c) {
//檢查索引位置是否合法
checkPositionIndex(index);
//將目標(biāo)集合c轉(zhuǎn)為數(shù)組
Object[] a = c.toArray();
//獲得待添加目標(biāo)數(shù)組的長度
int numNew = a.length;
//若長度為0成玫，無需添加绿渣，直接返回
if (numNew == 0)
return false;
//index節(jié)點的前置節(jié)點宴咧，后置節(jié)點
Node<E> pred, succ;
//在鏈表尾部追加數(shù)據(jù)
if (index == size) {
succ = null;
pred = last;
} else {
//取出index節(jié)點根灯，作為后置節(jié)點
succ = node(index);
//前置節(jié)點是，index節(jié)點的前一個節(jié)點
pred = succ.prev;
}
//變量數(shù)組a掺栅，依次添加節(jié)點
for (Object o : a) {
@SuppressWarnings("unchecked") E e = (E) o;
//以前置節(jié)點pred 和 元素值e烙肺，構(gòu)建new一個新節(jié)點，
Node<E> newNode = new Node<>(pred, e, null);
//如果前置節(jié)點pred是空柿冲，說明是頭結(jié)點
if (pred == null)
first = newNode;
else////前置節(jié)點不為空則將pred的后置節(jié)點設(shè)置為新節(jié)點newNode
pred.next = newNode;
pred = newNode;//將當(dāng)前節(jié)點指針向后移動
}
//遍歷結(jié)束茬高，到達(dá)鏈表尾，設(shè)置尾節(jié)點
if (succ == null) {
last = pred;
} else {
//否則是在隊中插入的節(jié)點 假抄，更新前置節(jié)點 后置節(jié)點
pred.next = succ;
succ.prev = pred;
}
size += numNew;//更新節(jié)點數(shù)量size
modCount++;
return true;
}
4 核心方法
| 方法名 | 含義 | 時間復(fù)雜度 |
|---|---|---|
| get(int index) | 根據(jù)索引獲取元素 | O(n) |
| add(E e) | 添加元素 | O(1) |
| add(int index, E element) | 添加元素到指定位置 | O(n) |
| remove(int index) | 刪除索引為index的元素 | O(n) |
| set(int index, E element) | 設(shè)置索引為index的元素值 | O(n) |
| size() | 返回當(dāng)前容器元素大小 | O(1) |
| isEmpty() | 判斷容器是否為空 | O(1) |
| contains(Object o) | 判斷是否包含某個元素 | O(n) |
| indexOf(Object o) | 獲取某元素在列表中索引 | O(n) |
| clear() | 清空列表 | O(n) |
5 獲取元素get()
//根據(jù)索引index獲取元素
public E get(int index) {
checkElementIndex(index);//判斷是否越界 [0,size)
return node(index).item; //調(diào)用node()方法 取出 Node節(jié)點怎栽，
}
//根據(jù)index 查詢出Node
Node<E> node(int index) {
// assert isElementIndex(index);
// 首先根據(jù)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;
}
}
6 添加元素add
（1）直接添加節(jié)點至末尾
//在尾部插入一個節(jié)點： add
public boolean add(E e) {
linkLast(e);
return true;
}
//生成新節(jié)點 并插入到 鏈表尾部熏瞄， 更新 last/first 節(jié)點。
void linkLast(E e) {
final Node<E> l = last; //記錄原尾部節(jié)點
final Node<E> newNode = new Node<>(l, e, null);//以原尾部節(jié)點為新節(jié)點的前置節(jié)點
last = newNode;//更新尾部節(jié)點
if (l == null)//若原鏈表為空鏈表谬以，需要額外更新頭結(jié)點
first = newNode;
else//否則更新原尾節(jié)點的后置節(jié)點為現(xiàn)在的尾節(jié)點（新節(jié)點）
l.next = newNode;
size++;//修改size
modCount++;//修改modCount
}
（2）在指定下標(biāo)位置插入節(jié)點
//在指定下標(biāo)强饮，index處，插入一個節(jié)點
public void add(int index, E element) {
checkPositionIndex(index);//檢查下標(biāo)是否越界[0,size]
if (index == size)//在尾節(jié)點后插入
linkLast(element);
else//在中間插入
linkBefore(element, node(index));
}
//在succ節(jié)點前为黎，插入一個新節(jié)點e
void linkBefore(E e, Node<E> succ) {
// assert succ != null;
//保存后置節(jié)點的前置節(jié)點
final Node<E> pred = succ.prev;
//以前置和后置節(jié)點和元素值e 構(gòu)建一個新節(jié)點
final Node<E> newNode = new Node<>(pred, e, succ);
//新節(jié)點new是原節(jié)點succ的前置節(jié)點
succ.prev = newNode;
if (pred == null)//如果之前的前置節(jié)點是空邮丰，說明succ是原頭結(jié)點。所以新節(jié)點是現(xiàn)在的頭結(jié)點
first = newNode;
else//否則構(gòu)建前置節(jié)點的后置節(jié)點為new
pred.next = newNode;
size++;//修改數(shù)量
modCount++;//修改modCount
}
7 刪除元素remove
（1）刪除索引為index的元素
//刪：remove目標(biāo)節(jié)點
public E remove(int index) {
//檢查是否越界
checkElementIndex(index);
//調(diào)用unlink刪除節(jié)點
return unlink(node(index));
}
//從鏈表上刪除x節(jié)點
E unlink(Node<E> x) {
// assert x != null;
//當(dāng)前節(jié)點的元素值铭乾，設(shè)置為final剪廉，不可更改
final E element = x.item;
//當(dāng)前節(jié)點的后置節(jié)點
final Node<E> next = x.next;
//當(dāng)前節(jié)點的前置節(jié)點
final Node<E> prev = x.prev;
//如果前置節(jié)點為空(說明當(dāng)前節(jié)點原本是頭結(jié)點)
if (prev == null) {
//則頭結(jié)點為后置節(jié)點
first = next;
} else {
prev.next = next;
x.prev = null; //將當(dāng)前節(jié)點的 前置節(jié)點置空
}
//如果后置節(jié)點為空（說明當(dāng)前節(jié)點原本是尾節(jié)點）
if (next == null) {
last = prev; //則 尾節(jié)點為前置節(jié)點
} else {
next.prev = prev;
x.next = null;//將當(dāng)前節(jié)點x的后置節(jié)點置空
}
x.item = null; //將當(dāng)前元素值置空
size--; //修改數(shù)量
modCount++; //修改modCount
return element; //返回取出的元素值
}
private void checkElementIndex(int index) {
if (!isElementIndex(index))
throw new IndexOutOfBoundsException(outOfBoundsMsg(index));
}
private boolean isElementIndex(int index) {
return index >= 0 && index < size;
}
（2）刪除指定的元素
//因為要考慮 null元素，也是分情況遍歷
public boolean remove(Object o) {
if (o == null) {//如果要刪除的是null節(jié)點(從remove和add 里 可以看出炕檩，允許元素為null)
//遍歷每個節(jié)點 對比
for (Node<E> x = first; x != null; x = x.next) {
if (x.item == null) {
unlink(x);
return true;
}
}
} else {
for (Node<E> x = first; x != null; x = x.next) {
if (o.equals(x.item)) {
unlink(x);
return true;
}
}
}
return false;
}
//將節(jié)點x斗蒋，從鏈表中刪除
E unlink(Node<E> x) {
// assert x != null;
final E element = x.item;//繼續(xù)元素值，供返回
final Node<E> next = x.next;//保存當(dāng)前節(jié)點的后置節(jié)點
final Node<E> prev = x.prev;//前置節(jié)點
if (prev == null) {//前置節(jié)點為null，
first = next;//則首節(jié)點為next
} else {//否則 更新前置節(jié)點的后置節(jié)點
prev.next = next;
x.prev = null;//記得將要刪除節(jié)點的前置節(jié)點置null
}
//如果后置節(jié)點為null泉沾，說明是尾節(jié)點
if (next == null) {
last = prev;
} else {//否則更新 后置節(jié)點的前置節(jié)點
next.prev = prev;
x.next = null;//記得刪除節(jié)點的后置節(jié)點為null
}
//將刪除節(jié)點的元素值置null捞蚂，以便GC
x.item = null;
size--;//修改size
modCount++;//修改modCount
return element;//返回刪除的元素值
}
8 修改元素set
public E set(int index, E element) {
//檢查越界[0,size)
checkElementIndex(index);
//根據(jù)index取出對應(yīng)的Node
Node<E> x = node(index);
//保存舊值 供返回
E oldVal = x.item;
//用新值覆蓋舊值
x.item = element;
//返回舊值
return oldVal;
}
9 小結(jié)
LinkedList 是雙向鏈表，對其大部分操作屬于對雙向鏈表的增刪改查跷究。因此姓迅，對于LinkedList的學(xué)習(xí)主要是掌握數(shù)據(jù)結(jié)構(gòu)鏈表的操作。此外俊马，LinkedList在查找時使用了折半查找的方式队贱，提升了查找效率。
10 對比
（1）ArrayList是實現(xiàn)了基于動態(tài)數(shù)組的數(shù)據(jù)結(jié)構(gòu)潭袱，LinkedList是基于鏈表結(jié)構(gòu)柱嫌。
（2）對于隨機訪問的get和set方法，ArrayList要優(yōu)于LinkedList屯换，因為LinkedList要移動指針编丘。
（3）對于新增和刪除操作add和remove，LinkedList比較占優(yōu)勢彤悔，因為ArrayList要移動數(shù)據(jù)嘉抓。
11 使用場景
（1）對ArrayList和LinkedList而言，在列表末尾增加一個元素所花的開銷都是固定的晕窑。對 ArrayList而言抑片，主要是在內(nèi)部數(shù)組中增加一項，指向所添加的元素杨赤，偶爾可能會導(dǎo)致對數(shù)組重新進(jìn)行分配敞斋；而對LinkedList而言，這個開銷是 統(tǒng)一的疾牲，分配一個內(nèi)部Entry對象植捎。
（2）在ArrayList集合中添加或者刪除一個元素時，當(dāng)前的列表所所有的元素都會被移動阳柔。而LinkedList集合中添加或者刪除一個元素的開銷是固定的焰枢。
（3）LinkedList集合不支持 高效的隨機隨機訪問（RandomAccess），因為可能產(chǎn)生二次項的行為舌剂。
（4）ArrayList的空間浪費主要體現(xiàn)在在list列表的結(jié)尾預(yù)留一定的容量空間济锄，而LinkedList的空間花費則體現(xiàn)在它的每一個元素都需要消耗相當(dāng)?shù)目臻g
