一、LinkedList概述
LinkedList的底层数据结构为双向链表结构，与ArrayList相同的是LinkedList也可以存储相同或null的元素。相对于ArrayList来说，LinkedList的插入与删除的速度更快，时间复杂度为O(1),查找的速度就相对比较慢了，因为每次遍历的时候都必须从链表的头部或者链表的尾部开始遍历，时间复杂度为O(n/2)。为了实现快速插入或删除数据，LinkedList在每个节点都维护了一个前继节点和一个后续节点，这是一种典型的以时间换空间的思想。LinkedList同时也可以实现栈与队列的功能。
二、LinkedList的结构图
在LinkedList中每个节点有会有两个指针，一个指向前一个节点，另一个指向下一个节点。链表的头部的前指针为null，尾部的后指针也为null，因此也可以说明LinkedList（基于jdk1.8）是非循环双向链表结构。源码如下：
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属性
1、size: 链表的长度
2、first：链表的第一个节点
3、last：链表的最后一个节点
transient int size = 0; /** * Pointer to first node. * Invariant: (first == null && last == null) || * (first.prev == null && first.item != null) */ transient Node<E> first; /** * Pointer to last node. * Invariant: (first == null && last == null) || * (last.next == null && last.item != null) */ transient Node<E> last; /** * Constructs an empty list. */
四、添加节点
1、链表头部添加新节点
/** * Links e as first element. * 链接头部 */ private void linkFirst(E e) { //链表的第一个节点 final Node<E> f = first; //创建节点 final Node<E> newNode = new Node<>(null, e, f); //将新创建的节点放到链条头部 first = newNode; //当链表为null时，链表头部和尾部都指向新节点 if (f == null) last = newNode; else f.prev = newNode;//
