前言
LinkedList 底层是双向链表，同时实现了List接口和Deque接口，所以它既可以看作是一个顺序容器，也可以看作是一个队列(Queue)，同时也可以看作是一个栈(Stack)，
但如果想使用栈或队列等数据结构的话，推荐使用 ArrayDeque，它作为栈或队列会比 LinkedList 有更好的使用性能。
获取元素，修改元素，新增元素与删除元素，并分析这些操作对应的时间复杂度。
获取元素
LinkedList 提供了三种获取元素的方法，分别是：
getFirst()：获取第一个元素，直接返回 Node
first 指向的结点即可，所以时间复杂度为 O(1)。 getLast()：获取最后一个元素，直接返回 Node
last 指向的结点即可，所以时间复杂度也为 O(1)。 get(int i): 获取指定索引 index 位置的元素，由于结点在内存中存储的空间不是连续存储的，所以需要先遍历，首先判断位置在链表的前半部分或后半部分，再遍历查找数据，最坏的情况需要n/2次遍历，所以时间复杂度位 O(n)。
综上所述，LinkedList 获取元素的时间复杂度为 O(n)。
修改元素
LinkedList 提供了一种修改元素数据的方法:
set(int index, E element): 折半查询找到元素，赋予新值，返回旧元素。故时间复杂度为 O(n);
新增元素
LinkedList 提供了四种新增元素的方法，分别是：
addFirst(E e): 只需将头结点 first 指向新元素结点，将原第一结点的前驱指针指向新元素结点即可。所以时间复杂度为 O(1)。
addLast(E e): 只需将尾结点 last 指向新元素结点，将原最后一个结点的后继指针指向新元素结点即可。所以时间复杂度也为 O(1)。
add(E e): 等价于 addLast(E e)。
add(int index, E element)，需要先根据位置 index 调用 node(index)遍历链表获取该位置的原结点，然后将新结点插入至原该位置结点的前面，不需要移动原数据存储位置，只需交换一下相关结点的指针域信息即可。所以时间复杂度也为 O(1)。
综上所述，LinkedList 新增元素的时间复杂度为 O(1)，单纯论插入新元素，操作是非常高效的，特别是插入至头部或插入到尾部。但如果是通过索引 index 的方式插入，插入的位置越靠近链表中间所费时间越长，因为需要对链表进行遍历查找。
删除元素
LinkedList 提供了四种删除元素的方法，分别是：
removeFirst(): 只需将头结点
first指向删除元素结点的后继结点并将其前驱结点指针信息prev清空即可。不需要移动原数据存储位置，只需操作相关结点的指针域信息即可。所以时间复杂度为 O(1)。removeLast(): 只需将尾结点
last指向删除元素结点的前驱结点并将其后继结点指针信息next清空即可。不需要移动原数据存储位置，只需操作相关结点的指针域信息即可，所以时间复杂度也为 O(1)。remove(int index)，需要先根据位置 index 调用遍历链表获取该位置的原结点，然后将删除元素结点的前驱结点的 next 后继结点指针域指向删除元素结点的后继结点，删除元素结点的后继结点的 prev 前驱结点指针域指向删除元素结点的前驱结点即可，不需要移动原数据存储位置，只需交换一下相关结点的指针域信息即可。所以时间复杂度也为 O(1)。
remove(Object o): 比较对象是否一致通过
o.equals方法比较remove(Object o)，和 3.的思路基本差不多，关键是比较对象是通过o.equals方法，记住这点即可。综上所述，LinkedList 删除元素的时间复杂度为 O(1)，单纯论删除元素，操作是非常高效的，特别是删除第一个结点或删除最后一个结点。但如果是通过索引 index 的方式或者 object 对象的方式删除，则需要对链表进行遍历查找对应 index 索引的对象或者利用 equals 方法判断对象。
ArrayList 和 LinkedList
更占内存
LinkedList 内部存储的是 Node
，不仅要维护数据域，还要维护 prev 和 next，如果 LinkedList 中的结点特别多，则 LinkedList 比 ArrayList 更占内存。 插入删除效率高?
对于linkedList头部和尾部插入和删除，效率都很高，操作要靠近中间的位置，需要遍历的操作越多，效率就越低。
对于ArrayList而言，尾部插入，效率很高，否则都需要进行拷贝，效率降低。
但越靠近中间位置的插入、删除，ArrayList效率要高于LinkedList的。
可以这么说，ArrayList快在遍历查找，慢在位置移动。
循环遍历效率低
论遍历 ArrayList 要比 LinkedList 快得多，ArrayList 遍历最大的优势在于内存的连续性，CPU 的内部缓存结构会缓存连续的内存片段，可以大幅降低读取内存的性能开销。
注：ArryayList遍历for循环比用迭代器要快，LinkedList用迭代器遍历又要快于for循环。 ArrayList实现了 RandomAccess 接口，官网还特意说明了，如果是实现了这个接口的 List，那么使用for循环的方式获取数据会优于用迭代器获取数据。