概述
LinkedList继承自AbstrackSequentialList并实现了List接口以及Deque双向队列接口，因而 LinkedList 岂但领有 List 相干的操作方法，也有队列的相干操作方法。LinkedList和ArrayList一样实现了序列化接口Serializable和Cloneable接口使其领有了序列化和克隆的个性。- 继承了
AbstractSequentialList抽象类，在遍历的时候，举荐应用迭代器进行遍历。
然而只反对浅克隆，在LinkedList类中，其中的外部类Node并没有被克隆，只是调用了Object类中的clone办法进行可克隆。
LinkedList 双向链表实现及成员变量
外围组成：用来存储数据的结点，在LinkedList中设计成了外部类。
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 次要成员变量有下边三个：
//LinkedList 中的节点个数transient int size = 0;//LinkedList 链表的第一个节点transient Node<E> first;//LinkedList 链表的最初一个节点transient Node<E> last;构造方法
LinkedList的构造方法只提供了两个：
/** * 空参数的结构因为生成一个空链表 first = last = null */ public LinkedList() { }/** * 传入一个汇合类，来结构一个具备肯定元素的 LinkedList 汇合 * @param c 其外部的元素将按程序作为 LinkedList 节点 * @throws NullPointerException 如果 参数 collection 为空将抛出空指针异样 */public LinkedList(Collection<? extends E> c) { this(); addAll(c);}带参数的构造方法，调用 addAll(c) 这个办法，
public boolean addAll(Collection<? extends E> c) { return addAll(size, c);}实际上这办法调用了 addAll(size, c) 办法，
/** * 在 index 节点前插入蕴含所有 c 汇合元素的节点。 * 返回值示意是否胜利增加了对应的元素. */public boolean addAll(int index, Collection<? extends E> c) { // 查看索引是否满足 0 =< index =< size 的要求 checkPositionIndex(index); // 调用对应 Collection 实现类的 toArray 办法将汇合转为数组 Object[] a = c.toArray(); //查看数组长度，如果为 0 则间接返回 false 示意没有增加任何元素 int numNew = a.length; if (numNew == 0) return false; // 保留 index 以后的节点为 succ，以后节点的上一个节点为 pred Node<E> pred, succ; // 如果 index = size 示意在链表尾部插入 if (index == size) { succ = null; pred = last; } else { succ = node(index); pred = succ.prev; } // 遍历数组将对应的元素包装成节点增加到链表中 for (Object o : a) { @SuppressWarnings("unchecked") E e = (E) o; Node<E> newNode = new Node<>(pred, e, null); //如果 pred 为空示意 LinkedList 汇合中还没有元素 //生成的第一个节点将作为头节点 赋值给 first 成员变量 if (pred == null) first = newNode; else pred.next = newNode; pred = newNode; } // 如果 index 地位的元素为 null 则遍历数组后 pred 所指向的节点即为新链表的末节点，赋值给 last 成员变量 if (succ == null) { last = pred; } else { // 否则将 pred 的 next 索引指向 succ ，succ 的 prev 索引指向 pred pred.next = succ; succ.prev = pred; } // 更新以后链表的长度 size 并返回 true 示意增加胜利 size += numNew; //fast-fail modCount++; return true;}addAll(c)在内部独自调用时，将指定汇合的元素作为节点，增加到 LinkedList 链表尾部。
而 addAll(size, c) 能够将汇合元素插入到指定索引节点。
对于 checkPositionIndex办法这里想顺带剖析了，
LinkedList 中有两个办法用于查看角标越界，外部实现一样。
private boolean isElementIndex(int index) { return index >= 0 && index < size; } private boolean isPositionIndex(int index) { return index >= 0 && index <= size; }都是通过 index >= 0 && index <= size 判断。
LinkedList 的增删改查
LinkedList 能够不便的在头尾插入一个节点，而 add 办法默认在链表尾部增加节点：
增加节点
public void addFirst(E e) { linkFirst(e); } public void addLast(E e) { linkLast(e); } public boolean add(E e) { linkLast(e); return true; }/** * 在指定 index 地位插入节点 */public void add(int index, E element) { // 查看角标是否越界 checkPositionIndex(index); // 如果 index = size 代表是在尾部插入节点 if (index == size) linkLast(element); else linkBefore(element, node(index));}能够看到默认是“尾插”，有返回值。
linkXXX
咱们能够看到 add 办法是有返回值的，这个能够留神下。
看来这一系办法都调用用了 linkXXX 办法。
/** * 增加一个元素在链表的头节点地位 */private void linkFirst(E e) { // 增加元素之前的头节点 final Node<E> f = first; //以增加的元素为节点值构建新的头节点 并将 next 指针指向 之前的头节点 final Node<E> newNode = new Node<>(null, e, f); // first 索引指向将新的节点 first = newNode; // 如果增加之前链表空则新的节点也作为未节点 if (f == null) last = newNode; else f.prev = newNode;//否则之前头节点的 prev 指针指向新节点 size++; modCount++;//操作数++}/** * 在链表开端增加一个节点 */ void linkLast(E e) { final Node<E> l = last;//保留之前的未节点 //构建新的未节点，并将新节点 prev 指针指向 之前的未节点 final Node<E> newNode = new Node<>(l, e, null); //last 索引指向末节点 last = newNode; if (l == null)//如果之前链表为空则新节点也作为头节点 first = newNode; else//否则将之前的未节点的 next 指针指向新节点 l.next = newNode; size++; modCount++;//操作数++}node(int index)
/** * 返回一个非空节点，这个非空节点位于 index 地位 */ Node<E> node(int index) { // assert isElementIndex(index); // 如果 index < size/2 则从0开始寻找指定角标的节点 if (index < (size >> 1)) { Node<E> x = first; for (int i = 0; i < index; i++) x = x.next; return x; } else { // 如果 index >= size/2 则从 size-1 开始寻找指定角标的节点 Node<E> x = last; for (int i = size - 1; i > index; i--) x = x.prev; return x; } }linkBefore(E e, Node<E> succ)
void linkBefore(E e, Node<E> succ) { // assert succ != null; // 因为 succ 肯定不为空，所以能够间接获取 prev 节点 final Node<E> pred = succ.prev; // 新节点 prev 节点为 pred，next 节点为 succ final Node<E> newNode = new Node<>(pred, e, succ); // 原节点的 prev 指向新节点 succ.prev = newNode; // 如果 pred 为空即头节点出插入了一个节点，则将新的节点赋值给 first 索引 if (pred == null) first = newNode; else pred.next = newNode;//否则 pred 的下一个节点改为新节点 size++; modCount++;}删除节点
remove()
/** * 删除头节点 * @return 删除的节点的值 即 节点的 element * @throws NoSuchElementException 如果链表为空则抛出异样 */ public E removeFirst() { final Node<E> f = first; if (f == null) throw new NoSuchElementException(); return unlinkFirst(f); }/** * 删除尾节点 * * @return 删除的节点的值 即 节点的 element * @throws NoSuchElementException 如果链表为空则抛出异样 */ public E removeLast() { final Node<E> l = last; if (l == null) throw new NoSuchElementException(); return unlinkLast(l); } /** * 删除指定索引地位的节点 */public E remove(int index) { checkElementIndex(index); return unlink(node(index));}/** *删除从头节点其第一个与 o 雷同的节点 */public boolean remove(Object o) { // 区别对待 null 元素，比拟元素时候应用 == 而不是 equals 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;}unlink()
/** * 移除头节点 */ private E unlinkFirst(Node<E> f) { // assert f == first && f != null; // 头节点的 element 这里作为返回值应用 final E element = f.item; // 头节点下个节点 final Node<E> next = f.next; // 开释头节点的 next 指针，和 element 下次 gc 的时候回收这个外部类 f.item = null; f.next = null; // help GC // 将 first 索引指向新的节点 first = next; // 如果 next 节点为空，即链表只有一个节点的时候，last 指向 null if (next == null) last = null; else next.prev = null; //否则 next 的 prev 指针指向 null size--;//扭转链表长度 modCount++;//批改操作数 return element;//返回删除节点的值 }/** * 移除未节点 */ 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 索引指向新的未节点 last = prev; // 链表只有一个节点的时候，first 指向 null if (prev == null) first = null; else prev.next = null; size--; modCount++; return element; }对于unlink的代码示意图：
/** * Unlinks non-null node x. */E unlink(Node<E> x) { // assert x != null; final E element = x.item; //保留 index 节点的前后两个节点 final Node<E> next = x.next; final Node<E> prev = x.prev; // 如果节点为头节点，则做 unlinkFirst 雷同操作 if (prev == null) { first = next; } else {//否则将上一个节点的 next 指针指向下个节点 prev.next = next; // 开释 index 地位 prev 指针 x.prev = null; } // 如果节点为尾节点，则将 last 索引指向上个节点 if (next == null) { last = prev; } else {//否则下个节点 prev 指针指向上个节点 next.prev = prev; x.next = null; } x.item = null; size--; modCount++; return element;}clear 操作
/*** Removes all of the elements from this list.* The list will be empty after this call returns.*/public void clear() { // 顺次革除节点，帮忙开释内存空间 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++;}查问节点
LinkedList 查问节点的办法，可分为依据指定的索引查问，获取头节点，获取未节点三种。
值得注意的是，依据索引去获取节点内容的效率并不高，所以如果查问操作多余增删操作的时候倡议用 ArrayList 去代替。
/*** 依据索引查问*public E get(int index) { checkElementIndex(index); return node(index).item;}/*** 返回 first 索引指向的节点的内容** @return the first element in this list* @throws NoSuchElementException 如果链表为空则抛出异样*/public E getFirst() { final Node<E> f = first; if (f == null) throw new NoSuchElementException(); return f.item;}/*** 返回 last 索引指向的节点的内容** @return the last element in this list* @throws NoSuchElementException 如果链表为空则抛出异样*/public E getLast() { final Node<E> l = last; if (l == null) throw new NoSuchElementException(); return l.item;}批改节点
LinkedList 只提供了 set(int index, E element) 一个办法
public E set(int index, E element) { // 判断角标是否越界 checkElementIndex(index); // 采纳 node 办法查找对应索引的节点 Node<E> x = node(index); //保留节点原有的内容值 E oldVal = x.item; // 设置新值 x.item = element; // 返回旧的值 return oldVal;}元素查问
/* * 返回参数元素在链表的节点索引，如果有反复元素，那么返回值为从头节点起的第一雷同的元素节点索引，* 如果没有值为该元素的节点，则返回 -1；* * @param o element to search for* @return */public int indexOf(Object o) { int index = 0; // 区别对待 null 元素，用 == 判断，非空元素用 equels 办法判断 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;}/****返回参数元素在链表的节点索引，如果有反复元素，那么返回值为从尾节点起的第一雷同的元素节点索引，* 如果没有值为该元素的节点，则返回 -1；** @param o element to search for* @return the index of the last occurrence of the specified element in* this list, or -1 if this list does not contain the element*/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;}调用 indexOf 从头结点开始查问元素地位遍历实现后若 返回值 !=-1 则示意存在，反之不存在
public boolean contains(Object o) { return indexOf(o) != -1;}LinkedList 作为双向队列的增删改查
Deque 这个双端队列就厉害了,它既能够实现栈的操作，也能够实现队列的操作，换句话说，实现了这个接口的类，既能够作为栈应用也能够作为队列应用。
咱们来看下 Queue 给咱们提供了的办法：
| 头部 | 头部 | 尾部 | 尾部 | |
|---|---|---|---|---|
| 插入 | addFirst(e) | offerFirst(e) | addLast(e) | offerLast(e) |
| 移除 | removeFirst() | pollFirst() | remveLast() | pollLast |
| 获取 | getFirst() | peekFirst() | getLast() | peekLast |
因为 Deque 接口继承 Queue 接口，当 Deque 当做队列应用时（FIFO），只须要在头部删除，尾部增加即可。咱们当初温习下 Queue 中的办法及区别：
Queue的offer和add都是在队列中插入一个元素，具体区别在于，对于一些 Queue 的实现的队列是有大小限度的，因而如果想在一个满的队列中退出一个新项，多出的项就会被回绝。此时调用add()办法会抛出异样，而offer()只是返回的 false。remove()和poll()办法都是从队列中删除第一个元素。remove()也将抛出异样，而poll()则会返回nullelement()和peek()用于在队列的头部查问元素。在队列为空时，element()抛出一个异样，而peek()返回null。
增加元素
// queue 的增加办法实现，public boolean add(E e) { linkLast(e); return true;}// Deque 的增加办法实现，public void addLast(E e) { linkLast(e);} // queue 的增加办法实现，public boolean offer(E e) { return add(e);}// Deque 的增加办法实现，public boolean offerLast(E e) { addLast(e); return true;} 很显著 LinkedList 的大小并没有限度，所以在 LinkedList 中他们的实现并没有实质性不同。
删除元素
// Queue 删除元素的实现 removeFirst 会抛出 NoSuchElement 异样public E remove() { return removeFirst();}// Deque 的删除办法实现public E removeFirst() { final Node<E> f = first; if (f == null) throw new NoSuchElementException(); return unlinkFirst(f);} // Queue 删除元素的实现 不会抛出异样 如果链表为空则返回 null public E poll() { final Node<E> f = first; return (f == null) ? null : unlinkFirst(f);}// Deque 删除元素的实现 不会抛出异样 如果链表为空则返回 null public E pollFirst() { final Node<E> f = first; return (f == null) ? null : unlinkFirst(f);}获取元素
// Queue 获取队列头部的实现 队列为空的时候回抛出异样 public E element() { return getFirst(); }// Deque 获取队列头部的实现 队列为空的时候回抛出异样public E getFirst() { final Node<E> f = first; if (f == null) throw new NoSuchElementException(); return f.item;}// Queue 获取队列头部的实现 队列为空的时候返回 nullpublic E peek() { final Node<E> f = first; return (f == null) ? null : f.item;}// Deque 获取队列头部的实现 队列为空的时候返回 nullpublic E peekFirst() { final Node<E> f = first; return (f == null) ? null : f.item;}参考链接
https://juejin.cn/post/684490...