public class LinkedList<E>
extends AbstractSequentialList<E>
implements List<E>, Deque<E>, Cloneable, java.io.Serializable
LinkedList繼承自AbstractSequentialList，實(shí)現(xiàn)了List、 Deque、 Cloneable、Serializable 4個(gè)接口
用法的話基本與ArrayList用法一致，這邊也不多講啦，主要還是看看內(nèi)部實(shí)現(xiàn)
不同于ArrayList的get方法可以輕松的看出內(nèi)部是由數(shù)組實(shí)現(xiàn)的，所以這邊就先講結(jié)論了，LinkedList內(nèi)部是由雙向鏈表實(shí)現(xiàn)的[1]，我們先來(lái)看一些基本的變量
transient int size = 0;
transient Node<E> first;
transient Node<E> last;
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;
}
}
- size不多講，跟ArrayList一樣，返回的是LinkedList的長(zhǎng)度
- Node類（節(jié)點(diǎn)），里面一共有三個(gè)參數(shù)，
1.item：該節(jié)點(diǎn)存放的元素
2.prev：上一個(gè)節(jié)點(diǎn)對(duì)象
3.next：下一個(gè)節(jié)點(diǎn)對(duì)象- first就是LinkedList的第一個(gè)節(jié)點(diǎn)
- last則是最后一個(gè)節(jié)點(diǎn)
那么為什么特地弄出頭尾節(jié)點(diǎn)來(lái)呢？
因?yàn)殒湵聿煌跀?shù)組，數(shù)組可以通過(guò)索引直接定位到所需要操作的元素，而鏈表不行，它只能通過(guò).next一個(gè)一個(gè)的遍歷元素直到查詢到指定數(shù)據(jù)，這樣一來(lái)查詢的時(shí)間就呈線性增長(zhǎng)了。所以在遍歷鏈表的時(shí)候，采用了“二分法”，若需要對(duì)>size/2位置的元素進(jìn)行CRUD，則從尾結(jié)點(diǎn)從后往前遍歷，否則從頭結(jié)點(diǎn)從前往后遍歷
我們同樣來(lái)看看LinkedList的add方法：
LinkedList<String> linkedList = new LinkedList<>();
linkedList.add("asd");
public LinkedList() {
}
public LinkedList(Collection<? extends E> c) {
this();
addAll(c);
}
*/
public boolean add(E e) {
linkLast(e);
return true;
}
/**
* Links e as last element.
*/
void linkLast(E e) {
這里我們知道last一開(kāi)始是為null的
final Node<E> l = last;
這個(gè)是需要插入的節(jié)點(diǎn)，pre（上一個(gè)節(jié)點(diǎn)）為l（尾結(jié)點(diǎn)），
next（下一個(gè)節(jié)點(diǎn)）為null，元素值為e
final Node<E> newNode = new Node<>(l, e, null);
將需要插入的值賦予尾結(jié)點(diǎn)
last = newNode;
如果舊的尾節(jié)點(diǎn)為null，說(shuō)明鏈表為空，此時(shí)將需要插入
的節(jié)點(diǎn)賦值給頭結(jié)點(diǎn)
if (l == null)
first = newNode;
else
否則將需要插入的節(jié)點(diǎn)插到尾結(jié)點(diǎn)后面（last.next指向新節(jié)點(diǎn)
，上方在聲明newNode的時(shí)候就將newNode.pre指向了last）
l.next = newNode;
size++;
modCount++;
}
public void add(int index, E element)
public void add(int index, E element) {
校驗(yàn)index是否有效，無(wú)效則直接拋出異常
checkPositionIndex(index);
如果插入的值剛好在尾結(jié)點(diǎn)，則直接插入
if (index == size)
linkLast(element);
else
否則進(jìn)入該方法
linkBefore(element, node(index));
}
/**
* Returns the (non-null) Node at the specified element index.
*/
Node<E> node(int index) {
// assert isElementIndex(index);
這里就是上面所說(shuō)的，<size/2則從前往后遍歷
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;
}
}
/**
* Inserts element e before non-null Node succ.
*/
1. 需要在succ節(jié)點(diǎn)前插入指定的元素
void linkBefore(E e, Node<E> succ) {
// assert succ != null;
獲取succ的上一個(gè)節(jié)點(diǎn)
final Node<E> pred = succ.prev;
2.生成新的節(jié)點(diǎn)，上一個(gè)節(jié)點(diǎn)為succ的上一個(gè)節(jié)點(diǎn)，下一個(gè)節(jié)點(diǎn)則為succ
final Node<E> newNode = new Node<>(pred, e, succ);
3.指定succ的上一個(gè)節(jié)點(diǎn)為新節(jié)點(diǎn)
succ.prev = newNode;
這里判斷如果succ是first節(jié)點(diǎn)（頭結(jié)點(diǎn)）則將新節(jié)點(diǎn)指定為頭結(jié)點(diǎn)
if (pred == null)
first = newNode;
else
4.否則將新節(jié)點(diǎn)的上一個(gè)節(jié)點(diǎn)的next指向新節(jié)點(diǎn)
pred.next = newNode;
size++;
modCount++;
}
上面這一點(diǎn)其實(shí)就是對(duì)新節(jié)點(diǎn)的pre指向succ的pre節(jié)點(diǎn)，next指向succ節(jié)點(diǎn)，然后新節(jié)點(diǎn)的pre節(jié)點(diǎn)的next指向新節(jié)點(diǎn)。沒(méi)錯(cuò)第一次接觸的小伙伴一定非常繞，這里畫幅圖讓大家更好理解（這里為了更好理解，我們就取index為1時(shí)插入，即在頭結(jié)點(diǎn)后插入，分別對(duì)應(yīng)上方的1234）
（這里有點(diǎn)跑題了，講到鏈表去了= =）
public boolean addAll(int index, Collection<? extends E> c)
public boolean addAll(int index, Collection<? extends E> c) {
校驗(yàn)index是否有效
checkPositionIndex(index);
Object[] a = c.toArray();
int numNew = a.length;
如果傳進(jìn)來(lái)的collection為空的，則直接返回
if (numNew == 0)
return false;
succ節(jié)點(diǎn)：需要在succ節(jié)點(diǎn)前插入指定的元素（所需要插入節(jié)點(diǎn)的下一個(gè)節(jié)點(diǎn)）
pred節(jié)點(diǎn)：succ的上一個(gè)節(jié)點(diǎn)(所需要插入節(jié)點(diǎn)的上一個(gè)節(jié)點(diǎn)）
Node<E> pred, succ;
if (index == size) {
如果剛好在尾結(jié)點(diǎn)插入
succ = null;
pred = last;
} else {
否則遍歷之前的鏈表，獲取succ節(jié)點(diǎn)
succ = node(index);
pred = succ.prev;
}
for (Object o : a) {
這邊的操作無(wú)非就是重復(fù)上方add(int inedx,E e)的方法，這邊就不多講了
@SuppressWarnings("unchecked")
E e = (E) o;
Node<E> newNode = new Node<>(pred, e, null);
if (pred == null)
first = newNode;
else
pred.next = newNode;
pred = newNode;
}
如果是尾部插入，則將last重新賦值
if (succ == null) {
last = pred;
} else {
如果是中間/頭部插入，該咋咋地
pred.next = succ;
succ.prev = pred;
}
size += numNew;
modCount++;
return true;
}
remove方法的話就不講了吧，與add的原理差不多，大家可以自己去康康
我們可以發(fā)現(xiàn)，LinkedList插入刪除是非常快的，因?yàn)橹恍枰焉弦粋€(gè)節(jié)點(diǎn)的next、下一個(gè)節(jié)點(diǎn)的pre指向新節(jié)點(diǎn)即可。與此同時(shí)還有一個(gè)問(wèn)題，就是得找到所需要插入的位置才能進(jìn)行增刪操作，可數(shù)據(jù)量一大遍歷的時(shí)間就呈線性增長(zhǎng)了，帶動(dòng)著增刪操作的成本也高了起來(lái)
我們以1000萬(wàn)條數(shù)據(jù)為例，對(duì)LinkedList與ArrayList進(jìn)行對(duì)比
| 操作 | ArrayList | LinkedList |
|---|---|---|
| for循環(huán)插入1000萬(wàn)個(gè)值 | 2676ms | 6589ms |
| add頭部 | 78ms | <1ms |
| add中間值 | 78ms | 140ms |
| add末尾 | 78ms | <1ms |
| remove頭部 | 15ms | <1ms |
| remove中間值 | 26ms | 141ms |
| remove尾部 | <1ms | <1ms |
| get頭部 | <1ms | <1ms |
| get中間值 | <1ms | 140ms |
| get尾部 | <1ms | <1ms |
*以上數(shù)據(jù)僅供參考，ArrayList add、remove之前都經(jīng)過(guò)trimToSize()方法處理
我們可以看到，ArrayList查詢是非常快的，但是增刪就有些不盡人意了（除卻remove尾部，因?yàn)榇藭r(shí)是不需要擴(kuò)容處理的）
LinkedList對(duì)頭尾部的增刪改查都是非?？斓?，而中間值則非常慢
總結(jié)
- 在數(shù)據(jù)量較小的情況比如10條、100條喜歡用啥用啥
- 數(shù)據(jù)量大一點(diǎn)，并且總是在尾部/頭部新增數(shù)據(jù)，那是非常建議使用LInkedList的
- 數(shù)據(jù)量大而查詢多則使用ArrayList
- 那我數(shù)據(jù)量又多，查詢?cè)鰟h都有該怎么選擇？還是ArrayList，畢竟ArrayList你可以在一開(kāi)始就申明所需要的數(shù)組大小，這樣后續(xù)的擴(kuò)容耗時(shí)問(wèn)題就可以少考慮一點(diǎn)
-
數(shù)據(jù)結(jié)構(gòu)本系列就不展開(kāi)討論了，但是這樣其實(shí)是有點(diǎn)本末倒置了，因?yàn)椴涣私怄湵?、樹這些數(shù)據(jù)結(jié)構(gòu)后續(xù)的集合也很難理解，但是沒(méi)辦法數(shù)據(jù)結(jié)構(gòu)里面隨便拎出一個(gè)就夠講大半天的，預(yù)計(jì)在2月份的時(shí)候會(huì)有數(shù)據(jù)結(jié)構(gòu)系列的，屆時(shí)與算法一起研究 ?
