目录
linkedList的基本结构
linkedLisa的实现
linkedList的构造方法
linkedList 新增元素
linkedList 删除元素
linkedList 遍历元素
linkedList get方法
linkedList的基本结构
1.7中的结构：
1.6的结构
linkedLisa的实现
linkedList 是基于双向链表数据结构实现的，linkedList 定义了一个 Node 结构，Node 结构中包含了 3 个部分：元素内容 item、前指针 prev 以及后指针 next，代码如下。
private static class Node{ E item; Node next; Node prev; Node(Node prev, E element, Node next) { this.item = element; this.next = next; this.prev = prev; } }
linkedList 就是由 Node 结构对象连接而成的一个双向链表。在 JDK1.7 之前，linkedList 中只包含了一个 Entry 结构的 header 属性，并在初始化的时候默认创建一个空的 Entry，用来做 header，前后指针指向自己，形成一个循环双向链表。
在 JDK1.7 之后，linkedList 做了很大的改动，对链表进行了优化。链表的 Entry 结构换成了 Node，内部组成基本没有改变，但 linkedList 里面的 header 属性去掉了，新增了一个 Node 结构的 first 属性和一个 Node 结构的 last 属性。这样做有以下几点好处：
first/last 属性能更清晰地表达链表的链头和链尾概念；
first/last 方式可以在初始化 linkedList 的时候节省 new 一个 Entry；
first/last 方式最重要的性能优化是链头和链尾的插入删除操作更加快捷了。
linkedList的构造方法
linkedList包含3个全局参数：
size存放当前链表有多少个节点。
first为指向链表的第一个节点的引用。
last为指向链表的最后一个节点的引用。
linkedList构造方法有两个，一个是无参构造，一个是传入Collection对象的构造。
// 什么都没做，是一个空实现
public linkedList() {
}
public linkedList(Collection c) {
this();
addAll(c);
}
public boolean addAll(Collection c) {
return addAll(size, c);
}
public boolean addAll(int index, Collection c) {
// 检查传入的索引值是否在合理范围内
checkPositionIndex(index);
// 将给定的Collection对象转为Object数组
Object[] a = c.toArray();
int numNew = a.length;
// 数组为空的话，直接返回false
if (numNew == 0)
return false;
// 数组不为空
Node pred, succ;
if (index == size) {
// 构造方法调用的时候，index = size = 0，进入这个条件。
succ = null;
pred = last;
} else {
// 链表非空时调用，node方法返回给定索引位置的节点对象
succ = node(index);
pred = succ.prev;
}
// 遍历数组，将数组的对象插入到节点中
for (Object o : a) {
@SuppressWarnings("unchecked") E e = (E) o;
Node newNode = new Node<>(pred, e, null);
if (pred == null)
first = newNode;
else
pred.next = newNode;
pred = newNode;
}
if (succ == null) {
last = pred; // 将当前链表最后一个节点赋值给last
} else {
// 链表非空时，将断开的部分连接上
pred.next = succ;
succ.prev = pred;
}
// 记录当前节点个数
size += numNew;
modCount++;
return true;
}
构造方法的参数顺序是：前继节点的引用，数据，后继节点的引用。
解析如下图：
对于两种构造方法，总结起来，可以概括为：无参构造为空实现。有参构造传入Collection对象，将对象转为数组，并按遍历顺序将数组首尾相连，全局变量first和last分别指向这个链表的第一个和最后一个。
linkedList 新增元素
linkedList 添加元素的实现很简洁，但添加的方式却有很多种。默认的 add (Ee) 方法是将添加的元素加到队尾，首先是将 last 元素置换到临时变量中，生成一个新的 Node 节点对象，然后将 last 引用指向新节点对象，之前的 last 对象的前指针指向新节点对象。
public boolean add(E e) {
linkLast(e);
return true;
}
void linkLast(E e) {
final Node l = last;
final Node newNode = new Node<>(l, e, null);
last = newNode;
if (l == null)
first = newNode;
else
l.next = newNode;
size++;
modCount++;
}
linkedList 也有添加元素到任意位置的方法，如果我们是将元素添加到任意两个元素的中间位置，添加元素操作只会改变前后元素的前后指针，指针将会指向添加的新元素，所以相比 ArrayList 的添加操作来说，linkedList 的性能优势明显。
public void add(int index, E element) {
checkPositionIndex(index);
if (index == size)
linkLast(element);
else
linkBefore(element, node(index));
}
void linkBefore(E e, Node succ) {
// assert succ != null;
final Node pred = succ.prev;
final Node newNode = new Node<>(pred, e, succ);
succ.prev = newNode;
if (pred == null)
first = newNode;
else
pred.next = newNode;
size++;
modCount++;
}
linkedList 删除元素
在 linkedList 删除元素的操作中，我们首先要通过循环找到要删除的元素，如果要删除的位置处于 List 的前半段，就从前往后找；若其位置处于后半段，就从后往前找。
这样做的话，无论要删除较为靠前或较为靠后的元素都是非常高效的，但如果 List 拥有大量元素，移除的元素又在 List 的中间段，那效率相对来说会很低。
public E removeFirst() {
final Node f = first;
if (f == null)
throw new NoSuchElementException();
return unlinkFirst(f);
}
private E unlinkFirst(Node f) {
// assert f == first && f != null;
final E element = f.item;
final Node next = f.next;
f.item = null;
f.next = null; // help GC
first = next;
if (next == null)
last = null;
else
next.prev = null;
size--;
modCount++;
return element;
}
linkedList 遍历元素
linkedList 的获取元素操作实现跟 linkedList 的删除元素操作基本类似，通过分前后半段来循环查找到对应的元素。但是通过这种方式来查询元素是非常低效的，特别是在 for 循环遍历的情况下，每一次循环都会去遍历半个 List。
所以在 linkedList 循环遍历时，我们可以使用 iterator 方式迭代循环，直接拿到我们的元素，而不需要通过循环查找 List。
linkedList get方法
public E getFirst() {
final Node f = first;
if (f == null)
throw new NoSuchElementException();
return f.item;
}
public E getLast() {
final Node l = last;
if (l == null)
throw new NoSuchElementException();
return l.item;
}
node()方法
public E get(int index) {
// 校验给定的索引值是否在合理范围内
checkElementIndex(index);
return node(index).item;
}
Node node(int index) {
if (index < (size >> 1)) {
Node x = first;
for (int i = 0; i < index; i++)
x = x.next;
return x;
} else {
Node x = last;
for (int i = size - 1; i > index; i--)
x = x.prev;
return x;
}
}
作用：判断给定的索引值，若索引值大于整个链表长度的一半，则从后往前找，若索引值小于整个链表的长度的一般，则从前往后找。这样就可以保证，不管链表长度有多大，搜索的时候最多只搜索链表长度的一半就可以找到，大大提升了效率。
