LinkedList是List家族除ArrayList之外最为常用的另一成员，今天一文彻底搞懂LinkedList。
底层数据结构
LinkedList底层是一个双向链表：
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;
}
}
数据存储在Node对象的item中，并保留指向上一节点、下一节点的对象。
再为整个LinkedList定义首节点first，尾结点last，方便对LinkedList的正向或逆向访问。
LinkedList的容量
不使用数组存储数据，所以不存在容量的概念，可以无限存入。
数据存入
add（E e）/addlast(E e)：追加数据到链表尾部。
addfirst(E e):追加数据到链表头部。
push(E e)：压栈，等同于addfirst。
add(int index, E element)：追加数据到链表指定位置。
addAll(Collection<? extends E> c)：追加集合c中的所有数据到链表尾部。
addAll(int index,Collection<? extends E> c)：追加集合c中的所有数据到链表指定位置。
获取数据
contains(Object o)：判断链表是否包含目标对象。
peek()：获取链表第一个对象，并且不从链表中移除对象（不出栈）。
get(int index):获取指定位置对象。
pop()：获取链表第一个数据并出栈。
removeFirst():等同于pop。
get方法的时间复杂度？
不读源码的前提下，我们可以先猜测一下LinkedList获取指定位置元素的get(int index)方法的时间复杂度。LinkedList是一个双向列表，获取指定位置元素的唯一方法就是遍历，理论上的时间复杂度就是O(n)，n是列表长度。
我们看一下源码：
public E get(int index) {
checkElementIndex(index);
return node(index).item;
}
Node<E> node(int index) {
// assert isElementIndex(index);
if (index < (size >> 1)) {
Node<E> x = first;
for (int i = 0; i < index; i++)
x = x.next;
return x;
} else {
Node<E> x = last;
for (int i = size - 1; i > index; i--)
x = x.prev;
return x;
}
}
node(int index)方法其实还是用一种简单的方法提高了下遍历的性能：判断index是出于列表的前半部分、还是后半部分，出于前半部分则从表头first开始遍历，处于后半部分就从表尾last遍历。所以严格说LinkedList的get(int index)方法的时间复杂度是O(n/2)，虽然O(n)和O(n/2)在表述上其实没有什么太大区别，但是通过读源码知道这个细节，在你自己的应用中如果有类似场景的话，你可以用这样的方式（虽然并非并非显著）提高性能。
transient 关键字
可以看到LinkedList的属性size、first、last的定义加了关键字transient ，顺便简单了解一下transient 的作用。
个人认为transient 其实可以忽略，因为对代码运行逻辑没有任何影响，一般情况下，对性能也没有太大影响。transient 关键字只在序列化及反序列化时生效：序列化的时候忽略transient 关键字修饰的字段，他们不会被序列化，从而节约序列化过程中的时间和存储空间开销。所以我们其实可以猜测使用transient 关键字的一个基本要求：这些字段在序列化的时候不需要包含，那么，一定是通过现有的已序列化的其他数据、在反序列化的过程中可以计算出来。
检查下LinkedList的：
private void writeObject(java.io.ObjectOutputStream s)
throws java.io.IOException {
// Write out any hidden serialization magic
s.defaultWriteObject();
// Write out size
s.writeInt(size);
// Write out all elements in the proper order.
for (Node<E> x = first; x != null; x = x.next)
s.writeObject(x.item);
}
/**
* Reconstitutes this {@code LinkedList} instance from a stream
* (that is, deserializes it).
*/
@SuppressWarnings("unchecked")
private void readObject(java.io.ObjectInputStream s)
throws java.io.IOException, ClassNotFoundException {
// Read in any hidden serialization magic
s.defaultReadObject();
// Read in size
int size = s.readInt();
// Read in all elements in the proper order.
for (int i = 0; i < size; i++)
linkLast((E)s.readObject());
}
在反序列化（readObject方法）的过程中，size和first、last都会被计算出来。
总结：由于LinkedList是双向链表结构，实现了Deque接口，提供了一系列非常方便的队列操作方法，所以，如果有类似比如先进先出、先进后出等队列操作需求的场景，LinkedList是首选。