Linkedlist
簡介
本節(jié)來介紹LinkedList ,他也是List 接口下最常用的用來存儲數(shù)據(jù)的工具類之一。仍然從基礎(chǔ)的數(shù)據(jù)結(jié)構(gòu)，整個類的繼承和實(shí)現(xiàn)的體系來了解。Linkedlist可以做那些事情，在哪些的應(yīng)用場景下更適合應(yīng)用。
1.首先LinkedList是基于雙向鏈表。意味著增刪比較快，但是查找相對于ArrayList會比較慢。（常見面試題之一，ArrayList與LinkedList的區(qū)別），本質(zhì)上來講，就是二者的數(shù)據(jù)結(jié)構(gòu)不同，稍后可以說明。
2.實(shí)現(xiàn)了 Deque 接口，意味著可以進(jìn)行隊(duì)列操作。
3.實(shí)現(xiàn)了Cloneable接口，即覆蓋了函數(shù)clone()，可以被克隆。
4.實(shí)現(xiàn)了 Serializable 接口，意味著LinkedList支持序列化，能通過序列化去傳輸。
5.LinkedList和Arraylist一樣，都是線程不安全的。
結(jié)構(gòu)圖
構(gòu)造函數(shù)
Linkedlist共有兩個構(gòu)造函數(shù)。分別為：
1.無參構(gòu)造，直接創(chuàng)建LinkedList對象。
/**
* 構(gòu)造一個空列表
*/
public LinkedList() {
}
2.參數(shù)需要一個Collection集合，作為參數(shù)，構(gòu)造一個新的集合。
/**
* 構(gòu)造包含指定元素的列表集合，按照集合返回的順序迭代器
*
* @param c the collection whose elements are to be placed into this list
* @throws NullPointerException if the specified collection is null
*/
public LinkedList(Collection<? extends E> c) {
this();
addAll(c);
}
這里就是，接收一個集合，作為參數(shù)，然后調(diào)用 addAll() 方法，來初始化LinkedList()。
接下來分析，addAll()方法做了哪些事情。
這里調(diào)用了 public 權(quán)限的 addAll() 方法。說明，我們可以將任意一個集合添加到 LinkedList 中。
這里有一點(diǎn)要注意：默認(rèn)的size就是當(dāng)前的鏈表長度，默認(rèn)在當(dāng)前鏈表后面添加參數(shù)的集合。
/**
* 將指定集合中的所有元素追加到末尾這個列表，按照指定的返回順序集合的迭代器。
* 如果沒有定義此操作的行為在操作中修改指定的集合進(jìn)步。(注意，如果指定的集合是，就會發(fā) * 生這種情況*這個列表，它不是空的。
*/
public boolean addAll(Collection<? extends E> c) {
return addAll(size, c);
}
addAll()
這里要對Node做一下解釋，Node共包含三個屬性，上一個節(jié)點(diǎn)，當(dāng)前元素，下一個節(jié)點(diǎn)。這樣就組成了一個鏈表。
private static class Node<E> {
E item;//元素值
Node<E> next;//上一個節(jié)點(diǎn)
Node<E> prev;//下一個節(jié)點(diǎn)
Node(Node<E> prev, E element, Node<E> next) {
this.item = element;
this.next = next;
this.prev = prev;
}
}
/**
*將指定集合中的所有元素插入其中列表，從指定位置開始。變化的元素
*目前處于該位置(如果有的話)和任何后續(xù)元素
*右邊(增加他們的指數(shù))。新的元素將會出現(xiàn)
*在列表中，以它們被返回的順序指定集合的迭代器。
*/
public boolean addAll(int index, Collection<? extends E> c) {
//檢查索引是否合法
checkPositionIndex(index);
//將添加的集合先轉(zhuǎn)成Object數(shù)組
Object[] a = c.toArray();
int numNew = a.length;
//如果數(shù)組的長度為0，返回false不做任何操作
if (numNew == 0)
return false;
//定義一個節(jié)點(diǎn)
Node<E> pred, succ;
//當(dāng)向鏈表最后面插入時。
if (c == size) {
succ = null;
//將鏈表最后一個節(jié)點(diǎn)，賦值給當(dāng)前定義節(jié)點(diǎn)的上一個節(jié)點(diǎn)。
pred = last;
} else {
//這里查找原來index位置的Node，做為后置節(jié)點(diǎn)。
succ = node(index);
//前置節(jié)點(diǎn)為index節(jié)點(diǎn)的前一個節(jié)點(diǎn)。
pred = succ.prev;
}
for (Object o : a) {
@SuppressWarnings("unchecked") E e = (E) o;
//構(gòu)造一個新的節(jié)點(diǎn)，pred原來index位置的上一個節(jié)點(diǎn)。e當(dāng)前節(jié)點(diǎn)
Node<E> newNode = new Node<>(pred, e, null);
//如果pred為空,說明原來的鏈表是空的，那么新增的節(jié)點(diǎn)為鏈表的第一個節(jié)點(diǎn)。
if (pred == null)
first = newNode;
else
//這里是當(dāng)鏈表不是初始化時候，替換鏈表內(nèi)指定的node
pred.next = newNode;
pred = newNode;
}
//如果succ為空，說明在鏈表的末尾，（或者是鏈表剛剛初始化，也為null）
if (succ == null) {
last = pred;
} else {
//鏈表中間添加情況，更新前置節(jié)點(diǎn) 后置節(jié)點(diǎn)。
pred.next = succ;
succ.prev = pred;
}
//修改size
size += numNew;
//修改modCount（這里后續(xù)解釋作用是什么）
modCount++;
return true;
}
add()添加一個元素到鏈表內(nèi)
/**
* 添加一個元素到鏈鏈表中，默認(rèn)追加到鏈表的末尾‘
* 這里調(diào)用了public權(quán)限的add方法。’
*/
public boolean add(E e) {
//調(diào)用linkLast
linkLast(e);
return true;
}
linkLast追加到鏈表末尾
/**
*添加到鏈表末尾
*/
void linkLast(E e) {
//保存原有鏈表的最后一個節(jié)點(diǎn)。
final Node<E> l = last;
//構(gòu)造當(dāng)前節(jié)點(diǎn)，并且原來的最后一個節(jié)點(diǎn)最為當(dāng)前節(jié)點(diǎn)的上一個節(jié)點(diǎn)
final Node<E> newNode = new Node<>(l, e, null);
//當(dāng)前節(jié)點(diǎn)作為原有鏈表的最后一個節(jié)點(diǎn)
last = newNode;
//如果原有的最后一個節(jié)點(diǎn)為null，說明鏈表為null（剛剛初始化）
if (l == null)
//當(dāng)前節(jié)點(diǎn)作為第一個節(jié)點(diǎn)。
first = newNode;
else
//將當(dāng)前節(jié)點(diǎn)賦值給原來最后一個節(jié)點(diǎn)的下一個節(jié)點(diǎn)。
l.next = newNode;
size++;
modCount++;
}
remove刪除元素
/**
*刪除指定元素
*/
public boolean remove(Object o) {
//如果要刪除的元素為空，那么便利當(dāng)前鏈表，找到為空的元素，解除關(guān)聯(lián)。
if (o == null) {
for (Node<E> x = first; x != null; x = x.next) {
if (x.item == null) {
//實(shí)際從鏈表中去除關(guān)聯(lián)
unlink(x);
return true;
}
}
} else {
for (Node<E> x = first; x != null; x = x.next) {
//如果去除指定元素，則直接equals尋找要刪除的元素。
if (o.equals(x.item)) {
unlink(x);
return true;
}
}
}
return false;
}
unlink刪除元素
/**
* 刪除指定的元素
*/
E unlink(Node<E> x) {
// assert x != null;
//需要刪除的節(jié)點(diǎn)
final E element = x.item;
//保存需要刪除節(jié)點(diǎn)的下一個節(jié)點(diǎn)
final Node<E> next = x.next;
//保存需要刪除節(jié)點(diǎn)的上一個節(jié)點(diǎn)
final Node<E> prev = x.prev;
//如果上一個節(jié)點(diǎn)是空，則原有的末尾節(jié)點(diǎn)作為第一個節(jié)點(diǎn)
if (prev == null) {
first = next;
} else {
//原有節(jié)點(diǎn)上一個節(jié)點(diǎn)，對應(yīng)的下一個節(jié)點(diǎn)為next。有點(diǎn)繞口。。。
prev.next = next;
//將當(dāng)前節(jié)點(diǎn)的 前置節(jié)點(diǎn)置空
x.prev = null;
}
//如果后置節(jié)點(diǎn)為空（說明當(dāng)前節(jié)點(diǎn)原本是尾節(jié)點(diǎn)）
if (next == null) {
//則尾節(jié)點(diǎn)為前置節(jié)點(diǎn)
last = prev;
} else {
//將當(dāng)前節(jié)點(diǎn)的 后置節(jié)點(diǎn)置空
next.prev = prev;
x.next = null;
}
//當(dāng)前元素置為null
x.item = null;
//鏈表數(shù)量-1
size--;
//修改modCount
modCount++;
//返回刪除的元素
return element;
}
push&pop
注意：鏈表中也存在push，pop操作，說明可以作為一個棧來操作。面試也很常見實(shí)現(xiàn)一個自己的?；蛘哧?duì)列。這里看一下，push和pop操作，用來了解一下棧是如何實(shí)現(xiàn)的。
public void push(E e) {
addFirst(e);
}
public E pop() {
return removeFirst();
}
調(diào)用的方法分別為addFirst，removeFirst。
/**
* 直接追加到鏈表最前面
*/
public void addFirst(E e) {
linkFirst(e);
}
pop也是一樣的道理，直接操作首節(jié)點(diǎn)
/**
*刪除首節(jié)點(diǎn)
*/
public E removeFirst() {
final Node<E> f = first;
if (f == null)
throw new NoSuchElementException();
return unlinkFirst(f);
}
總結(jié)
1.上文說明了LinkedList是基于雙向鏈表，在實(shí)際的代碼中看到，當(dāng)增加或者刪除一個元素，在原有的鏈表中直接尋找并且unlink即可。
2.刪除和增加都涉及到modCount操作，這點(diǎn)要注意（后續(xù)解釋，或者可以自行百度）。
3.其實(shí)增加和刪除或者其他操作，都圍繞著一個核心，就是處理鏈表。這里如果把鏈表的結(jié)構(gòu)自己理解的足夠好，可以嘗試自己寫一個自己的鏈表。
4.jdk中每一個類，方法都拆分的足夠細(xì)致，得以最大化的復(fù)用。這也是是學(xué)習(xí)的目的之一，將自己的代碼做到盡可能細(xì)致的拆分，每一個方法具體用來做什么。
