jdk源码详解之LinkedList

1、家族情况

LinkedList

ArrayList一样,他们的共同的祖先是Collection。不同的是他的继承结构还是比ArrayList复杂一些。

AbstractSequentialList是顺序访问list的骨架,LinkedList底层是链表属于顺序访问,所以应该集成这个类。如果是随机访问,如ArrayList则应该直接继承AbstractList就好了。

Deque接口声明了一系列链表集合需要实现的函数。你既可以用这个接口做先进先出(队列),也可以用做先进后出(栈)。具体要看你怎么实现和调用方法。关于堆、栈、队列的区别可以看这里Queue这个接口主要注重的是队列(FIFO)这个方式的实现,而Qeque基于Queue做了一些双向链表的方法抽象。比如Queue中的add方法在Deque中又扩展了两个方法:addFirstaddLast

2、数据结构

LinkedList的底层的数据结构是双向链表,所以内部的实现肯定也是按照这个结构来做的。首先我们来看单个节点是如何构成的。

1
2
3
4
5
6
7
8
9
10
11
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;
}
}

这是一个静态内部类,里面有3个成员变量,分别标识:本节点的实际内容、上一个节点、下一个节点。如果变成图片的话,大概是下图所示;每一个节点都会指向上一个节点,也会指向下一个节点。为什么说是双向呢,因为你可以从头遍历到尾部,也可以从尾部遍历到头部。因为他底层不数组,所以这也就意味着如果想要访问LinkedList中任意一个元素,必须一个一个遍历过去,才能访问到。但是相应的,对集合中间进行元素的增删成本就会很低。因为只需要改变上一个节点和下一个节点的指针就可以做到。而ArrayList必须对数组的大量内容做移动才能做到。

LinkedList

3、成员变量

  • size

    当前集合的大小。

  • first

    第一个Node,默认为null。

  • last

    最后一个Node,默认为null。

因为第一个节点和最后一个节点比较特殊,因此以成员变量的形式体现。如果知道首尾的node,就可以在两个方向上遍历这个集合了。

4、重要函数

LinkedList中很多对外暴露的函数都由下面几个内部方法完成,下面我来详细讲解一下这些内部方法是如何操作“双向链表”这个数据结构的。

4.1、linkFirst

linkFirst

linkFirst的作用是将指定的对象放到队列的头部。操作流程也非常简单:

  1. 创建一个新节点,同时将前驱指定为null,后驱指向当前的头部节点。
  2. 将当前的头部节点的前驱设置为刚刚创建的新节点。
  3. 将新节点设置为当前队列的头部。

通过上面一番操作之后,元素e变成了头部的元素。addFirst方法的内部就是使用的linkFirst方法将元素添加到list的头部。

4.2、linkLast

linkLast

linkFirst对应,就是将元素e添加到队列的末尾。原理也和linkFirst类似。

  1. 创建一个新的节点,将此节点的前驱设置为当前的尾部节点,后驱设置为null。
  2. 将当前的尾部节点的后驱指向刚刚创建的新节点。
  3. 将新节点设置为当前队列的尾部。

4.3、linkBefore

linkBefore

linkBefore方法的意思将元素e插入到一个非空的节点之前。add(int index, E element)方法内部就是使用了这个方法添加元素。

4.4、unlinkFirst

unlinkFirst

unlinkFirst就是将队列中第一个元素剔除,并且返回被剔除元素给调用者。removeFirst(),poll(),pollFirst()方法内部都调用了这个方法。

4.5、unlinkLast

unlinkLast

unlinkLast就是将队列中最后一个元素剔除,并且返回被剔除元素给调用者。

unlink

unlink就是将节点x从队列中剔除。

原文地址:https://www.jdkdownload.com/jdk_linkedlilst.html