Linkedlist
简介
本节来介绍LinkedList ,他也是List 接口下最常用的用来存储数据的工具类之一。仍然从基础的数据结构，整个类的继承和实现的体系来了解。Linkedlist可以做那些事情，在哪些的应用场景下更适合应用。
1.首先LinkedList是基于双向链表。意味着增删比较快，但是查找相对于ArrayList会比较慢。（常见面试题之一，ArrayList与LinkedList的区别），本质上来讲，就是二者的数据结构不同，稍后可以说明。
2.实现了 Deque 接口，意味着可以进行队列操作。
3.实现了Cloneable接口，即覆盖了函数clone()，可以被克隆。
4.实现了 Serializable 接口，意味着LinkedList支持序列化，能通过序列化去传输。
5.LinkedList和Arraylist一样，都是线程不安全的。
结构图
image.png
构造函数
Linkedlist共有两个构造函数。分别为：
1.无参构造，直接创建LinkedList对象。
/**
* 构造一个空列表
*/
public LinkedList() {
}
image.png
2.参数需要一个Collection集合，作为参数，构造一个新的集合。
/**
* 构造包含指定元素的列表集合，按照集合返回的顺序迭代器
*
* @param c the collection whose elements are to be placed into this list
* @throws NullPointerException if the specified collection is null
*/
public LinkedList(Collection<? extends E> c) {
this();
addAll(c);
}
image.png
这里就是，接收一个集合，作为参数，然后调用 addAll() 方法，来初始化LinkedList()。
接下来分析，addAll()方法做了哪些事情。
这里调用了 public 权限的 addAll() 方法。说明，我们可以将任意一个集合添加到 LinkedList 中。
这里有一点要注意：默认的size就是当前的链表长度，默认在当前链表后面添加参数的集合。
/**
* 将指定集合中的所有元素追加到末尾这个列表，按照指定的返回顺序集合的迭代器。
* 如果没有定义此操作的行为在操作中修改指定的集合进步。(注意，如果指定的集合是，就会发 * 生这种情况*这个列表，它不是空的。
*/
public boolean addAll(Collection<? extends E> c) {
return addAll(size, c);
}
Alt text
addAll()
这里要对Node做一下解释，Node共包含三个属性，上一个节点，当前元素，下一个节点。这样就组成了一个链表。
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;
}
}
/**
*将指定集合中的所有元素插入其中列表，从指定位置开始。变化的元素
*目前处于该位置(如果有的话)和任何后续元素
*右边(增加他们的指数)。新的元素将会出现
*在列表中，以它们被返回的顺序指定集合的迭代器。
*/
public boolean addAll(int index, Collection<? extends E> c) {
//检查索引是否合法
checkPositionIndex(index);
//将添加的集合先转成Object数组
Object[] a = c.toArray();
int numNew = a.length;
//如果数组的长度为0，返回false不做任何操作
if (numNew == 0)
return false;
//定义一个节点
Node<E> pred, succ;
//当向链表最后面插入时。
if (c == size) {
succ = null;
//将链表最后一个节点，赋值给当前定义节点的上一个节点。
pred = last;
} else {
//这里查找原来index位置的Node，做为后置节点。
succ = node(index);
//前置节点为index节点的前一个节点。
pred = succ.prev;
}
for (Object o : a) {
@SuppressWarnings("unchecked") E e = (E) o;
//构造一个新的节点，pred原来index位置的上一个节点。e当前节点
Node<E> newNode = new Node<>(pred, e, null);
//如果pred为空,说明原来的链表是空的，那么新增的节点为链表的第一个节点。
if (pred == null)
first = newNode;
else
//这里是当链表不是初始化时候，替换链表内指定的node
pred.next = newNode;
pred = newNode;
}
//如果succ为空，说明在链表的末尾，（或者是链表刚刚初始化，也为null）
if (succ == null) {
last = pred;
} else {
//链表中间添加情况，更新前置节点 后置节点。
pred.next = succ;
succ.prev = pred;
}
//修改size
size += numNew;
//修改modCount（这里后续解释作用是什么）
modCount++;
return true;
}
add()添加一个元素到链表内
/**
* 添加一个元素到链链表中，默认追加到链表的末尾‘
* 这里调用了public权限的add方法。’
*/
public boolean add(E e) {
//调用linkLast
linkLast(e);
return true;
}
linkLast追加到链表末尾
/**
*添加到链表末尾
*/
void linkLast(E e) {
//保存原有链表的最后一个节点。
final Node<E> l = last;
//构造当前节点，并且原来的最后一个节点最为当前节点的上一个节点
final Node<E> newNode = new Node<>(l, e, null);
//当前节点作为原有链表的最后一个节点
last = newNode;
//如果原有的最后一个节点为null，说明链表为null（刚刚初始化）
if (l == null)
//当前节点作为第一个节点。
first = newNode;
else
//将当前节点赋值给原来最后一个节点的下一个节点。
l.next = newNode;
size++;
modCount++;
}
remove删除元素
/**
*删除指定元素
*/
public boolean remove(Object o) {
//如果要删除的元素为空，那么便利当前链表，找到为空的元素，解除关联。
if (o == null) {
for (Node<E> x = first; x != null; x = x.next) {
if (x.item == null) {
//实际从链表中去除关联
unlink(x);
return true;
}
}
} else {
for (Node<E> x = first; x != null; x = x.next) {
//如果去除指定元素，则直接equals寻找要删除的元素。
if (o.equals(x.item)) {
unlink(x);
return true;
}
}
}
return false;
}
unlink删除元素
/**
* 删除指定的元素
*/
E unlink(Node<E> x) {
// assert x != null;
//需要删除的节点
final E element = x.item;
//保存需要删除节点的下一个节点
final Node<E> next = x.next;
//保存需要删除节点的上一个节点
final Node<E> prev = x.prev;
//如果上一个节点是空，则原有的末尾节点作为第一个节点
if (prev == null) {
first = next;
} else {
//原有节点上一个节点，对应的下一个节点为next。有点绕口。。。
prev.next = next;
//将当前节点的 前置节点置空
x.prev = null;
}
//如果后置节点为空（说明当前节点原本是尾节点）
if (next == null) {
//则尾节点为前置节点
last = prev;
} else {
//将当前节点的 后置节点置空
next.prev = prev;
x.next = null;
}
//当前元素置为null
x.item = null;
//链表数量-1
size--;
//修改modCount
modCount++;
//返回删除的元素
return element;
}
push&pop
注意：链表中也存在push，pop操作，说明可以作为一个栈来操作。面试也很常见实现一个自己的栈或者队列。这里看一下，push和pop操作，用来了解一下栈是如何实现的。
public void push(E e) {
addFirst(e);
}
public E pop() {
return removeFirst();
}
调用的方法分别为addFirst，removeFirst。
/**
* 直接追加到链表最前面
*/
public void addFirst(E e) {
linkFirst(e);
}
pop也是一样的道理，直接操作首节点
/**
*删除首节点
*/
public E removeFirst() {
final Node<E> f = first;
if (f == null)
throw new NoSuchElementException();
return unlinkFirst(f);
}
总结
1.上文说明了LinkedList是基于双向链表，在实际的代码中看到，当增加或者删除一个元素，在原有的链表中直接寻找并且unlink即可。
2.删除和增加都涉及到modCount操作，这点要注意（后续解释，或者可以自行百度）。
3.其实增加和删除或者其他操作，都围绕着一个核心，就是处理链表。这里如果把链表的结构自己理解的足够好，可以尝试自己写一个自己的链表。
4.jdk中每一个类，方法都拆分的足够细致，得以最大化的复用。这也是是学习的目的之一，将自己的代码做到尽可能细致的拆分，每一个方法具体用来做什么。
