一、前言
前面介绍了ArryList的原理和使用方法，本篇来介绍List家族中另一个重要成员——LinkedList。LinkedList和ArrayList一样是集合List的实现类，虽然较之ArrayList，其使用场景并不多，但同样有用到的时候，那么接下来，我们来认识一下它。
二、LinkedList的继承关系
通过IDEA生成LinkedList的继承关系图，可以清晰的看出LinkedList的继承关系。如下图
三、LinkedList的属性
首先，我们先看一下LinkedList这个类的属性。
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; 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类的主要属性有size，first和last。其中，size标识节点的个数，first指向链表的头节点，last指向链表的尾节点。再看一下节点的定义，也就是Node类，可以看出，LinkedList其实就是一个双向链表。
四、LinkedList的构造函数
LinkedList的提供两个构造函数。一个无参构造函数，一个参数未集合构造函数。
4.1 无参构造函数
无参构造函数很简单，只是创建了一个LinkedList的对象。
public LinkedList() { }
4.2 有参构造函数
有参构造函数首先调用无参构造函数新建一个对象，然后再调用addAll将集合添加进去。
public LinkedList(Collection<? extends E> c) { this(); addAll(c); }
再来看一下addAll方法，我将相关的方法都粘了过来，逐一进行分析public boolean addAll(Collection<? extends E> c) return addAll(size, c);
} public boolean addAll(int index, Collection<? extends E> c) { checkPositionIndex(index); Object[] a = c.toArray(); int numNew = a.length; if (numNew == 0) return false; //pred指向插入位置的前一个节点，succ指向插入位置的后一个节点 Node<E> pred, succ;
if (index == size) { succ = null;
//指向最后一个节点 pred = last; } else { succ = node(index);
//指向要插入位置的前一个节点 pred = succ.prev; } for (Object o : a) { @SuppressWarnings("unchecked") E e = (E) o;
//新建一个节点，前驱为prep所指向的节点 Node<E> newNode = new Node<>(pred, e, null); if (pred == null)
//新创建的对象，这里会执行 first = newNode; else
//pred的后置节点为新建节点 pred.next = newNode;
//将pred前移 pred = newNode; } if (succ == null) {
//设置尾节点 last = pred; } else {
//指向后一个节点 pred.next = succ; succ.prev = pred; } size += numNew; modCount++; return true; } private void checkPositionIndex(int index) { if (!isPositionIndex(index)) throw new IndexOutOfBoundsException(outOfBoundsMsg(index)); } private boolean isPositionIndex(int index) { return index >= 0 && index <= size; }
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;
}
}
首先调用addAll的重载方法，可以再某个位置添加节点，传入size，此时size的值为0。首先调用 checkPositionIndex(index)方法，然后将要得到要插入位置的前置节点和后置节点，最后插入元素，详细看代码注释。
五、常用方法解读
这里只说一下插入和删除，他们牵涉到引用的变动
5.1 添加元素
LinkedList主要提供addFirst、addLast、add、addAll等方法来实现元素的添加。下面我们一一来看：public void addFirst(E e) { linkFirst(e);
} private void linkFirst(E e) {
//保存第一个元素 final Node<E> f = first;
//创建新元素，并将后驱指向原来的first final Node<E> newNode = new Node<>(null, e, f); first = newNode; if (f == null) last = newNode; else
//原来的前置节点前驱为新节点
f.prev = newNode; size++; modCount++; }
add方法和addLast方法最后调用的都是一个方法，总体思路一样，只是牵涉到引用的指向。
public boolean add(E e) { linkLast(e); return true; } public void addLast(E e) { linkLast(e); } void linkLast(E e) { final Node<E> l = last; final Node<E> newNode = new Node<>(l, e, null); last = newNode; if (l == null) first = newNode; else l.next = newNode; size++; modCount++; }
看了这几个添加，通过下面这个图来看一下吧
5.2 移除元素
这里只说一下public E remove(int index)这个方法
public E remove(int index) {
//检查是否越界 checkElementIndex(index);
//得到对应位置的节点，然后移除 return unlink(node(index)); } 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) {
//前置为空，头节点为next first = next; } else {
//前一个节点指向要移除节点的后置，并将要移除节点前驱置空 prev.next = next; x.prev = null; } if (next == null) { last = prev; } else {
//去掉后置节点连接，将要移除节点的后置节点的前驱设置，要移除节点的前驱 next.prev = prev; x.next = null; } x.item = null; size--; modCount++; return element; }
通过下面这张图就可以清楚的标识引用的变动了
六、总结
本篇对LinkedList的原理进行了分析，希望对大家有所帮助，接下来会对比一下ArrayList和LinkedList，希望小伙伴们持续关注。