上一章進(jìn)行了ArrayList源碼分析南片，這一章分析一下另一個重要的List集合LinkedList筹煮。
public class LinkedList<E>
extends AbstractSequentialList<E>
implements List<E>, Deque<E>, Cloneable, java.io.Serializable{}
public class ArrayList<E> extends AbstractList<E>
implements List<E>, RandomAccess, Cloneable, java.io.Serializable{}
LinkedList與ArrayList對比發(fā)現(xiàn)：
- 它們繼承的基類不同哲戚，LinkedList繼承自AbstractSequentialList基類衅金，AbstractSequentialList是AbstractList子類妖谴，這個類后面再說。
- LinkedList實現(xiàn)了Deque接口酵熙，代表它是一個隊列轧简，準(zhǔn)確地說它是一個雙端隊列。
- LinkedList沒有實現(xiàn)RandomAccess可隨機(jī)訪問標(biāo)記接口匾二，表示使用LinkedList的get(int index)獲取集合中元素的方法效率非常低哮独。
一. Queue隊列接口
隊列是一種FIFO(先入先出)的數(shù)據(jù)結(jié)構(gòu)，和它相對應(yīng)的是一種叫做棧(LIFO后入先出)的數(shù)據(jù)結(jié)構(gòu)察藐。
1.1 棧
對于棧來說皮璧，我們想一想它應(yīng)該有哪些方法?
- void push(E e); 向棧頂添加元素。
- E pop(); 移除棧頂元素分飞，并返回它悴务。
- E peek(); 查看棧頂元素。
- boolean isEmpty(); 棧是不是為空浸须。
- int size(); 棧中元素的數(shù)量惨寿。
要實現(xiàn)一個棧，實現(xiàn)這5個方法就可以了删窒。
1.2 隊列
隊列與棧的方法應(yīng)該差不多裂垦，只不過每次添加的時候，都是向隊列尾新添元素肌索，而不是隊列頭蕉拢。
- boolean offer(E e); 向隊列尾添加元素。
- E poll();移除隊列頭元素，并返回它晕换。
- E peek(); 查看隊列頭元素午乓。
- boolean isEmpty(); 隊列是不是為空抑淫。
- int size(); 隊列中元素的數(shù)量癌幕。
public interface Queue<E> extends Collection<E> {
// 向隊列末尾新添加元素,返回true表示添加成功
// 不會返回false抒痒，因為添加失敗直接拋出IllegalStateException異常匙隔。
// 一般調(diào)用offer方法實現(xiàn)。
boolean add(E e);
// 向隊列末尾新添加元素脖隶，返回true表示添加成功侵歇，返回false碍彭，添加失敗
boolean offer(E e);
// 這個與Collection中的remove方法不一樣库快，因為Collection中的remove方法都要提供一個元素或者集合摸袁，用于刪除。
// 這里不穿任何參數(shù)义屏，就是代表刪除隊列第一個元素(即隊列頭)靠汁，并返回它
// 還需要注意的時，如果隊列是空的闽铐，即隊列頭是null蝶怔，這個方法會拋出NoSuchElementException異常。
E remove();
// 這個方法也是刪除隊列第一個元素(即隊列頭)阳啥，并返回它
// 但是它和remove()方法不同的時添谊，如果隊列是空的，即隊列頭是null察迟，它不會拋出異常，而是會返回null耳高。
E poll();
// 查看隊列頭的元素扎瓶，如果隊列是空的，就拋出異常
E element();
// 查看隊列頭的元素泌枪。如果隊列是空的概荷，不會拋出異常，而是返回null
E peek();
}
可以看出繼承自Collection接口碌燕，那么size()和isEmpty()方法都由Collection接口提供误证，但是Queue接口還提供了是三個好像重復(fù)的方法。
- 向隊列尾添加元素的方法：add(E e)與offer(E e)修壕。區(qū)別就是隊列是滿的愈捅，添加失敗時，add方法會拋出異常慈鸠，而offer方法只會返回false蓝谨。
- 移除隊列頭元素的方法：remove()與poll()。區(qū)別就是隊列為空的時候,remove方法會拋出異常，poll方法只會返回null譬巫。
- 查看隊列頭元素的方法：element()與peek()咖楣。區(qū)別就是隊列為空的時候，element方法會拋出異常芦昔，peek方法只會返回null诱贿。
下面是AbstractQueue中的實現(xiàn)
public abstract class AbstractQueue<E>
extends AbstractCollection<E>
implements Queue<E> {
protected AbstractQueue() {
}
// 直接調(diào)用offer方法來實現(xiàn)，如果隊列是滿的咕缎，添加失敗瘪松，
// 則拋出IllegalStateException異常
public boolean add(E e) {
if (offer(e))
return true;
else
throw new IllegalStateException("Queue full");
}
// 直接調(diào)用poll方法來實現(xiàn)，如果隊列是空的锨阿，移除元素失敗宵睦，
// 則拋出NoSuchElementException異常
public E remove() {
E x = poll();
if (x != null)
return x;
else
throw new NoSuchElementException();
}
// 直接調(diào)用peek方法來實現(xiàn)，如果隊列是空的,查看元素失敗墅诡，
// 則拋出NoSuchElementException異常
public E element() {
E x = peek();
if (x != null)
return x;
else
throw new NoSuchElementException();
}
......
}
二. 雙端隊列
它與普通隊列相比較壳嚎，它既可以在隊列頭添加元素，也可以在隊列尾添加元素末早；既可以在隊列頭刪除元素烟馅，也可以在隊列尾刪除元素。
注意一下然磷，因為雙端隊列特性郑趁，所以它很容易實現(xiàn)一個棧，也就是說它本身可以當(dāng)做棧使用姿搜。
根據(jù)雙端隊列的特性寡润，它比普通隊列應(yīng)該多了三個方法。
- boolean offerFirst(E e); 向隊列頭添加元素舅柜。
- boolean offerLast(E e); 向隊列尾添加元素梭纹。
- E pollFirst();移除隊列頭元素，并返回它致份。
- E pollLast();移除隊列尾元素变抽，并返回它。
- E peekFirst(); 查看隊列頭元素氮块。
- E peekLast(); 查看隊列尾元素绍载。
- boolean isEmpty(); 隊列是不是為空。
- int size(); 隊列中元素的數(shù)量滔蝉。
public interface Deque<E> extends Queue<E> {
// 向隊列頭添加元素
void addFirst(E e);
// 向隊列末尾新添加元素
void addLast(E e);
// 向隊列頭添加元素,和addFirst(E e)作用一樣击儡，就是直接調(diào)用addFirst(E e)方法來實現(xiàn)。
boolean offerFirst(E e);
// 向隊列末尾新添加元素锰提，和addLast(E e)作用一樣曙痘，就是直接調(diào)用addLast(E e)方法來實現(xiàn)芳悲。
boolean offerLast(E e);
// 刪除隊列第一個元素(即隊列頭)，并返回它, 如果隊列是空的,這個方法會拋出NoSuchElementException異常边坤。
// 注名扛，與Queue接口中remove()作用一樣，remove()方法就是調(diào)用removeFirst()方法來實現(xiàn)的
E removeFirst();
// 刪除隊列最后一個元素(即隊列尾)茧痒，并返回它, 如果隊列是空的,這個方法會拋出NoSuchElementException異常肮韧。
E removeLast();
// 刪除隊列第一個元素(即隊列頭)，并返回它, 如果隊列是空的,它不會拋出異常旺订，而是會返回null弄企。
// 注，與Queue接口中poll()作用一樣区拳，
E pollFirst();
// 刪除隊列最后一個元素(即隊列尾)拘领，并返回它, 如果隊列是空的,它不會拋出異常，而是會返回null樱调。
E pollLast();
// 查看隊列頭的元素约素，如果隊列是空的，就拋出異常
// 注笆凌，與Queue接口中element()作用一樣圣猎，
E getFirst();
// 查看隊列尾的元素，如果隊列是空的乞而，就拋出異常
E getLast();
// 查看隊列頭的元素送悔。如果隊列是空的，不會拋出異常爪模，而是返回null
E peekFirst();
// 查看隊列尾的元素欠啤。如果隊列是空的，不會拋出異常呻右，而是返回null
E peekLast();
// 從隊列頭都開始遍歷跪妥，找到與o相等的第一個元素刪除它，并返回true声滥，如果沒找到就返回false，最多只刪除一個元素
// 注侦香，與Collection中remove(Object o)方法作用一樣
boolean removeFirstOccurrence(Object o);
// 從隊列尾都開始遍歷落塑，找到與o相等的第一個元素刪除它，并返回true罐韩，如果沒找到就返回false憾赁，最多只刪除一個元素
boolean removeLastOccurrence(Object o);
// *** Queue methods ***
boolean add(E e);
boolean offer(E e);
E remove();
E poll();
E element();
E peek();
// *** Stack methods ***
// 向棧頂添加元素。與addFirst(E e)方法作用一樣
void push(E e);
// 移除棧頂元素散吵，并返回它龙考。如果棧為空的話蟆肆，會拋出NoSuchElementException異常
// 注，與removeFirst()方法一樣
E pop();
// *** Collection methods ***
boolean remove(Object o);
boolean contains(Object o);
public int size();
Iterator<E> iterator();
Iterator<E> descendingIterator();
}
可以看出定義的接口中的方法比我們預(yù)計的多得多晦款，主要是添加了一些隊列為空時炎功，獲取元素會拋出異常的方法，還順便定義了棧的方法缓溅，因為雙端隊列很容易實現(xiàn)一個棧的功能蛇损。
雙端隊列Deque與普通隊列Queue相比較，就是多了從隊列頭插入坛怪，從隊列尾刪除淤齐，從隊列尾查看的功能。
三. AbstractSequentialList抽樣類
AbstractSequentialList這個類表示它的子類是使用鏈表這種數(shù)據(jù)結(jié)構(gòu)來存儲集合元素的袜匿，而不是使用數(shù)組這種數(shù)據(jù)結(jié)構(gòu)更啄。這有什么不同呢？
- 數(shù)組的插入和刪除的效率都不高居灯，因為可能涉及到數(shù)組元素的移動祭务。但是訪問效率非常高，它支持隨機(jī)訪問穆壕，就是通過數(shù)組的下標(biāo)直接獲取對應(yīng)的元素待牵。
- 鏈表的插入和刪除的效率都很高，因為只需要改變元素之間指向就可以了喇勋。但是訪問效率不高缨该，它不支持隨機(jī)訪問，必須從鏈表頭或者鏈表尾開始一次訪問川背。
還記得我們在AbstractList方法中贰拿，怎么實現(xiàn)迭代器的么？
使用一個cursor屬性來記錄索引位置熄云，然后通過調(diào)用List集合的get(int index)來獲取對應(yīng)的元素膨更。這里就不行了，因為通過get(int index)方法獲取集合元素的效率非常低缴允。
而遍歷鏈表的方式就是獲取鏈表中一個元素荚守，然后通過指向下一個元素的引用，不斷獲取下一個元素练般，直到為空矗漾，表示已經(jīng)到了鏈表尾，而不是通過索引的方式薄料。
所以我們思考一下AbstractSequentialList會做哪些事情敞贡。
- 將獲取迭代器的方法設(shè)置成abstract抽樣方法，強(qiáng)制子類提供迭代器方法摄职，因為不能用索引這種低效率的方式獲取元素誊役，所以強(qiáng)制子類去實現(xiàn)获列。
// 調(diào)用listIterator方法，返回一個迭代器
public Iterator<E> iterator() {
return listIterator();
}
// 子類必須復(fù)寫這個方法蛔垢，提供一個ListIterator迭代器击孩。
public abstract ListIterator<E> listIterator(int index);
- List集合可以通過索引得到集合中的元素，AbstractSequentialList集合也必須支持這種方式啦桌，雖然效率低溯壶。這時就可以通過ListIterator迭代器實現(xiàn)對應(yīng)方法。
這里就與AbstractList中內(nèi)部迭代器ListIterator類不同甫男，AbstractList中迭代器是通過調(diào)用AbstractList中g(shù)et(int index)和set(int index, E element)方法來實現(xiàn)對應(yīng)功能的且改，所以AbstractList子類必須復(fù)寫這些方法。
而AbstractSequentialList是通過迭代器來實現(xiàn)本AbstractSequentialList對應(yīng)方法板驳，所以子類必須實現(xiàn)一個自定義迭代器又跛。
public abstract class AbstractSequentialList<E> extends AbstractList<E> {
protected AbstractSequentialList() {
}
// 調(diào)用迭代器listIterator獲取
public E get(int index) {
try {
// 迭代器會先根據(jù)index值，從鏈表頭開始遍歷若治，直到移動到index位置慨蓝，將元素返回，所以效率不高端幼。
return listIterator(index).next();
} catch (NoSuchElementException exc) {
throw new IndexOutOfBoundsException("Index: "+index);
}
}
// 調(diào)用迭代器listIterator的set設(shè)置
public E set(int index, E element) {
try {
ListIterator<E> e = listIterator(index);
E oldVal = e.next();
e.set(element);
return oldVal;
} catch (NoSuchElementException exc) {
throw new IndexOutOfBoundsException("Index: "+index);
}
}
// 調(diào)用迭代器listIterator的add方法添加元素
public void add(int index, E element) {
try {
listIterator(index).add(element);
} catch (NoSuchElementException exc) {
throw new IndexOutOfBoundsException("Index: "+index);
}
}
// 調(diào)用迭代器listIterator的remove方法移除元素
public E remove(int index) {
try {
ListIterator<E> e = listIterator(index);
E outCast = e.next();
e.remove();
return outCast;
} catch (NoSuchElementException exc) {
throw new IndexOutOfBoundsException("Index: "+index);
}
}
// Bulk Operations
public boolean addAll(int index, Collection<? extends E> c) {
try {
boolean modified = false;
ListIterator<E> e1 = listIterator(index);
Iterator<? extends E> e2 = c.iterator();
while (e2.hasNext()) {
e1.add(e2.next());
modified = true;
}
return modified;
} catch (NoSuchElementException exc) {
throw new IndexOutOfBoundsException("Index: "+index);
}
}
// 會調(diào)用listIterator方法礼烈，返回一個迭代器
public Iterator<E> iterator() {
return listIterator();
}
// 子類必須復(fù)寫這個方法，提供一個ListIterator迭代器婆跑。
public abstract ListIterator<E> listIterator(int index);
}
四. 單向鏈表和雙向鏈表
4.1 單向鏈表
簡單的說此熬，元素除了包含本身的數(shù)據(jù)item,還有一個指向下一個元素的引用next。數(shù)據(jù)結(jié)構(gòu)就像這樣：
class Node<E> {
E item;
Node<E> next;
Node( E element, Node<E> next) {
this.item = element;
this.next = next;
}
}
然后我們在看看單向鏈表插入和刪除滑进。
- 插入：單向鏈表的插入犀忱，我們只需要改變兩個引用就可以了。
private void insert(Node<E> prevNode, Node<E> node, Node<E> newNode) {
// prevNode表示插入點前一個元素
// node表示插入點元素
// newNode表示要添加的元素扶关，將它放入插入點(即前一個元素的next指向)
// 并將newNode的next指向原來元素node
if (prevNode != null) prevNode.next = newNode;
newNode.next = node;
}
在鏈表node元素前添加一個元素阴汇，就是將node元素前一個元素的next指向新元素newNode，再將新元素newNode的next指向node元素节槐，這樣就把新元素newNode插入到鏈表中了搀庶。
注意要做一下前元素非空判斷，如果前元素為空表示插入點是鏈表頭铜异。
根據(jù)我的經(jīng)驗地来，先不考慮null的情況，改變對應(yīng)引用熙掺，這里就是prevNode.next = newNode，newNode.next = node咕宿。然后我們再看看那些需要考慮null的情況币绩。
比如這里prevNode就需要考慮null情況蜡秽，否則會發(fā)生空指針異常。prevNode為空其實表示在鏈表頭缆镣。newNode是不允許為空芽突。而node是不是為空對我們程序沒有任何影響。
- 刪除：單向鏈表的刪除董瞻，也只需要改變兩個引用就可以了寞蚌。
private void delete(Node<E> prevNode, Node<E> node) {
// prevNode表示被刪除元素的前一個元素
// node表示被刪除的元素
if (prevNode != null) prevNode.next = node.next;
node.next = null;
}
刪除一個單向鏈表元素，就是將它的前一個元素的next指向它的next钠糊，這樣就在整個鏈表中查找不到這個元素了挟秤，然后將它的next設(shè)置為null。
當(dāng)前一個元素為null抄伍，表示被刪除元素是鏈表頭艘刚，那么需要將表頭的next指向被刪除元素的next，這里沒有體現(xiàn)截珍。
4.2 雙向鏈表
與單向鏈表相比攀甚，它的元素多了一個指向上一個元素的引用prev。數(shù)據(jù)結(jié)構(gòu)就像這樣：
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;
}
}
然后我們在看看雙向鏈表插入和刪除岗喉。
- 插入：雙向鏈表的插入秋度，我們需要改變四個引用。
private void insert(Node<E> node, Node<E> newNode) {
// node表示插入點元素
// newNode表示要添加的元素钱床，將它插入到node元素之前
// 將node前一個元素的next指向新元素newNode
if(node.prev != null) node.prev.next = newNode;
// 將新元素newNode的prev指向node前一個元素
newNode.prev = node.prev;
// 將node的prev指向新元素newNode荚斯，現(xiàn)在node的前一個元素變成新元素newNode
node.prev = newNode;
// 將新元素的next指向node，所以新元素的下一個元素是node
newNode.next = node;
}
要在元素node前插入一個新元素newNode诞丽。那么就需要四步：
- 將node前一個元素的next指向新元素newNode
- 將新元素newNode的prev指向node前一個元素
- node元素的prev指向新元素
- 新元素newNode的next指向node
- 刪除：雙向鏈表的刪除鲸拥，也需要改變四個引用。
private void delete(Node<E> node) {
// node表示要刪除的元素
// 將node前一個元素的next指向node下一個元素
if (node.prev != null) node.prev.next = node.next;
// 將node下一個元素的pre指向node前一個元素
if (node.next != null) node.next.prev = node.prev;
// 將node的prev和next都置位null
node.prev = null;
node.next = null;
}
注意只考慮本節(jié)點元素情況僧免，沒有考慮鏈表頭的賦值刑赶。
五. LinkedList 類
5.1 成員屬性
// 集合數(shù)量
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;
}
}
通過一個雙向鏈表來記錄集合中的元素。
5.2 構(gòu)造函數(shù)
public LinkedList() {
}
public LinkedList(Collection<? extends E> c) {
this();
addAll(c);
}
LinkedList的構(gòu)造函數(shù)比較簡單懂衩，因為它不用想ArrayList那樣撞叨，要確定初始數(shù)組的長度。
5.3 添加元素
public boolean add(E e) {
linkLast(e);
return true;
}
void linkLast(E e) {
final Node<E> l = last;
final Node<E> newNode = new Node<>(l, e, null);
last = newNode;
if (l == null)
first = newNode;
else
l.next = newNode;
size++;
modCount++;
}
向鏈表尾添加一個新元素newNode,要進(jìn)行以下幾個步驟：
- 將鏈表尾last賦值給變量l浊洞，因為表尾last要指向新元素newNode
- 創(chuàng)建新元素newNode牵敷，根據(jù)Node的構(gòu)造函數(shù)，我們知道新元素newNode的prev指向l(即表尾),next還是為null法希。
- 將表尾last指向新元素newNode
- 將原表尾l的next指向新元素枷餐，這時要考慮一種情況，原表尾l為null苫亦，即整個鏈表是空的毛肋，那么這個時候怨咪，我們只需要將表頭first也指向新元素newNode就可以了。
- 集合數(shù)量size加1润匙，以及modCount自增表示集合已經(jīng)修改了诗眨。
注意，這里好像只改變了三個應(yīng)用孕讳，缺少了新元素newNode下一個元素的prev指向新元素newNode匠楚。這是因為在表尾，不存在下一個元素厂财。
public void add(int index, E element) {
checkPositionIndex(index);
if (index == size)
linkLast(element);
else
linkBefore(element, node(index));
}
在鏈表指定索引位置插入元素芋簿，如果index等于size，表示在表尾插入元素蟀苛，直接調(diào)用linkLast(element)方法益咬，否則先調(diào)用node(index)方法，找到index索引對應(yīng)元素node帜平，并將要添加元素element插入到元素node之前幽告。
Node<E> node(int index) {
// 如果index小于集合數(shù)量的一半，那么從表頭開始遍歷裆甩，一直到index位置冗锁。
// 否則從表尾開始遍歷，一直到index位置嗤栓。這樣我們每次最多遍歷size/2的次數(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;
}
}
這里用了個巧妙方法，先判斷index在集合的前一半還是后一半茉帅，決定從鏈表頭還是鏈表尾遍歷叨叙。
void linkBefore(E e, Node<E> succ) {
// e表示新添加的元素
// succ表示被插入的元素(即新元素插入到這個元素之前)
final Node<E> pred = succ.prev;
final Node<E> newNode = new Node<>(pred, e, succ);
succ.prev = newNode;
if (pred == null)
first = newNode;
else
pred.next = newNode;
size++;
modCount++;
}
在succ元素之前插入新元素e，要進(jìn)行以下幾個步驟：
- 將元素succ的前一個元素賦值給變量pred
- 創(chuàng)建新元素newNode堪澎。 新元素newNode的prev指向pred擂错，next指向succ。
- 將元素succ的prev指向新元素newNode樱蛤。
- 將元素pred的next指向新元素newNode钮呀。但是考慮一種情況，pred為null昨凡，即元素succ就是鏈表頭爽醋，那么新添加元素就變成新表頭了，first = newNode便脊。
- 集合數(shù)量size加1蚂四，以及modCount自增表示集合已經(jīng)修改了。
public boolean addAll(Collection<? extends E> c) {
return addAll(size, c);
}
public boolean addAll(int index, Collection<? extends E> c) {
checkPositionIndex(index);
Object[] a = c.toArray();
int numNew = a.length;
if (numNew == 0)
return false;
// pred表示index位置前一個元素，succ表示index位置元素
Node<E> pred, succ;
if (index == size) {
// 當(dāng)index == size時证杭，index位置的元素為null田度，它的前一個元素是表尾last元素
succ = null;
pred = last;
} else {
// 通過ode(index)方法，查找index位置元素
succ = node(index);
pred = succ.prev;
}
// 遍歷要插入集合c的元素解愤，將它們插入到本集合中
for (Object o : a) {
@SuppressWarnings("unchecked") E e = (E) o;
// 將新元素的prev指向前一個元素pred
Node<E> newNode = new Node<>(pred, e, null);
// pred為空表示，插入點在表頭乎莉，所以將新元素設(shè)置為表頭
if (pred == null)
first = newNode;
else
// 將前一個元素pred的next指向新元素newNode
pred.next = newNode;
// pred指向新元素送讲，然后繼續(xù)遍歷
pred = newNode;
}
// pred現(xiàn)在表示插入集合元素最后一個元素
// succ為空表示在表尾插入集合，那么插入集合中最后一個元素就成為新的表尾
if (succ == null) {
last = pred;
} else {
// 將插入集合中最后一個元素和插入點index位置元素進(jìn)行聯(lián)系惋啃。
pred.next = succ;
succ.prev = pred;
}
size += numNew;
modCount++;
return true;
}
在集合index位置前插入一個集合c中所有元素哼鬓。可以這么做：
- 先找到index位置元素succ边灭，和它前一個元素pred异希。
- 遍歷集合c中元素，將它們插入到元素pred之后绒瘦，即新元素newNode.prev = pred, pred.next = newNode称簿。然后將 pred = newNode; 再依次遍歷集合c。
- 遍歷完成之后惰帽，pred就指向集合c最后一個添加的元素憨降。這時就要讓它和index位置元素發(fā)生聯(lián)系。
當(dāng)然這個過程中還要考慮表頭和表尾的改變该酗。
5.4 刪除元素
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;
}
遍歷整個集合授药，找到與o相同元素，調(diào)用unlink方法刪除這個元素呜魄，如果沒有找打悔叽，就返回false。
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;
if (prev == null) {
first = next;
} else {
prev.next = next;
x.prev = null;
}
if (next == null) {
last = prev;
} else {
next.prev = prev;
x.next = null;
}
x.item = null;
size--;
modCount++;
return element;
}
這個方法和我們前面寫的雙向鏈表刪除方法一樣爵嗅。主要就是
- 被刪除元素x的前一個元素的next指向被刪除元素后一個元素娇澎。
- 被刪除元素x后一個元素的prev指向被刪除元素x前一個元素。
- 最后將刪除元素x的prev與next都設(shè)置為null操骡。
- 當(dāng)然要注意下表頭和表尾的判斷九火，如果被刪除元素x的prev為null，表示x是表頭册招，那么就要將表頭first指向元素x的下一個元素岔激。如果被刪除元素x的next為null，表示x是表尾是掰，那么就要將表尾last指向元素x前一個元素虑鼎。
public E remove(int index) {
checkElementIndex(index);
return unlink(node(index));
}
通過node(index)方法，獲取index索引對應(yīng)元素，然后調(diào)用unlink(Node<E> x) 方法刪除這個索引炫彩。
public void clear() {
// 遍歷鏈表匾七，將鏈表中的引用都置位null，方便垃圾回收器釋放內(nèi)存
for (Node<E> x = first; x != null; ) {
Node<E> next = x.next;
x.item = null;
x.next = null;
x.prev = null;
x = next;
}
first = last = null;
size = 0;
modCount++;
}
將鏈表中元素的引用都置位null江兢，方便垃圾回收器回收昨忆。
注 boolean removeAll(Collection<?> c)與boolean retainAll(Collection<?> c)都是使用AbstractCollection抽樣類的默認(rèn)實現(xiàn)。也就是通過迭代器Iterator來刪除集合中元素杉允。
5.5 替換元素
public E set(int index, E element) {
checkElementIndex(index);
Node<E> x = node(index);
E oldVal = x.item;
x.item = element;
return oldVal;
}
替換元素非常簡單邑贴，通過node(index)查找出元素，將元素中數(shù)據(jù)賦值給oldVal叔磷，再將新數(shù)據(jù)element設(shè)置到元素中拢驾，最后返回老數(shù)據(jù)oldVal。
5.5 查找元素
public int indexOf(Object o) {
int index = 0;
if (o == null) {
for (Node<E> x = first; x != null; x = x.next) {
if (x.item == null)
return index;
index++;
}
} else {
for (Node<E> x = first; x != null; x = x.next) {
if (o.equals(x.item))
return index;
index++;
}
}
return -1;
}
從表頭開始遍歷改基，查找第一個與o值相等元素繁疤，返回對應(yīng)索引，如果沒找到就返回-1 秕狰。
public int lastIndexOf(Object o) {
int index = size;
if (o == null) {
for (Node<E> x = last; x != null; x = x.prev) {
index--;
if (x.item == null)
return index;
}
} else {
for (Node<E> x = last; x != null; x = x.prev) {
index--;
if (o.equals(x.item))
return index;
}
}
return -1;
}
從表尾開始遍歷稠腊，查找第一個與o值相等元素，返回對應(yīng)索引封恰，如果沒找到就返回-1 麻养。
public E get(int index) {
checkElementIndex(index);
return node(index).item;
}
通過node(index)方法找到對應(yīng)索引的元素，然后返回元素的值诺舔。
public ListIterator<E> listIterator(int index) {
checkPositionIndex(index);
return new ListItr(index);
}
返回LinkedList內(nèi)部的一個迭代器鳖昌。這個類我們之后會詳細(xì)介紹。
5.6 其他重要方法
public Object[] toArray() {
Object[] result = new Object[size];
int i = 0;
for (Node<E> x = first; x != null; x = x.next)
result[i++] = x.item;
return result;
}
將集合轉(zhuǎn)成一個Object[]數(shù)組低飒，先創(chuàng)建一個長度為集合數(shù)量size的Object[]數(shù)組许昨，然后遍歷鏈表，將元素中數(shù)據(jù)item存放到數(shù)組中褥赊。
public <T> T[] toArray(T[] a) {
if (a.length < size)
a = (T[])java.lang.reflect.Array.newInstance(
a.getClass().getComponentType(), size);
int i = 0;
Object[] result = a;
for (Node<E> x = first; x != null; x = x.next)
result[i++] = x.item;
if (a.length > size)
a[size] = null;
return a;
}
將集合轉(zhuǎn)成T類型的數(shù)組糕档。如果數(shù)組a的長度小于集合數(shù)量size，那么就要創(chuàng)建一個新數(shù)組拌喉，再賦值給a速那，然后遍歷鏈表，將元素中數(shù)據(jù)item存放到數(shù)組a中尿背。
這里有個很詭異的地方端仰，就是if (a.length > size)這個判斷。我們知道數(shù)組a中 0 -- size-1 位置的元素都是集合中的田藐，那么從size位置開始之后的元素都是數(shù)組a原有的元素荔烧，這里不知道為什么單單將size位置元素置位null吱七。
六. LinkedList內(nèi)部類ListItr
6.1 成員屬性
// 代表當(dāng)前遍歷到的元素
private Node<E> lastReturned;
// 表示迭代器開始的元素
private Node<E> next;
// 表示元素next在鏈表中的位置，與next是相對應(yīng)的鹤竭。
private int nextIndex;
private int expectedModCount = modCount;
6.2 構(gòu)造函數(shù)
ListItr(int index) {
// 先通過LinkedList的node方法踊餐，查找index索引位置對于的元素，賦值給next
next = (index == size) ? null : node(index);
// 將index賦值給 nextIndex
nextIndex = index;
}
6.3 正向遍歷集合
public boolean hasNext() {
return nextIndex < size;
}
當(dāng)nextIndex小于集合數(shù)量size臀稚，說明集合還有元素沒有遍歷到吝岭。
public E next() {
checkForComodification();
if (!hasNext())
throw new NoSuchElementException();
lastReturned = next;
next = next.next;
nextIndex++;
return lastReturned.item;
}
將next賦值給lastReturned，再將next指向它的下一個元素烁涌，然后將nextIndex自增苍碟，最后返回當(dāng)前元素lastReturned的數(shù)據(jù)item。
6.4 反向遍歷
public boolean hasPrevious() {
return nextIndex > 0;
}
public E previous() {
checkForComodification();
if (!hasPrevious())
throw new NoSuchElementException();
lastReturned = next = (next == null) ? last : next.prev;
nextIndex--;
return lastReturned.item;
}
這里做了一個處理撮执，還記得在ListItr構(gòu)造函數(shù)中，如果index == size舷丹，那么next就賦值為null抒钱，所以這里當(dāng)next == null就從表尾開始向前遍歷。
6.5 返回索引
public int nextIndex() {
return nextIndex;
}
public int previousIndex() {
return nextIndex - 1;
}
這個已經(jīng)在AbstractList中的詳細(xì)介紹過了颜凯。
6.6 操作集合的方法
public void remove() {
checkForComodification();
if (lastReturned == null)
throw new IllegalStateException();
// 將當(dāng)前元素下一個元素賦值給lastNext
Node<E> lastNext = lastReturned.next;
// 調(diào)用LinkedList集合的unlink方法谋币，刪除當(dāng)前元素
unlink(lastReturned);
// 如果next == lastReturned，表示反向遍歷症概。
// 將next指向lastNext蕾额，因為lastNext的前一個就是原lastReturned前一個元素，所以不會有遺漏
if (next == lastReturned)
next = lastNext;
else
// 表示正向遍歷彼城，那么刪除當(dāng)前元素诅蝶，只有一個影響，就是集合數(shù)量減少了募壕。
// 而正向遍歷結(jié)束條件時nextIndex < size调炬，所以要將nextIndex自減。
// 而反向遍歷是結(jié)束條件是nextIndex > 0舱馅，所以不需要處理
nextIndex--;
lastReturned = null;
expectedModCount++;
}
public void set(E e) {
if (lastReturned == null)
throw new IllegalStateException();
checkForComodification();
// 超級簡單缰泡，就是將當(dāng)前元素的數(shù)據(jù)item設(shè)置成e
lastReturned.item = e;
}
public void add(E e) {
checkForComodification();
lastReturned = null;
// 如果next == null，就在鏈表尾插入元素e
if (next == null)
linkLast(e);
else
// 不然就在next元素之前插入元素e
linkBefore(e, next);
nextIndex++;
expectedModCount++;
}
總結(jié)
LinkedList不僅是一個List集合代嗤，它還是一個隊列棘钞，或者說是雙端隊列。
棧
棧是一個后入先出(LIFO)的數(shù)據(jù)結(jié)構(gòu)干毅，主要是三個方法：
- void push(E e); 向棧頂添加元素宜猜。
- E pop(); 移除棧頂元素，并返回它溶锭。
- E peek(); 查看棧頂元素宝恶。
隊列
隊列是一個先入先出(FIFO)的數(shù)據(jù)結(jié)構(gòu)，主要是三個方法：
- boolean offer(E e); 向隊列尾添加元素。
- E poll();移除隊列頭元素垫毙，并返回它霹疫。
- E peek(); 查看隊列頭元素。
雙端隊列
雙端隊列與普通隊列做比較综芥，它既可以在隊列頭添加元素丽蝎，也可以在隊列尾添加元素；既可以在隊列頭刪除元素膀藐，也可以在隊列尾刪除元素屠阻。
它的主要方法有六個：
- boolean offerFirst(E e); 向隊列頭添加元素。
- boolean offerLast(E e); 向隊列尾添加元素额各。
- E pollFirst();移除隊列頭元素国觉，并返回它。
- E pollLast();移除隊列尾元素虾啦，并返回它麻诀。
- E peekFirst(); 查看隊列頭元素。
- E peekLast(); 查看隊列尾元素傲醉。
AbstractSequentialList抽樣類
AbstractSequentialList這個類表示它的子類是使用鏈表這種數(shù)據(jù)結(jié)構(gòu)來存儲集合元素的蝇闭，而不是使用數(shù)組這種數(shù)據(jù)結(jié)構(gòu)。也就是說它沒有可隨機(jī)訪問能力硬毕。
單向鏈表和雙向鏈表
注意一下單向鏈表和雙向鏈表的插入和刪除呻引。
單向鏈表的插入和刪除最多改變兩個引用，而雙向鏈表的插入和刪除最多改變四個引用吐咳。
LinkedList 類
使用first表示雙向鏈表的表頭逻悠，使用last表示雙向鏈表的表尾。
