1.简介
实现List接口，继承添加，修改，遍历，包含等父类方法。实现Deque接口，Deque双端队列，支持LinkedList可当队列使用，增加队列相关方法。继承AbstractSequentialList，AbstractSequentialList继承AbstractList实现Cloneable接口，可以被克隆。实现java.io.Serializable接口，支持序列化。
2.成员属性
//链表长度
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;
}
}
3.构造方法
/**
* 空构造
*/
public LinkedList() {
}
/**
* 支持从集合构造
*/
public LinkedList(Collection<? extends E> c) {
this();
addAll(c);
}
4.方法解析
void linkFirst(E e)
/**
* 添加元素到链表头部
*/
private void linkFirst(E e) {
//获取到头节点
final Node<E> f = first;
//构造一个后继节点为头节点的新节点
final Node<E> newNode = new Node<>(null, e, f);
//将新节点更新为头节点
first = newNode;
//说明链表为空，将新节点置为尾部节点，否则将l的前置节点置为新节点
if (f == null)
last = newNode;
else
f.prev = newNode;
size++;
modCount++;
}
void linkLast(E e)
/**
* 添加元素到链表尾部
*/
void linkLast(E e) {
//获取尾巴节点l
final Node<E> l = last;
//构造一个前驱节点为l的新节点
final Node<E> newNode = new Node<>(l, e, null);
//将新节点置为尾结点
last = newNode;
//链表为空时，将新节点同时置为尾结点，否则将l的后继节点置为新节点
if (l == null)
first = newNode;
else
l.next = newNode;
size++;
modCount++;
}
void linkBefore(E e, Node succ)
/**
* 在指定元素前面添加元素
*/
void linkBefore(E e, Node<E> succ) {
// assert succ != null;
// 获取传入节点的前置节点
final Node<E> pred = succ.prev;
//构造新节点，前置节点指向pred，后继节点指向succ
final Node<E> newNode = new Node<>(pred, e, succ);
succ.prev = newNode;
//pred为null说明succ为头节点，将新节点置为头节点
if (pred == null)
first = newNode;
else
pred.next = newNode;//更新pred的后继节点为新节点
size++;
modCount++;
}
E unlinkFirst(Node 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;
//如果next为null，说明该链表只有一个节点，last置为null
if (next == null)
last = null;
else
next.prev = null;//后继节点为头节点，头节点的前置节点为null
size--;
modCount++;
return element;
}
E unlinkLast(Node f)
/**
* 删除链表尾部元素，并返回该元素
*/
private E unlinkLast(Node<E> l) {
// assert l == last && l != null;
final E element = l.item;
// 获取前置节点
final Node<E> prev = l.prev;
l.item = null;
l.prev = null; // help GC
// 将前置节点置为尾结点
last = prev;
// 如果prev为null，说明该链表只有一个节点，first置为null
if (prev == null)
first = null;
else
prev.next = null;// 前置节点为尾节点，尾结点的后置节点为null
size--;
modCount++;
return element;
}
E unlinkLast(Node f)
/**
* 删除指定元素，并返回该元素
*/
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;
}
E unlinkLast(Node f)
/**
* 添加元素，默认添加到链表尾部
*/
public boolean add(E e) {
linkLast(e);
return true;
}
boolean addAll(Collection<? extends E> c)
/**
* 添加集合元素到链表，默认添加到链表尾部
*/
public boolean addAll(Collection<? extends E> c) {
return addAll(size, c);
}
/**
* 添加集合元素到链表，添加到指定索引位置
*/
public boolean addAll(int index, Collection<? extends E> c) {
//校验index是否合法
checkPositionIndex(index);
Object[] a = c.toArray();
int numNew = a.length;
if (numNew == 0)
return false;
//插入位置的前驱节点和后继节点
Node<E> pred, succ;
//从尾部插入，前驱节点为last,后继节点为null
if (index == size) {
succ = null;
pred = last;
} else {//否则node(index)获取到后继节点，
succ = node(index);
pred = succ.prev;
}
for (Object o : a) {
//新构建一个前驱节点为pred,后继节点为null的Node
@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) {
last = pred;
} else {//否则将链表连接起来
pred.next = succ;
succ.prev = pred;
}
size += numNew;
modCount++;
return true;
}
boolean 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;
}
4.队列相关方法解析
E getFirst()
/**
* 获取第一个元素
*/
public E getFirst() {
final Node<E> f = first;
if (f == null)
throw new NoSuchElementException();
return f.item;
}
E getLast()
/**
* 获取最后一个元素
*/
public E getLast() {
final Node<E> l = last;
if (l == null)
throw new NoSuchElementException();
return l.item;
}
E peek()
/**
* 获取第一个元素
*/
public E peek() {
final Node<E> f = first;
//返回第一个元素，但不删除
return (f == null) ? null : f.item;
}
E poll()
/**
* 弹出第一个元素
*/
public E poll() {
final Node<E> f = first;
//返回第一个元素，并删除该元素
return (f == null) ? null : unlinkFirst(f);
}
E remove()
/**
* 删除第一个元素
*/
public E remove() {
return removeFirst();
}
public E removeFirst() {
final Node<E> f = first;
if (f == null)
throw new NoSuchElementException();
return unlinkFirst(f);
}
peek()与remove()都是删除第一个元素并返回 区别在于：若元素不存在poll会返回null，remove会抛出异常。
6.总结
底层为双向链表，而非数组可以当做队列使用线程不安全随机访问效率低，但增删效率高(因为不需要拷贝)有序可重复
