1 集合特性
對(duì)于集合框架我們的關(guān)注點(diǎn)一般在一下幾點(diǎn)：
- 集合底層實(shí)現(xiàn)的數(shù)據(jù)結(jié)構(gòu)是什么 雙向鏈表
- 集合中元素是否允許為空 是
- 是否允許重復(fù)的數(shù)據(jù) 是
- 是否有序(這里的有序是指讀取數(shù)據(jù)和存放數(shù)據(jù)的順序是否一致) 是
- 是否線程安全。 否
針對(duì)這些問題，我們先來分析集合框架LinkedList
2 LinkedList分析
依賴關(guān)系
LinkedList主要是繼承自AbstractSequentialList抽象類并實(shí)現(xiàn)了List接口、實(shí)現(xiàn)了Cloneable和Serializable接口使得LinkedList具有克隆和序列化的功能、實(shí)現(xiàn)了Deque接口和Queue因此具有隊(duì)列的性質(zhì)（注意對(duì)比ArrayList沒有隨機(jī)訪問哦）。
public class LinkedList<E> extends AbstractSequentialList<E> implements List<E>, Deque<E>, Cloneable, java.io.Serializable
add方法分析，尋找最后節(jié)點(diǎn)，存在插在后面，不存在創(chuàng)建
void linkLast(E e) {
final Node<E> l = last;//最后一個(gè)節(jié)點(diǎn)
final Node<E> newNode = new Node<>(l, e, null);
last = newNode;
if (l == null)
first = newNode;
else
l.next = newNode;
size++;
modCount++;
}
get方法分析
/**
判斷節(jié)點(diǎn)小于一般正序遍歷，大于一般倒序遍歷
**/
Node<E> node(int index) {
// assert isElementIndex(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;
}
}
ps：對(duì)比ArrayList有個(gè)細(xì)節(jié)要注意
ArrayList使用最普通的for循環(huán)遍歷，LinkedList使用foreach循環(huán)比較快~
ArrayList 快在尋址，慢在擴(kuò)容
LinkedList 慢在尋址，插入方便。
