JDK源码阅读——LinkedList实现

时间:2022-07-17 17:20:33

1 继承结构图

JDK源码阅读——LinkedList实现

LinkedList是List的另一种实现。继承自AbstractSequentialList

2 数据结构

LinkedList与ArrayList不同的是LinkedList底层使用双向链表进行存储,其主要数据结构如下

  // 记录List长度
  transient int size = 0;   // 指向LinkedList第一个节点
  transient Node<E> first;   // 指向LinkedList最后一个节点
  transient Node<E> last;   // Node Class如下
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的一个节点是一个Node对象,可以看到node.item记录值,并且分别有指向前一个节点和后一个节点的指针prev和next

3 构造方法

    public LinkedList() {}

    public LinkedList(Collection<? extends E> c) {
this();
addAll(c);
}

LinkedList也支持两种构造方式,无参构造和传入一个集合构造LinkedList,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; 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;
Node<E> newNode = new Node<>(pred, e, null);
if (pred == null)
first = newNode;
else
pred.next = newNode;
pred = newNode;
} if (succ == null) {
last = pred;
} else {
pred.next = succ;
succ.prev = pred;
} size += numNew;
modCount++;
return true;
}

初始化是size=0,可见就是利用Collection的toArray方法把c转为对象数组,然后遍历新建Node,并逐个连起来,基本的链表操作。

4 一些方法介绍

    void linkBefore(E e, Node<E> succ) {
// assert succ != null;
final Node<E> pred = succ.prev;
final Node<E> newNode = new Node<>(pred, e, succ);
succ.prev = newNode;
if (pred == null)
first = newNode;
else
pred.next = newNode;
size++;
modCount++;
}

linkBefore方法是在succ节点之前插入一个新的节点,其执行过程大致如下图

JDK源码阅读——LinkedList实现

其他方法类似也都可以通过画图的形式了解大致执行步骤,涉及链表操作,画图能更好的理解执行过程,在此不再赘述。

5 与ArrayList的异同

ArrayList和LinkedList是List的两种实现,不同的ArrayList是基于动态数组的数据结构,而LinkedList是基于双向链表的数据结构。

他们的优缺点也正是由于他们所依赖的数据结构决定的

  • 对于随机存取,因为ArrayList是基于数组实现的,所以随机存取的时间复杂度为O(1),直接根据数据下标即可get或set,而LinkedList由于是使用双向链表实现,随机存取需要移动指针,时间复杂度为O(n);
  • 但是对于元素的删除和增加,如果不是在List尾部操作,ArrayList中元素的删除会涉及数组元素的移动,所以复杂度O(n)会比只单纯操作几个指针的复杂度O(1)要高。

所以在日常使用中,需要根据应用场景灵活选择,对于不需要随机存取而是只进行平凡的增加和删除的场景,使用LinkedList是较好的选择。

本文来自我的个人博客:http://blog.duchangchun.com/2018/12/29/jdk_linkedlist/