LinkedList源码解析

/ Java / 没有评论 / 313浏览

在这一篇中我们主要介绍LinkedList集合类。它和ArrayList不同的是,LinkedList底层是通过双向链表的方式实现的。下面我们介绍一下双向链表的知识。在上一篇中我们知道ArrayList底层数组在处理业务有一个很大的性能问题,就是如果我们从数组的中间位置要删除一个元素要付出很大的代价,原因就是将元素删除之后,这个元素后面的元素都要向数组的前端移动,所以会造成性能的损失,同样,在数组的中间位置插入元素时,也会有上述等问题。于是Java的设计者们为了解决ArrayList的性能问题时,于是LinkedList诞生了。因为它底层是采用双向链表的方式实现的,所以不会出现上述等问题。下面我们详细了解一下链表这个数据结构。

上一篇中我们介绍过,数组的底层实现是在连续的内存上存储的对象的信息,而在链表中却不是这样的,它会将每一个对象都存储在不同的独立的节点中,并且每个节点中除了存储要保存的数据信息外,还将存储上一个节点的引用和下一个节点的引用信息。在Java中可以将它们叫做前驱节点和后继节点。如下图所示:

QQ截图20170426170441.jpg

所以在我们使用LinkedList集合类时,从LinkedList删除一个元素是很方便的,并且性能是非常高的,因为它只需要把相应节点中的前驱节点和后继节点的引用删除就可以了,而不需要执行其它的额外操作。如下图所示:

QQ截图20170426171304.jpg

所以,通过上面双向链表数据结构的特性,使我们知道在使用LinkedList集合类时,如果有频繁的插入和删除操作时,那么使用LinkedList集合类时效率会比较高。但LinkedList集合的检索速度与ArrayList集合相比性能却要低很多,原因就是双链表的存储方式并不一定是连续的内存,所以在检索时,必须从双链表的第一个节点一个一个的向后查找,所以会消耗大量的查询时间,降低程序的运行性能。下面我们来分析一下LinkedList集合类的源码来看看底层是怎么实现上述功能的。

public LinkedList() {
}

LinkedList的构造方法,这里只是定义了一个空的构造方法,并没有其它的逻辑实现。可能有人想说,那我们完全可以不定义这个空的构造方法啊,反正虚拟机也会为我们自动创建,那为什么还要定义一个空的呢?虚拟机的确会为类自动创建一个空的构造方法,但这里有一个条件,那就是当前类中不能有其它的构造方法。如果虚拟机发现在当前类中已经有了其它的构造方法时,那么虚拟机在执行时是不会为我们自动创建新的构造方法的。在LinkedList中其实已经有了很多有参的构造方法,所以创建上述无参的构造方法,只是为了方便我们创建无参的LinkedList对象, 方便我们实例化用的。

public boolean add(E e) {
linkLast(e);
return true;
}

LinkedList中的添加方法,方法比较简单主要就是调用了linkLast()方法,可见该方法就是实现整个add()方法逻辑的主要方法。下面我们看一下该方法的源码。

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++;
}

我们看到此方法中使用了一个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;
}
}

现在我们知道了这个Node类是LinkedList集合中的一个内部类,它的功就相当于双链表中的节点,所以这个类中除了保存了当前元素外,还保存了这个元素的前驱节点,和后继节点。所以在linkLast()方法的前两句代码的意思就是将当前节点保存到一个新的节点中,然后在将链表中的最后一个元素设置为当前元素的前驱节点,然后在将当前元素的后继节点设置为null。这样就把数据添加到了当前节点中。所以LinkedList集合中的add()方法,每次都会把元素添加到链表的后端,这也是保证在LinkedList集合存储元素顺序的根本原因。将后继节点设置为null的目的是在双链表中此节点为最后一个节点。

通过上述的分析使我们知道LinkedList集合和ArrayList集合一样,也不是线程安全的,所以在多线程开发时也要额外添加同步代码,保证集合的线程安全。