LinkedList的繼承結(jié)構(gòu)：
public class LinkedList<E>
extends AbstractSequentialList<E>
implements List<E>, Deque<E>, Cloneable, java.io.Serializable
Queue(interface):
隊(duì)列的父接口瞧挤，抽象方法：
boolean add(E e);// 插入元素到隊(duì)列焚碌，（超過容量會(huì)拋出異常）
boolean offer(E e);// 在不超出容量的情況下插入元素到隊(duì)列（超過容量返回false）
E remove();// 出列返回第一個(gè)元素，（空會(huì)拋出異常）
E poll();// 出列拌倍，返回第一個(gè)元素（空返回null）
E element();// 返回第一個(gè)元素，但是不出列（和peek的區(qū)別是這個(gè)方法會(huì)拋出異常）
E peek();// 返回第一個(gè)元素于个，但是不出列（空返回null）
Deque（interface）：雙端隊(duì)列
void addFirst(E e);
void addLast(E e);
boolean offerFirst(E e);
boolean offerLast(E e);
E removeFirst();
E removeLast();
E pollFirst();
E pollLast();
E getFirst();
E getLast();
E peekFirst();
E peekLast();
boolean removeFirstOccurrence(Object o);
boolean removeLastOccurrence(Object o);
結(jié)合隊(duì)列的接口解釋都能看懂上端隊(duì)列接口的抽象方法镐作；
LinkedList：
LinkedList的底層是雙端鏈表（隊(duì)列/雙端隊(duì)列），特點(diǎn)是增刪快呀酸，查找慢
LinkedList的類變量
// 存放數(shù)據(jù)的個(gè)數(shù)
transient int size = 0;
// 鏈表的頭
transient Node<E> first;
// 鏈表的尾
transient Node<E> last;
// 內(nèi)部類node
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;
}
}
LinkedList(Collection<? extends E> c):
使用集合構(gòu)造linkedList
public LinkedList(Collection<? extends E> c) {
this();
addAll(c);
}
public boolean addAll(Collection<? extends E> c) {
return addAll(size, c);
}
public boolean addAll(int index, Collection<? extends E> c) {
// 判斷index是否合法
checkPositionIndex(index);
// 將集合轉(zhuǎn)為數(shù)組
Object[] a = c.toArray();
int numNew = a.length;
if (numNew == 0)
return false;
Node<E> pred, succ;
if (index == size) { // 如果是構(gòu)造方法里進(jìn)來的
succ = null;
pred = last;
} else {
succ = node(index);
pred = succ.prev;
}
for (Object o : a) { // 遍歷這個(gè)數(shù)組（集合轉(zhuǎn)化的）
@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;
}
if (succ == null) { // 如果是構(gòu)造方法進(jìn)來的凉蜂，
last = pred;
} else {
pred.next = succ;
succ.prev = pred;
}
size += numNew;
modCount++;
return true;
}
// 判斷下標(biāo)是否合法
private void checkPositionIndex(int index) {
if (!isPositionIndex(index))
throw new IndexOutOfBoundsException(outOfBoundsMsg(index));
}
private boolean isPositionIndex(int index) {
return index >= 0 && index <= size;
}
簡(jiǎn)單說下由集合構(gòu)造的LinkedList，將集合轉(zhuǎn)為數(shù)組性誉，在遍歷數(shù)組窿吩，創(chuàng)建node拼接到first和last；
add（E e）：
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++;
}
LinkedList沒有數(shù)量限制错览，所以不需要考慮容量大小纫雁，直接新建一個(gè)node，拼接到最后倾哺；
remove():
直接調(diào)用remove（）轧邪，返回鏈表第一個(gè)元素，first指針后移
public E remove() {
return removeFirst();
}
public E removeFirst() {
final Node<E> f = first;
if (f == null)
throw new NoSuchElementException();
return unlinkFirst(f);
}
private E unlinkFirst(Node<E> f) {
// assert f == first && f != null;
final E element = f.item;
final Node<E> next = f.next;
f.item = null;
f.next = null; // help GC
first = next;
if (next == null)
last = null;
else
next.prev = null;
size--;
modCount++;
return element;
}
remove(Object o)：
刪除指定的元素
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;
}
// 刪除指定元素的主要代碼
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;
}
unLink（）主要思路：找到當(dāng)前unLink節(jié)點(diǎn)x的pre和next羞海，如果pre==null忌愚，說明x是第一個(gè)節(jié)點(diǎn)，將first = first.next就可以刪除第一個(gè)節(jié)點(diǎn)了却邓；如果next==null硕糊，說明x是最后一個(gè)節(jié)點(diǎn)，直接將last==null即可申尤；如果在中間癌幕，將前面一個(gè)相鄰的節(jié)點(diǎn)和后面一個(gè)相鄰的節(jié)點(diǎn)連接起來；因?yàn)殒湵硎请p向的昧穿，所以需要兩次連接操作勺远；（記得置null便于回收內(nèi)存）
