LinkedList
- 在Java.util包下
- 繼承自AbstractSequentialList
- 實(shí)現(xiàn) List 接口，能對(duì)它進(jìn)行隊(duì)列操作吼旧。
- 實(shí)現(xiàn) Deque 接口惯雳，即能將LinkedList當(dāng)作雙端隊(duì)列使用畦幢。
- 實(shí)現(xiàn)了Cloneable接口返奉，即覆蓋了函數(shù)clone()污尉，能克隆锐朴。
- 實(shí)現(xiàn)java.io.Serializable接口酱酬，這意味著LinkedList支持序列化挑社，能通過(guò)序列化去傳輸吼肥。
- 允許包含null值
- 迭代器可以快速報(bào)錯(cuò)
- 非線程安全的动猬，如果在多線程中使用（修改），需要在外部作同步處理。
LinkedList是一種可以在任何位置進(jìn)行高效地插入和移除操作的有序序列慈俯，它是基于雙向鏈表實(shí)現(xiàn)的刑峡。內(nèi)部有三個(gè)變量阳似，size表示鏈表中元素的個(gè)數(shù)， first指向鏈表頭部玲献，last指向鏈表尾部眠砾。 結(jié)構(gòu)圖如下圖所示
LinkedList.png
下面是LinkedList中Node節(jié)點(diǎn)的定義，Node類是LinkedList的靜態(tài)內(nèi)部類淤井。
private static class Node<E> {
E item; // 當(dāng)前節(jié)點(diǎn)所存數(shù)據(jù)
Node<E> next; // 當(dāng)前節(jié)點(diǎn)的下一個(gè)節(jié)點(diǎn)
Node<E> prev; // 當(dāng)前節(jié)點(diǎn)的前一個(gè)節(jié)點(diǎn)
Node(Node<E> prev, E element, Node<E> next) {
this.item = element;
this.next = next;
this.prev = prev;
}
}
構(gòu)造方法（Construction method）
LinkedList提供了兩種種方式的構(gòu)造器，構(gòu)造一個(gè)空列表游两、以及構(gòu)造一個(gè)包含指定collection的元素的列表漩绵，
這些元素按照該collection的迭代器返回的順序排列的止吐。
public LinkedList() {
}
public LinkedList(Collection<? extends E> c) {
this();
addAll(c); // 調(diào)用addAll方法，構(gòu)建一個(gè)包含指定集合c的列表
}
添加元素
因?yàn)長(zhǎng)inkedList即實(shí)現(xiàn)了List接口，又實(shí)現(xiàn)了Deque接口，所以LinkedList既可以添加將元素添加到尾部饭望，也可以將元素添加到指定索引位置，還可以添加添加整個(gè)集合雏节；另外既可以在頭部添加，又可以在尾部添加。
//添加元素作為第一個(gè)元素
public void addFirst(E e) {
linkFirst(e);
}
//店家元素作為最后一個(gè)元素
public void addLast(E e) {
linkLast(e);
}
//使用對(duì)應(yīng)參數(shù)作為第一個(gè)節(jié)點(diǎn)，內(nèi)部使用
private void linkFirst(E e) {
final Node<E> f = first;//得到首節(jié)點(diǎn)
final Node<E> newNode = new Node<>(null, e, f);//創(chuàng)建一個(gè)節(jié)點(diǎn)
first = newNode; //更新首節(jié)點(diǎn)
if (f == null)
last = newNode; //如果之前首節(jié)點(diǎn)為空(size==0)拓轻，那么尾節(jié)點(diǎn)就是首節(jié)點(diǎn)
else
f.prev = newNode; //如果之前首節(jié)點(diǎn)不為空斯撮，之前的首節(jié)點(diǎn)的前一個(gè)節(jié)點(diǎn)為當(dāng)前首節(jié)點(diǎn)
size++; //長(zhǎng)度+1
modCount++; //修改次數(shù)+1
}
//使用對(duì)應(yīng)參數(shù)作為尾節(jié)點(diǎn)
void linkLast(E e) {
final Node<E> l = last; //得到尾節(jié)點(diǎn)
final Node<E> newNode = new Node<>(l, e, null);//使用參數(shù)創(chuàng)建一個(gè)節(jié)點(diǎn)
last = newNode; //設(shè)置尾節(jié)點(diǎn)
if (l == null)
first = newNode; //如果之前尾節(jié)點(diǎn)為空(size==0)，首節(jié)點(diǎn)即尾節(jié)點(diǎn)
else
l.next = newNode; //如果之前尾節(jié)點(diǎn)不為空扶叉，之前的尾節(jié)點(diǎn)的后一個(gè)就是當(dāng)前的尾節(jié)點(diǎn)
size++;
modCount++;
}
//在非空節(jié)點(diǎn)succ之前插入元素E勿锅。
void linkBefore(E e, Node<E> succ) {
final Node<E> pred = succ.prev;//獲取前一個(gè)節(jié)點(diǎn)
final Node<E> newNode = new Node<>(pred, e, succ);//使用參數(shù)創(chuàng)建新的節(jié)點(diǎn)
succ.prev = newNode;//當(dāng)前節(jié)點(diǎn)指向新的節(jié)點(diǎn)
if (pred == null)
first = newNode;//如果前一個(gè)節(jié)點(diǎn)為null，新的節(jié)點(diǎn)就是首節(jié)點(diǎn)
else
pred.next = newNode;//如果存在前節(jié)點(diǎn)枣氧，那么前節(jié)點(diǎn)的向后指向新節(jié)點(diǎn)
size++;
modCount++;
}
//添加指定集合的元素到列表溢十，默認(rèn)從最后開(kāi)始添加
public boolean addAll(Collection<? extends E> c) {
return addAll(size, c);//size表示最后一個(gè)位置
}
/*
從指定位置（而不是下標(biāo)！下標(biāo)即索引從0開(kāi)始达吞，位置可以看做從1開(kāi)始张弛，其實(shí)也是0）后面添加指定集合的元素到列表中，只要有至少一次添加就會(huì)返回true
index換成position應(yīng)該會(huì)更好理解，所以也就是從索引為index(position)的元素的前面索引為index-1的后面添加吞鸭！
當(dāng)然位置可以為0啊寺董，為0的時(shí)候就是從位置0(雖然它不存在)后面開(kāi)始添加嘛，所以理所當(dāng)然就是添加到第一個(gè)位置（位置1的前面）的前面
比如列表：0 1 2 3刻剥，如果此處index=4(實(shí)際索引為3)遮咖，就是在元素3后面添加；如果index=3(實(shí)際索引為2)造虏，就在元素2后面添加御吞。
*/
public boolean addAll(int index, Collection<? extends E> c) {
checkPositionIndex(index); //檢查索引是否正確（0<=index<=size）
Object[] a = c.toArray(); //得到元素?cái)?shù)組
int numNew = a.length; //得到元素個(gè)數(shù)
if (numNew == 0) //若沒(méi)有元素要添加，直接返回false
return false;
Node<E> pred, succ;
if (index == size) { //如果是在末尾開(kāi)始添加漓藕，當(dāng)前節(jié)點(diǎn)后一個(gè)節(jié)點(diǎn)初始化為null陶珠，前一個(gè)節(jié)點(diǎn)為尾節(jié)點(diǎn)
succ = null; //這里可以看做node(index)，不過(guò)index=size了（index最大只能是size-1）享钞，所以這里的succ只能=null背率，也方便后面判斷
pred = last;
} else { //如果不是從末尾開(kāi)始添加，當(dāng)前位置的節(jié)點(diǎn)為指定位置的節(jié)點(diǎn)嫩与，前一個(gè)節(jié)點(diǎn)為要添加的節(jié)點(diǎn)的前一個(gè)節(jié)點(diǎn)
succ = node(index); //添加好元素后(整個(gè)新加的)的后一個(gè)節(jié)點(diǎn)
pred = succ.prev;
}
//遍歷數(shù)組并添加到列表中
for (Object o : a) {
@SuppressWarnings("unchecked") E e = (E) o;
Node<E> newNode = new Node<>(pred, e, null);//創(chuàng)建一個(gè)節(jié)點(diǎn)寝姿，向前指向上面得到的前節(jié)點(diǎn)
if (pred == null)
first = newNode; //若當(dāng)前節(jié)點(diǎn)為null，則新加的節(jié)點(diǎn)為首節(jié)點(diǎn)
else
pred.next = newNode;//如果存在前節(jié)點(diǎn)划滋，前節(jié)點(diǎn)會(huì)向后指向新加的節(jié)點(diǎn)
pred = newNode; //新加的節(jié)點(diǎn)成為前一個(gè)節(jié)點(diǎn)
}
if (succ == null) {
//pred.next = null //加上這句也可以更好的理解
last = pred; //如果是從最后開(kāi)始添加的饵筑，則最后添加的節(jié)點(diǎn)成為尾節(jié)點(diǎn)
} else {
pred.next = succ; //如果不是從最后開(kāi)始添加的，則最后添加的節(jié)點(diǎn)向后指向之前得到的后續(xù)第一個(gè)節(jié)點(diǎn)
succ.prev = pred; //當(dāng)前处坪，后續(xù)的第一個(gè)節(jié)點(diǎn)也應(yīng)改為向前指向最后一個(gè)添加的節(jié)點(diǎn)
}
size += numNew;
modCount++;
return true;
}
//將指定的元素(E element)插入到列表的指定位置(index)
public void add(int index, E element) {
checkPositionIndex(index); //index >= 0 && index <= size
if (index == size)
linkLast(element); //尾插入
else
linkBefore(element, node(index)); //中間插入
}
linkBefore的添加步驟：
- 創(chuàng)建newNode節(jié)點(diǎn)根资，將newNode的后繼指針指向succ，前驅(qū)指針指向pred
- 將succ的前驅(qū)指針指向newNode
- 根據(jù)pred是否為null同窘，進(jìn)行不同操作玄帕。
- 如果pred為null，說(shuō)明該節(jié)點(diǎn)插入在頭節(jié)點(diǎn)之前想邦，要重置first頭節(jié)點(diǎn)
- 如果pred不為null裤纹，那么直接將pred的后繼指針指向newNode即可
addAll的添加步驟：
- 檢查index索引范圍
- 得到集合數(shù)據(jù)
- 得到插入位置的前驅(qū)和后繼節(jié)點(diǎn)
- 遍歷數(shù)據(jù)，將數(shù)據(jù)插入到指定位置
刪除元素
同樣的LinkedList也提供了很多方法來(lái)刪除元素
// 刪除首節(jié)點(diǎn)并返回刪除前首節(jié)點(diǎn)的值丧没，內(nèi)部使用 (f == first && f != null)
private E unlinkFirst(Node<E> f) {
final E element = f.item; // 獲取首節(jié)點(diǎn)的值
final Node<E> next = f.next; // 獲取首節(jié)點(diǎn)的后一個(gè)節(jié)點(diǎn)
f.item = null;
f.next = null; // help GC
first = next; // 更新首節(jié)點(diǎn)
if (next == null) //如果不存在下一個(gè)節(jié)點(diǎn)鹰椒，則首尾都為null
last = null;
else
next.prev = null; //如果存在下一個(gè)節(jié)點(diǎn)，那它的前指針為null
size--;
modCount++;
return element;
}
// 刪除尾節(jié)點(diǎn)呕童，并返回尾節(jié)點(diǎn)的元素 （assert l == last && l != null）
private E unlinkLast(Node<E> l) {
final E element = l.item;//獲取尾節(jié)點(diǎn)的值
final Node<E> prev = l.prev;//獲取尾節(jié)點(diǎn)前一個(gè)節(jié)點(diǎn)
l.item = null;
l.prev = null; // help GC
last = prev; //前一個(gè)節(jié)點(diǎn)成為新的尾節(jié)點(diǎn)
if (prev == null)
first = null; //如果前一個(gè)節(jié)點(diǎn)不存在漆际，則首尾都為null
else
prev.next = null;//如果前一個(gè)節(jié)點(diǎn)存在，先后指向null
size--;
modCount++;
return element;
}
// 刪除指定節(jié)點(diǎn)x并返回節(jié)點(diǎn)的值（x != null）
E unlink(Node<E> x) {
//獲取當(dāng)前值和前后節(jié)點(diǎn)
final E element = x.item;
final Node<E> next = x.next;
final Node<E> prev = x.prev;
if (prev == null) {
first = next; //如果前一個(gè)節(jié)點(diǎn)為空(如當(dāng)前節(jié)點(diǎn)為首節(jié)點(diǎn))夺饲，后一個(gè)節(jié)點(diǎn)成為新的首節(jié)點(diǎn)
} else {
prev.next = next;//如果前一個(gè)節(jié)點(diǎn)不為空奸汇，那么他先后指向當(dāng)前的下一個(gè)節(jié)點(diǎn)
x.prev = null; //help GC
}
if (next == null) {
last = prev; //如果后一個(gè)節(jié)點(diǎn)為空(如當(dāng)前節(jié)點(diǎn)為尾節(jié)點(diǎn))施符，當(dāng)前節(jié)點(diǎn)前一個(gè)成為新的尾節(jié)點(diǎn)
} else {
next.prev = prev;//如果后一個(gè)節(jié)點(diǎn)不為空，后一個(gè)節(jié)點(diǎn)向前指向當(dāng)前的前一個(gè)節(jié)點(diǎn)
x.next = null; //help GC
}
x.item = null; //help GC
size--;
modCount++;
return element;
}
//刪除第一個(gè)元素并返回刪除的元素
public E removeFirst() {
final Node<E> f = first;//得到第一個(gè)節(jié)點(diǎn)
if (f == null) //如果為空擂找，拋出異常
throw new NoSuchElementException();
return unlinkFirst(f);
}
//刪除最后一個(gè)元素并返回刪除的值
public E removeLast() {
final Node<E> l = last;//得到最后一個(gè)節(jié)點(diǎn)
if (l == null) //如果為空操刀，拋出異常
throw new NoSuchElementException();
return unlinkLast(l);
}
序列化方法
private static final long serialVersionUID = 876323262645176354L;
//序列化：將linkedList的“大小，所有的元素值”都寫(xiě)入到輸出流中
private void writeObject(java.io.ObjectOutputStream s)
throws java.io.IOException {
s.defaultWriteObject();
s.writeInt(size);
for (Node<E> x = first; x != null; x = x.next)
s.writeObject(x.item);
}
//反序列化：先將LinkedList的“大小”讀出婴洼，然后將“所有的元素值”讀出
@SuppressWarnings("unchecked")
private void readObject(java.io.ObjectInputStream s)
throws java.io.IOException, ClassNotFoundException {
s.defaultReadObject();
int size = s.readInt();
for (int i = 0; i < size; i++)
linkLast((E)s.readObject()); //以尾插入的方式
}
隊(duì)列操作
//提供普通隊(duì)列和雙向隊(duì)列的功能，當(dāng)然撼嗓，也可以實(shí)現(xiàn)棧柬采，F(xiàn)IFO，F(xiàn)ILO
//出隊(duì)（從前端）且警，獲得第一個(gè)元素粉捻，不存在會(huì)返回null，不會(huì)刪除元素（節(jié)點(diǎn)）
public E peek() {
final Node<E> f = first;
return (f == null) ? null : f.item;
}
//出隊(duì)（從前端）斑芜，不刪除元素肩刃，若為null會(huì)拋出異常而不是返回null
public E element() {
return getFirst();
}
//出隊(duì)（從前端），如果不存在會(huì)返回null杏头，存在的話會(huì)返回值并移除這個(gè)元素（節(jié)點(diǎn)）
public E poll() {
final Node<E> f = first;
return (f == null) ? null : unlinkFirst(f);
}
//出隊(duì)（從前端）盈包，如果不存在會(huì)拋出異常而不是返回null，存在的話會(huì)返回值并移除這個(gè)元素（節(jié)點(diǎn)）
public E remove() {
return removeFirst();
}
//入隊(duì)（從后端）醇王，始終返回true
public boolean offer(E e) {
return add(e);
}
//入隊(duì)（從前端）呢燥，始終返回true
public boolean offerFirst(E e) {
addFirst(e);
return true;
}
//入隊(duì)（從后端），始終返回true
public boolean offerLast(E e) {
addLast(e);//linkLast(e)
return true;
}
//出隊(duì)（從前端）寓娩，獲得第一個(gè)元素叛氨，不存在會(huì)返回null，不會(huì)刪除元素（節(jié)點(diǎn)）
public E peekFirst() {
final Node<E> f = first;
return (f == null) ? null : f.item;
}
//出隊(duì)（從后端）棘伴，獲得最后一個(gè)元素寞埠，不存在會(huì)返回null，不會(huì)刪除元素（節(jié)點(diǎn)）
public E peekLast() {
final Node<E> l = last;
return (l == null) ? null : l.item;
}
//出隊(duì)（從前端）焊夸，獲得第一個(gè)元素仁连，不存在會(huì)返回null，會(huì)刪除元素（節(jié)點(diǎn)）
public E pollFirst() {
final Node<E> f = first;
return (f == null) ? null : unlinkFirst(f);
}
//出隊(duì)（從后端）阱穗，獲得最后一個(gè)元素怖糊，不存在會(huì)返回null，會(huì)刪除元素（節(jié)點(diǎn)）
public E pollLast() {
final Node<E> l = last;
return (l == null) ? null : unlinkLast(l);
}
//入棧颇象，從前面添加
public void push(E e) {
addFirst(e);
}
//出棧伍伤，返回棧頂元素，從前面移除（會(huì)刪除）
public E pop() {
return removeFirst();
}
迭代器
//返回迭代器
public Iterator<E> descendingIterator() {
return new DescendingIterator();
}
//迭代器
private class DescendingIterator implements Iterator<E> {
private final ListItr itr = new ListItr(size());
public boolean hasNext() {
return itr.hasPrevious();
}
public E next() {
return itr.previous();
}
public void remove() {
itr.remove();
}
}
public ListIterator<E> listIterator(int index) {
checkPositionIndex(index);
return new ListItr(index);
}
private class ListItr implements ListIterator<E> {
private Node<E> lastReturned;
private Node<E> next;
private int nextIndex;
private int expectedModCount = modCount;//保存當(dāng)前modCount遣钳，確保fail-fast機(jī)制
ListItr(int index) {
next = (index == size) ? null : node(index);//得到當(dāng)前索引指向的next節(jié)點(diǎn)
nextIndex = index;
}
public boolean hasNext() { // 判斷后面是否還有元素
return nextIndex < size;
}
public E next() { //獲取下一個(gè)節(jié)點(diǎn)
checkForComodification();
if (!hasNext())
throw new NoSuchElementException();
lastReturned = next;
next = next.next;
nextIndex++;
return lastReturned.item;
}
public boolean hasPrevious() {
return nextIndex > 0;
}
//獲取前一個(gè)節(jié)點(diǎn)扰魂，將next節(jié)點(diǎn)向前移
public E previous() {
checkForComodification();
if (!hasPrevious())
throw new NoSuchElementException();
lastReturned = next = (next == null) ? last : next.prev;
nextIndex--;
return lastReturned.item;
}
public int nextIndex() {
return nextIndex;
}
public int previousIndex() {
return nextIndex - 1;
}
public void remove() {
checkForComodification();
if (lastReturned == null)
throw new IllegalStateException();
Node<E> lastNext = lastReturned.next;
unlink(lastReturned);
if (next == lastReturned)
next = lastNext;
else
nextIndex--;
lastReturned = null;
expectedModCount++;
}
public void set(E e) {
if (lastReturned == null)
throw new IllegalStateException();
checkForComodification();
lastReturned.item = e;
}
public void add(E e) {
checkForComodification();
lastReturned = null;
if (next == null)
linkLast(e);
else
linkBefore(e, next);
nextIndex++;
expectedModCount++;
}
public void forEachRemaining(Consumer<? super E> action) {
Objects.requireNonNull(action);
while (modCount == expectedModCount && nextIndex < size) {
action.accept(next.item);
lastReturned = next;
next = next.next;
nextIndex++;
}
checkForComodification();
}
final void checkForComodification() {
if (modCount != expectedModCount)
throw new ConcurrentModificationException();
}
}
在ListIterator的構(gòu)造器中，得到了當(dāng)前位置的節(jié)點(diǎn)，就是變量next劝评。next()方法返回當(dāng)前節(jié)點(diǎn)的值并將next指向其后繼節(jié)點(diǎn)姐直，previous()方法返回當(dāng)前節(jié)點(diǎn)的前一個(gè)節(jié)點(diǎn)的值并將next節(jié)點(diǎn)指向其前驅(qū)節(jié)點(diǎn)。
由于Node是一個(gè)雙向節(jié)點(diǎn)蒋畜，所以這用了一個(gè)節(jié)點(diǎn)就可以實(shí)現(xiàn)從前向后迭代和從后向前迭代声畏。另外在ListIterator初始時(shí)，exceptedModCount保存了當(dāng)前的modCount姻成，如果在迭代期間插龄，有操作改變了鏈表的底層結(jié)構(gòu)，那么再操作迭代器的方法時(shí)將會(huì)拋出ConcurrentModificationException科展。
fail-fast
fail-fast 機(jī)制是java集合(Collection)中的一種錯(cuò)誤機(jī)制均牢。當(dāng)多個(gè)線程對(duì)同一個(gè)集合的內(nèi)容進(jìn)行操作時(shí)，就可能會(huì)產(chǎn)生fail-fast事件才睹。例如：當(dāng)某一個(gè)線程A通過(guò)iterator去遍歷某集合的過(guò)程中徘跪，若該集合的內(nèi)容被其他線程所改變了；那么線程A訪問(wèn)集合時(shí)琅攘，就會(huì)拋出ConcurrentModificationException異常垮庐，產(chǎn)生fail-fast事件。
快速失斘肭佟（fail—fast）
在用迭代器遍歷一個(gè)集合對(duì)象時(shí)突硝，如果遍歷過(guò)程中對(duì)集合對(duì)象的內(nèi)容進(jìn)行了修改（增加、刪除置济、修改）解恰，則會(huì)拋出Concurrent Modification Exception。
原理：迭代器在遍歷時(shí)直接訪問(wèn)集合中的內(nèi)容浙于，并且在遍歷過(guò)程中使用一個(gè) modCount 變量护盈。集合在被遍歷期間如果內(nèi)容發(fā)生變化，就會(huì)改變modCount的值羞酗。每當(dāng)?shù)魇褂胔ashNext()/next()遍歷下一個(gè)元素之前腐宋，都會(huì)檢測(cè)modCount變量是否為expectedmodCount值，是的話就返回遍歷檀轨；否則拋出異常胸竞，終止遍歷。
注意：這里異常的拋出條件是檢測(cè)到 modCount参萄！=expectedmodCount 這個(gè)條件卫枝。如果集合發(fā)生變化時(shí)修改modCount值剛好又設(shè)置為了expectedmodCount值，則異常不會(huì)拋出讹挎。因此校赤，不能依賴于這個(gè)異常是否拋出而進(jìn)行并發(fā)操作的編程吆玖，這個(gè)異常只建議用于檢測(cè)并發(fā)修改的bug。
場(chǎng)景：java.util包下的集合類都是快速失敗的马篮，不能在多線程下發(fā)生并發(fā)修改（迭代過(guò)程中被修改）沾乘。
安全失敗（fail—safe）
采用安全失敗機(jī)制的集合容器浑测，在遍歷時(shí)不是直接在集合內(nèi)容上訪問(wèn)的翅阵，而是先復(fù)制原有集合內(nèi)容，在拷貝的集合上進(jìn)行遍歷迁央。
原理：由于迭代時(shí)是對(duì)原集合的拷貝進(jìn)行遍歷掷匠，所以在遍歷過(guò)程中對(duì)原集合所作的修改并不能被迭代器檢測(cè)到，所以不會(huì)觸發(fā)Concurrent Modification Exception漱贱。
缺點(diǎn)：基于拷貝內(nèi)容的優(yōu)點(diǎn)是避免了Concurrent Modification Exception，但同樣地夭委，迭代器并不能訪問(wèn)到修改后的內(nèi)容幅狮，即：迭代器遍歷的是開(kāi)始遍歷那一刻拿到的集合拷貝，在遍歷期間原集合發(fā)生的修改迭代器是不知道的株灸。
場(chǎng)景：java.util.concurrent包下的容器都是安全失敗崇摄，可以在多線程下并發(fā)使用，并發(fā)修改慌烧。
其他方法
//獲取第一個(gè)元素
public E getFirst() {
final Node<E> f = first;//得到首節(jié)點(diǎn)
if (f == null) //如果為空逐抑，拋出異常
throw new NoSuchElementException();
return f.item;
}
//獲取最后一個(gè)元素
public E getLast() {
final Node<E> l = last;//得到尾節(jié)點(diǎn)
if (l == null) //如果為空，拋出異常
throw new NoSuchElementException();
return l.item;
}
//檢查是否包含某個(gè)元素屹蚊，返回bool
public boolean contains(Object o) {
return indexOf(o) != -1;//返回指定元素的索引位置厕氨，不存在就返回-1，然后比較返回bool值
}
//返回列表長(zhǎng)度
public int size() {
return size;
}
//清空表
public void clear() { // help GC
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++;
}
//獲取指定索引的節(jié)點(diǎn)的值
public E get(int index) {
checkElementIndex(index);
return node(index).item;
}
//修改指定索引的值并返回之前的值
public E set(int index, E element) {
checkElementIndex(index); // 檢查下標(biāo)是否合法
Node<E> x = node(index);
E oldVal = x.item;
x.item = element;
return oldVal;
}
//獲取指定位置的節(jié)點(diǎn)
Node<E> node(int index) {
if (index < (size >> 1)) {//如果位置索引小于列表長(zhǎng)度的一半(或一半減一)汹粤，從前面開(kāi)始遍歷命斧；
Node<E> x = first;//index==0時(shí)不會(huì)循環(huán)，直接返回first
for (int i = 0; i < index; i++)
x = x.next;
return x;
} else { // 否則嘱兼，從后面開(kāi)始遍歷
Node<E> x = last;
for (int i = size - 1; i > index; i--)
x = x.prev;
return x;
}
}
//獲取指定元素從first開(kāi)始的索引位置国葬，不存在就返回-1
//這里不能按條件雙向找了，所以通常根據(jù)索引獲得元素的速度比通過(guò)元素獲得索引的速度快
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;
}
//獲取指定元素從first開(kāi)始最后出現(xiàn)的索引芹壕，不存在就返回-1
//但實(shí)際查找是從last開(kāi)始的
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;
}
//返回此 LinkedList實(shí)例的淺拷貝
public Object clone() {
LinkedList<E> clone = superClone();
clone.first = clone.last = null;
clone.size = 0;
clone.modCount = 0;
for (Node<E> x = first; x != null; x = x.next)
clone.add(x.item);
return clone;
}
//返回一個(gè)包含LinkedList中所有元素值的數(shù)組
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;
}
//如果給定的參數(shù)數(shù)組長(zhǎng)度足夠汇四，則將ArrayList中所有元素按序存放于參數(shù)數(shù)組中，并返回
//如果給定的參數(shù)數(shù)組長(zhǎng)度小于LinkedList的長(zhǎng)度踢涌，則返回一個(gè)新分配的通孽、長(zhǎng)度等于LinkedList長(zhǎng)度的、包含LinkedList中所有元素的新數(shù)組
@SuppressWarnings("unchecked")
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;
}
