双向循环链表
双向循环链表和双向链表的不同在于，第一个节点的pre指向最后一个节点，最后一个节点的next指向第一个节点，也形成一个“环”。而LinkedList就是基于双向循环链表设计的。
LinkedList 是一个继承于AbstractSequentialList的双向循环链表。它也可以被当作堆栈、队列或双端队列进行操作。
public class LinkedList<E> extends AbstractSequentialList<E> implements List<E>, Deque<E>, Cloneable, java.io.SerializableLinkedList 实现 List 接口，能对它进行队列操作。
LinkedList 实现 Deque 接口，即能将LinkedList当作双端队列使用。
LinkedList 实现了Cloneable接口，即覆盖了函数clone()，能克隆。
LinkedList 实现java.io.Serializable接口，这意味着LinkedList支持序列化，能通过序列化去传输。
LinkedList 是非同步的。
size:当前有多少个节点；
first：第一个节点；
last：最后一个节点；
public class LinkedList<E> extends AbstractSequentialList<E> implements List<E>, Deque<E>, Cloneable, java.io.Serializable { //list的元素数量 transient int size = 0; /** *第一个节点 */ transient Node<E> first; /** * 最后一个节点 */ transient Node<E> last;LinkedList构造方法：
空的构造方法：表示初始化的时候，size为默认值0；first和last为空；
带入参的构造方法：
this（）调用默认无参构造方法;
addAll()传进去入参的集合数据;
检查index索引范围 ;
得到集合数据
得到插入位置的前驱和后继节点
遍历数据，将数据插入到指定位置
/** * 空构造函数 */ public LinkedList() { } /** *构造一个包含指定 collection 中的元素的列表，这些元素按其 collection 的迭代器返回的顺序排列 */ public LinkedList(Collection<? extends E> c) { this(); addAll(c); } /** * 将集合从指定位置开始插入 * 1. 检查index索引范围 * 2. 得到集合数据 * 3. 得到插入位置的前驱和后继节点 * 4. 遍历数据，将数据插入到指定位置 */ 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()方法得到后继节点，再得到前驱节点 succ = node(index); pred = succ.prev; } //遍历数据将数据插入 for (Object o : a) { @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; } //如果插入位置在尾部，重置last节点 if (succ == null) { last = pred; } else { //否则，将插入的链表与先前链表连接起来 pred.next = succ; succ.prev = pred; } size += numNew; modCount++; return true; } 新增元素操作： /** * 将一个元素添加至list尾部 */ public boolean add(E e) { linkLast(e); return true; }指定位置添加元素：
检查index的范围，否则抛出异常
如果插入位置是链表尾部，那么调用linkLast方法
如果插入位置是链表中间，那么调用linkBefore方法
/** * 指定位置添加元素 *1. 检查index的范围，否则抛出异常 *2. 如果插入位置是链表尾部，那么调用linkLast方法 *3. 如果插入位置是链表中间，那么调用linkBefore方法 */ public void add(int index, E element) { //检查索引是否处于[0-size]之间 checkPositionIndex(index); //添加在链表尾部 if (index == size) linkLast(element); else //添加在链表中间 linkBefore(element, node(index)); }linkBefore 非空节点前插入元素图示：
检索操作分为按照位置得到对象以及按照对象得到位置两种方式，其中按照对象得到位置的方法有indexOf()和lastIndexOf()；按照位置得到对象有如下方法：
根据任意位置得到数据的get(int index)方法，当index越界会抛出异常
获得头节点数据
getFirst()和element()方法在链表为空时会抛出NoSuchElementException
peek()和peekFirst()方法在链表为空时会返回null
获得尾节点数据
getLast()在链表为空时会抛出NoSuchElementException
peekLast()在链表为空时会返回null