前言
在上篇文章中我們對(duì)ArrayList對(duì)了詳細(xì)的分析，今天我們來說一說LinkedList飘痛。他們之間有什么區(qū)別呢？最大的區(qū)別就是底層數(shù)據(jù)結(jié)構(gòu)的實(shí)現(xiàn)不一樣，ArrayList是數(shù)組實(shí)現(xiàn)的（具體看上一篇文章）程奠，LinedList是鏈表實(shí)現(xiàn)的。至于其他的一些區(qū)別祭钉，可以說大部分都是由于本質(zhì)不同衍生出來的不同應(yīng)用瞄沙。
LinkedList
鏈表
在分析LinedList之前先對(duì)鏈表做一個(gè)簡(jiǎn)單的介紹，畢竟鏈表不像數(shù)組一樣使用的多慌核，所以很多人不熟悉也在所難免距境。
鏈表是一種基本的線性數(shù)據(jù)結(jié)構(gòu)，其和數(shù)組同為線性垮卓，但是數(shù)組是內(nèi)存的物理存儲(chǔ)上呈線性垫桂，邏輯上也是線性；而鏈表只是在邏輯上呈線性粟按。在鏈表的每一個(gè)存儲(chǔ)單元中不僅存儲(chǔ)有當(dāng)前的元素诬滩，還有下一個(gè)存儲(chǔ)單元的地址，這樣的可以通過地址將所有的存儲(chǔ)單元連接在一起灭将。
每次查找的時(shí)候疼鸟，通過第一個(gè)存儲(chǔ)單元就可以順藤摸瓜的找到需要的元素。執(zhí)行刪除操作只需要斷開相關(guān)元素的指向就可以了庙曙。示意圖如下：
當(dāng)然了在空镜？LinkedList中使用的并不是最基本的單向鏈表，而是雙向鏈表捌朴。
在LinedList中存在一個(gè)基本存儲(chǔ)單元吴攒，是LinkedList的一個(gè)內(nèi)部類，節(jié)點(diǎn)元素存在兩個(gè)屬性男旗，分別保存前一個(gè)節(jié)點(diǎn)和后一個(gè)節(jié)點(diǎn)的引用舶斧。
//靜態(tài)內(nèi)部類
private static class Node<E> {
//存儲(chǔ)元素的屬性
E item;
//前后節(jié)點(diǎn)引用
Node<E> next;
Node<E> prev;
Node(Node<E> prev, E element, Node<E> next) {
this.item = element;
this.next = next;
this.prev = prev;
}
}
定義
public class LinkedList<E>
extends AbstractSequentialList<E>
implements List<E>, Deque<E>, Cloneable, java.io.Serializable
在定義上和ArrayList大差不差，但是需要注意的是察皇，LinkedList實(shí)現(xiàn)了Deque（間接實(shí)現(xiàn)了Qeque接口）茴厉，Deque是一個(gè)雙向?qū)α校瑸長(zhǎng)inedList提供了從對(duì)列兩端訪問元素的方法什荣。
初始化
在分析ArrayList的時(shí)候我們知道ArrayList使用無參構(gòu)造方法時(shí)的初始化長(zhǎng)度是10矾缓，并且所有無參構(gòu)造出來的集合都會(huì)指向同一個(gè)對(duì)象數(shù)組（靜態(tài)常量，位于方法區(qū)）稻爬，那么LinkedList的初始化是怎樣的呢嗜闻？
打開無參構(gòu)造方法
public LinkedList() {
}
什么都沒有，那么只能夠去看屬性了桅锄。
//初始化長(zhǎng)度為0
transient int size = 0;
//有前后節(jié)點(diǎn)
transient Node<E> first;
transient Node<E> last;
圖示初始化
LinkedList<String> list = new LinkedList<String>();
String s = "sss";
list.add(s);
方法
add(E e)
public boolean add(E e) {
linkLast(e);
return true;
}
從方法中我們知道在調(diào)用添加方法之后琉雳，并不是立馬添加的样眠，而是調(diào)用了linkLast方法，見名知意翠肘，新元素的添加位置是集合最后檐束。
void linkLast(E e) {
// 將最后一個(gè)元素賦值（引用傳遞）給節(jié)點(diǎn)l final修飾符 修飾的屬性賦值之后不能被改變
final Node<E> l = last;
// 調(diào)用節(jié)點(diǎn)的有參構(gòu)造方法創(chuàng)建新節(jié)點(diǎn) 保存添加的元素
final Node<E> newNode = new Node<>(l, e, null);
//此時(shí)新節(jié)點(diǎn)是最后一位元素 將新節(jié)點(diǎn)賦值給last
last = newNode;
//如果l是null 意味著這是第一次添加元素 那么將first賦值為新節(jié)點(diǎn) 這個(gè)list只有一個(gè)元素 存儲(chǔ)元素 開始元素和最后元素均是同一個(gè)元素
if (l == null)
first = newNode;
else
//如果不是第一次添加，將新節(jié)點(diǎn)賦值給l（添加前的最后一個(gè)元素）的next
l.next = newNode;
//長(zhǎng)度+1
size++;
//修改次數(shù)+1
modCount++;
}
從以上代碼中我們可以看到其在添加元素的時(shí)候并不依賴下標(biāo)束倍。
而其中的處理是被丧，通過一個(gè)last（Node對(duì)象）保存最后一個(gè)節(jié)點(diǎn)的信息（實(shí)際上就是最后一個(gè)節(jié)點(diǎn)），每次通過不斷的變化最后一個(gè)元素實(shí)現(xiàn)元素的添加绪妹。（想要充分理解此處甥桂，需要理解java值傳遞和引用傳遞的區(qū)別和本質(zhì)）。
add(int index, E element)
添加到指定的位置
public void add(int index, E element) {
//下標(biāo)越界檢查
checkPositionIndex(index);
//如果是向最后添加 直接調(diào)用linkLast
if (index == size)
linkLast(element);
//反之 調(diào)用linkBefore
else
linkBefore(element, node(index));
}
//在指定元素之前插入元素
void linkBefore(E e, Node<E> succ) {
// assert succ != null; 假設(shè)斷言 succ不為null
//定義一個(gè)節(jié)點(diǎn)元素保存succ的prev引用 也就是它的前一節(jié)點(diǎn)信息
final Node<E> pred = succ.prev;
//創(chuàng)建新節(jié)點(diǎn) 節(jié)點(diǎn)元素為要插入的元素e prev引用就是pred 也就是插入之前succ的前一個(gè)元素 next是succ
final Node<E> newNode = new Node<>(pred, e, succ);
//此時(shí)succ的上一個(gè)節(jié)點(diǎn)是插入的新節(jié)點(diǎn) 因此修改節(jié)點(diǎn)指向
succ.prev = newNode;
// 如果pred是null 表明這是第一個(gè)元素
if (pred == null)
//成員屬性first指向新節(jié)點(diǎn)
first = newNode;
//反之
else
//節(jié)點(diǎn)前元素的next屬性指向新節(jié)點(diǎn)
pred.next = newNode;
//長(zhǎng)度+1
size++;
modCount++;
}
節(jié)點(diǎn)元素插入圖示
在上面的代碼中我們應(yīng)該注意到了邮旷，LinkedList在插入元素的時(shí)候也要進(jìn)行一定的驗(yàn)證黄选，也就是下標(biāo)越界驗(yàn)證，下面我們看一下具體的實(shí)現(xiàn)廊移。
private void checkPositionIndex(int index) {
if (!isPositionIndex(index))
throw new IndexOutOfBoundsException(outOfBoundsMsg(index));
}
//如果輸入的index在范圍之內(nèi)返回ture
private boolean isPositionIndex(int index) {
return index >= 0 && index <= size;
}
通過對(duì)兩個(gè)添加方法的分析糕簿，我們可以很明顯的感受到LinkedList添加元素的效率，不需要擴(kuò)容狡孔，不需要復(fù)制數(shù)組懂诗。
get
public E get(int index) {
//檢查下標(biāo)元素是否存在 實(shí)際上就是檢查下標(biāo)是否越界
checkElementIndex(index);
//如果沒有越界就返回對(duì)應(yīng)下標(biāo)節(jié)點(diǎn)的item 也就是對(duì)應(yīng)的元素
return node(index).item;
}
//下標(biāo)越界檢查 如果越界就拋異常
private void checkElementIndex(int index) {
if (!isElementIndex(index))
throw new IndexOutOfBoundsException(outOfBoundsMsg(index));
}
private boolean isElementIndex(int index) {
return index >= 0 && index < size;
}
//該方法是用來返回指定下標(biāo)的非空節(jié)點(diǎn)
Node<E> node(int index) {
//假設(shè)下標(biāo)未越界 實(shí)際上也沒有越界 畢竟在此之前執(zhí)行了下標(biāo)越界檢查
// assert isElementIndex(index);
//如果index小于size的二分之一 從前開始查找（向后查找） 反之向前查找
if (index < (size >> 1)) {//左移 效率高 值得學(xué)習(xí)
Node<E> x = first;
//遍歷
for (int i = 0; i < index; i++)
//每一個(gè)節(jié)點(diǎn)的next都是他的后一個(gè)節(jié)點(diǎn)引用 遍歷的同時(shí)x會(huì)不斷的被賦值為節(jié)點(diǎn)的下一個(gè)元素 遍歷到index是拿到的就是index對(duì)應(yīng)節(jié)點(diǎn)的元素
x = x.next;
return x;
} else {
Node<E> x = last;
for (int i = size - 1; i > index; i--)
x = x.prev;
return x;
}
}
在這段代碼中充分體現(xiàn)了雙向鏈表的優(yōu)越性，可以從前也可以從后開始遍歷苗膝，通過對(duì)index范圍的判斷能夠顯著的提高效率殃恒。但是在遍歷的時(shí)候也可以很明顯的看到LinkedList get方法獲取元素的低效率，時(shí)間復(fù)雜度O(n)辱揭。
remove(int index)
所謂刪除節(jié)點(diǎn) 就是把節(jié)點(diǎn)的前后引用置為null离唐，并且保證沒有任何其他節(jié)點(diǎn)指向被刪除節(jié)點(diǎn)。
public E remove(int index) {
//下標(biāo)越界檢查
checkElementIndex(index);
//此處的返回值實(shí)際上是執(zhí)行了兩個(gè)方法
//node獲取制定下標(biāo)非空節(jié)點(diǎn)
//unlink 斷開指定節(jié)點(diǎn)的聯(lián)系
return unlink(node(index));
}
E unlink(Node<E> x) {
//假設(shè)x不是null
// assert x != null;
//定義一個(gè)變量element接受x節(jié)點(diǎn)中的元素 最后會(huì)最后返回值返回
final E element = x.item;
//定義連個(gè)節(jié)點(diǎn)分別獲得x節(jié)點(diǎn)的前后節(jié)點(diǎn)引用
final Node<E> next = x.next;
final Node<E> prev = x.prev;
//如果節(jié)點(diǎn)前引用為null 說明這是第一個(gè)節(jié)點(diǎn)
if (prev == null) {
//x是第一個(gè)節(jié)點(diǎn) 即將被刪除 那么first需要被重新賦值
first = next;
} else {
//如果不是x不是第一個(gè)節(jié)點(diǎn) 將prev（x的前一個(gè)節(jié)點(diǎn)）的next指向x的后一個(gè)節(jié)點(diǎn)（繞過x）
prev.next = next;
//x的前引用賦值null
x.prev = null;
}
//如果節(jié)點(diǎn)后引用為null 說明這是最后一個(gè)節(jié)點(diǎn) 一系列類似前引用的處理方式 不再贅述
if (next == null) {
last = prev;
} else {
next.prev = prev;
x.next = null;
}
//將x節(jié)點(diǎn)中的元素賦值null
x.item = null;
size--;
modCount++;
return element;
}
說明
- prev问窃，item亥鬓，next均置為null 是為了讓虛擬機(jī)回收
- 我們可以看到LinkedList刪除元素的效率也不錯(cuò)
LinkedList總結(jié)
- 查詢速度不行，每次查找都需要遍歷域庇，這就是在ArrayList分析時(shí)提到過的順序下標(biāo)遍歷
- 添加元素嵌戈，刪除都很有速度優(yōu)勢(shì)
- 實(shí)現(xiàn)對(duì)列接口
ArrayList和LinkedList的區(qū)別
- 順序插入，兩者速度都很快听皿，但是ArrayList稍快于LinkedList熟呛，數(shù)組實(shí)現(xiàn)，數(shù)組是提前創(chuàng)建好的尉姨；LinkedList每次都需要重新new新節(jié)點(diǎn)
- LinedList需要維護(hù)前后節(jié)點(diǎn)庵朝，會(huì)更耗費(fèi)內(nèi)存
- 遍歷，LinedList適合用迭代遍歷；ArrayList適合用循環(huán)遍歷
- 不要使用普通for循環(huán)遍歷LinedList
- 也不要使用迭代遍歷遍歷ArrayList（具體看上篇文章《ArrayList分析》）
- 刪除和插入就不說了九府，畢竟ArrayList需要復(fù)制數(shù)組和擴(kuò)容椎瘟。
我不能保證每一個(gè)地方都是對(duì)的，但是可以保證每一句話昔逗，每一行代碼都是經(jīng)過推敲和斟酌的降传。希望每一篇文章背后都是自己追求純粹技術(shù)人生的態(tài)度。
永遠(yuǎn)相信美好的事情即將發(fā)生勾怒。
