嗯 今天看下 LinkedList结笨，這個(gè) 最后會(huì)總結(jié)寫 ArrayList 的區(qū)別吧
image
-
先看下構(gòu)造函數(shù)
public LinkedList() { } public LinkedList(Collection<? extends E> c) { this(); addAll(c); }
// 咳咳 怎么說呢 沒想到你是這樣的構(gòu)造函數(shù) 什么都不干
在看LinkedList 的增刪改查之前 我們得有一個(gè)認(rèn)知 就是LinkedList 的 數(shù)據(jù)結(jié)構(gòu)是 鏈表（從名字就看出來了）闯传，他的每個(gè) 節(jié)點(diǎn) 都是存在一個(gè) 內(nèi)部類中
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;
}
}
Node 節(jié)點(diǎn) 可以看出 LinkedList 是 一個(gè)雙向鏈表 存了他自己 和 next 和 prev
接下去我們就可以 真正開始看 增刪改查了
老規(guī)矩看下 add
- 增 add() 果港，addAll()
public boolean add(E e) {
linkLast(e);
return true;
}
void linkLast(E e) {
final Node<E> l = last;
// 構(gòu)建 node 節(jié)點(diǎn)
final Node<E> newNode = new Node<>(l, e, null);
//將最新的add 放到 最后
last = newNode;
// 如果尾節(jié)點(diǎn)為空 新加入的變成 頭結(jié)點(diǎn)
if (l == null)
first = newNode;
else// 否則 之前的last 的 next 連接到新加入的節(jié)點(diǎn)
l.next = newNode;
size++;// 數(shù)組size 變大
modCount++; // 增加修改次數(shù)
}
- 刪 remove
根據(jù)對(duì)象
public boolean remove(Object o) {
if (o == null) {
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;
}
根據(jù) 對(duì)象刪除 比較簡答 直接去 equals()
根據(jù) 下 標(biāo)刪除
public E remove(int index) {
// 判斷是否越界
checkElementIndex(index);
return unlink(node(index));
}
// 這段代碼用到了 二分法查找 出node 節(jié)點(diǎn)
Node<E> node(int index) {
// assert isElementIndex(index);
// 有是size>>1 這個(gè)意思就是 size/2 （ >> 效率高）
// index list的左半部分的時(shí)候
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;
}
}
// unlink 就是清楚所有 有關(guān)節(jié)點(diǎn) 的鏈接然后 刪除連接 節(jié)點(diǎn)前后 的 next 和prev 在相互連接
E unlink(Node<E> x) {
// assert x != null;
final E element = x.item;
final Node<E> next = x.next;
final Node<E> prev = x.prev;
// 如果當(dāng)前節(jié)點(diǎn)的 prev 為空 則當(dāng)前節(jié)點(diǎn)的next 變成頭節(jié)點(diǎn)
if (prev == null) {
first = next;
} else {//否則 prev的 next 連接 當(dāng)前節(jié)點(diǎn)的next
prev.next = next;
x.prev = null;
}
if (next == null) { //如果next 則 prev 變成last
last = prev;
} else { // 否則 next prev 連接 當(dāng)前節(jié)點(diǎn)的prev
next.prev = prev;
x.next = null;
}
x.item = null; // 當(dāng)前節(jié)點(diǎn) 全部連接置空 （提醒jvm GC ）
size--; // 減少 數(shù)據(jù)大小
modCount++; //增加修改次數(shù)
return element; // 彈出 當(dāng)前節(jié)點(diǎn)的值
}
- 改 set
public E set(int index, E element) {
checkElementIndex(index);
// 查處
Node<E> x = node(index);
//
E oldVal = x.item;
// 修改
x.item = element;
//返回
return oldVal;
}
查 get
public E get(int index) {
checkElementIndex(index);
return node(index).item;
}
嗯 看起來都很簡單的樣子 從源碼來說 讓我看看其他的擴(kuò)展
這得從昨天 貼的 最后一段代碼 說起 ArrayList 和 LinkedList遍歷的時(shí)候
從今天可以看出來 LinkedList get 是 二分法查找 而 ArrayList 的get 是 直接數(shù)組的下標(biāo)取出來 當(dāng)然是 ArrayList 遍歷快
我們在比較下 remove
回憶一下 ArrayList 增 是 調(diào)用底層本地 native 方法 整個(gè)數(shù)組 拷貝 移動(dòng)的數(shù)組位置 之后 數(shù)組向前移動(dòng)一位
但是LinkedList 增 移動(dòng)的時(shí)候 就很簡單了 unlink 改變下 鏈表 移動(dòng)元素 前后的 prev 和next 就好了 理論上來說 是Linked remove 快點(diǎn)
實(shí)驗(yàn)下：
static final int N=50000;
static long timeListByPrev(List list){
long start=System.currentTimeMillis();
Object o = new Object();
for(int i=0;i<N;i++)
list.add(0, o);
return System.currentTimeMillis()-start;
}
static long timeListByLast(List list){
long start=System.currentTimeMillis();
Object o = new Object();
for(int i=0;i<N;i++)
list.add(i);
return System.currentTimeMillis()-start;
}
public static void main(String[] args) {
System.out.println("前置插入 ArrayList耗時(shí)："+timeListByPrev(new ArrayList()));
System.out.println("前置插入 LinkedList耗時(shí)："+timeListByPrev(new LinkedList()));
System.out.println("后置插入 ArrayList耗時(shí)："+timeListByLast(new ArrayList()));
System.out.println("后置插入 LinkedList耗時(shí)："+timeListByLast(new LinkedList()));
}
out:
前置插入 ArrayList耗時(shí)：288
前置插入 LinkedList耗時(shí)：4
后置插入 ArrayList耗時(shí)：4
后置插入 LinkedList耗時(shí)：3
可以看出 差距很大 四舍五入 差100倍 （本機(jī)測試 不代表任何基準(zhǔn)）
