当前位置: 代码迷 >> 综合 >> 容器类源码解析系列(二)—— LinkedList 集合源码分析(最新版)
  详细解决方案

容器类源码解析系列(二)—— LinkedList 集合源码分析(最新版)

热度:58   发布时间:2023-10-19 15:20:19.0

容器类源码解析系列(二)—— LinkedList 集合源码分析(最新版)

前言

上篇文章 容器类源码解析系列(一) ArrayList 源码分析——基于最新Android9.0源码 对ArrayList集合的源码进行了详细的分析,通过源码分析,使得我们对ArrayList的理解更加深刻,使用起来会更得心应手。本文将要讲解的是LinkedList的底层原理。建议在阅读本文之前,先回顾一下上篇介绍ArrayList的文章,毕竟它们都是开发中的常用的集合类。

要点

  • LinkedList底层是通过基于双向链表实现数据持久化存储的。

    容器类源码解析系列(二)—— LinkedList 集合源码分析(最新版)

  • LinkedList可以存储Null值,可以存储重复的值。

  • LinkedList是非线程安全的,在多线程并发环境下,需要加锁来做同步处理,也可通过Collections.synchronizedList(new LinkedList(…))方法,获得一个加过锁的List。

  • LinkedList也是具有fail-fast特性的集合类。关于fail-fast机制,容器类源码解析系列(一) ArrayList 源码分析——基于最新Android9.0源码 这篇文章有详细讲解。

  • current节点的prev等于null,则该节点是first节点;current节点的next等于null,则该节点是last节点。

Node 节点

分析LinkedList源码,Node这个类,我们必要要知道。Node(节点)是在链表结构中的基本组成单位。我们看一下LinkedList类中,对节点的定义。

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的含义,element表示存储的Value值,pre、next分别指向当前节点的上一个节点和下一个节点。

构造

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;/*** Constructs an empty list.*/public LinkedList() {
    }/*** Constructs a list containing the elements of the specified* collection, in the order they are returned by the collection's* iterator.** @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);}

先看上面的成员变量,他们都被transient关键字修饰,表示不会被序列化。size是容器大小;first,last分别表示开始的节点和最后一个节点。我们发现first和last上面还有两段说明。这两段说明,是很有必要注意一下的,因为后面的一些add,remove等常规操作,其中对节点的处理逻辑,是和这两段说明有对应联系的。

Invariant: (first == null && last == null) || (first.prev == null && first.item != null)

这段说明是形容first节点的,如果first是null,那么last节点也应该是null;first.prev等于null,first.item不能等于null。这两个条件至少有一个成立,这是对first节点的定理约束。第一个判断还比较好理解,第二个判断可能不好理解,我们来通过一些例子感受一下。

/*** Links e as last element.*/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;elsel.next = newNode;size++;modCount++;}

上面的代码是LinkedList源码中把一个value值插入链表尾部的方法,实现逻辑如下:

  1. 首先把旧的last节点引用指向l;
  2. 创建新的节点来,pre指向旧的last节点,那么不言而喻,newNode节点就是新的last节点。
  3. 如果l节点,也就是pre指向的节点等于null,这个newNode同是也被指向first节点,成为first节点。

后面的就不分析了,此时我们看,newNode节点(即first节点),它的pre(l)是等于null的,newNode节点的next也是null,如果此刻e也等于null,则第二个条件 (first.prev == null && first.item != null) 没有满足,但是不要忘了newNode既是first节点也是last节点,满足了第一个条件 (first == null && last == null) 所以,定理还是满足的。

第二个不变的定理是指向last节点的Invariant: (first == null && last == null) || (last.next == null && last.item != null) 就不在细说了,这两个不变的定理,在LinkedList的源码实现逻辑中,会表现出现。


LinkedList不像ArrayList默认有10个capacity,linkedlist的size默认是0。所以LinkedList每次add数据都需要创建Node节点。

LinkedList有两个构造方法:

/*** Constructs an empty list.*/public LinkedList() {
    }/*** Constructs a list containing the elements of the specified* collection, in the order they are returned by the collection's* iterator.** @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);}

我们主要看第二个构造函数。传入有个list集合,把它放在当前LinkedList的尾部。

public boolean addAll(int index, Collection<? extends E> c) {
    checkPositionIndex(index);//(注释1)Object[] a = c.toArray();int numNew = a.length;if (numNew == 0)return false;Node<E> pred, succ;if (index == size) {
     //(注释2)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;elsepred.next = newNode;pred = newNode;}if (succ == null) {
    last = pred;} else {
    pred.next = succ;succ.prev = pred;}size += numNew;modCount++;return true;}

主要调用这个方法,表示吧指定集合添加到index对应的节点之前。通过构造函数调用这个方法的话,index是size值的大小,表示,把指定集合添加到当前链表的尾部。

(注释1)会先对index做一个数组越界的异常检测。

(注释2)如果size = index,表示吧传进来的指定集合add到链表尾部。不相等的话,就先通过node(index)拿到对应的节点,然后把pred = succ.prev;表示,之后添加的节点是插在index对应节点之前的地方。

接下来就比较简单了,就是循环创建节点,然后是修改next,prev指向问题。

常规操作

get,set操作

/*** Returns the element at the specified position in this list.** @param index index of the element to return* @return the element at the specified position in this list* @throws IndexOutOfBoundsException {@inheritDoc}*/public E get(int index) {
    checkElementIndex(index);return node(index).item;}/*** Replaces the element at the specified position in this list with the* specified element.** @param index index of the element to replace* @param element element to be stored at the specified position* @return the element previously at the specified position* @throws IndexOutOfBoundsException {@inheritDoc}*/public E set(int index, E element) {
    checkElementIndex(index);Node<E> x = node(index);E oldVal = x.item;x.item = element;return oldVal;}

先看get方法

/*** Returns the (non-null) Node at the specified element index.*/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;}}

在做一个判断来确定区间后,接着用for循环,遍历查找出目标节点。而ArrayList是通过数组直接拿到的。我们看set方法。

 public E set(int index, E element) {
    checkElementIndex(index);Node<E> x = node(index);E oldVal = x.item;x.item = element;return oldVal;}

和get方法一样,也是要通过node(index)方法,遍历获取目标节点,然后替换目标节点的element的值。所以相较于ArrayList,对于get,set操作,还是ArrayList更方便,效率些。

Add,Remove操作

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

添加元素,默认是添加到尾部,linkLast()这个方法前文有介绍,这里就不在重复了,内部逻辑就是new一个Node节点,然后赋给last,再把旧的last指向新的节点的prev。

public void add(int index, E element) {
    checkPositionIndex(index);if (index == size)linkLast(element);elselinkBefore(element, node(index));}

我们着重看linkBefore方法,该方法的第二个参数是调用了之前说的node(index)方法,找到对应index的目标节点。

/*** Inserts element e before non-null Node succ.*/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;elsepred.next = newNode;size++;modCount++;}

总的来说就是new一个节点,然后设置其的prev,next,以及它前一个节点的确定。add操作系列的方法还有addAll、addFirst、等等。addAll方法上面已经介绍过了。它们的逻辑都大差不差,有index要求的,就先遍历确定index对应的节点,然后创建Node节点,再做pre,next这些引用的调整,没有index要求的,就创建节点,默认放在最前面,或者最后面,最后重新设置一下first,last的引用。


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) {
    if (o.equals(x.item)) {
    unlink(x);return true;}}}return false;}
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 {
    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;}

先遍历找到目标节点,然后重新指定目标节点的prev,next指向关系,把目标节点的prev,element,next值置为null,方便回收。

public E remove(int index) {
    checkElementIndex(index);return unlink(node(index));}

这个方法,是根据index,先找到目标节点,然后在对目标节点进行处理。通过分析ArrayList和LinkedList的插入,删除源码实现,可以得出如下结论。

总结

有些说法认为LinkedList做插入和删除更快,这种说法其实不是绝对的:

(1)LinkedList做插入、删除的时候,慢在寻址,快在只需要改变前后Node节点的prev,next的引用地址。

(2)ArrayList做插入、删除的时候,慢在数组元素的批量copy,快在寻址。

顺序插入(add)的话,建议选择LinkedList,因为ArrayList有扩容和批量copy的消耗。

随机插入,如果插入点在集合的前面部分靠近头,后面部分靠近尾端的部分,LinkedList更合适。

对于ArrayList,插入的越靠后,即index越大,size-index越小,copy的数量就越小。会更快些。(但是存在扩容的损耗)

删除操作,如果是remove(Object o),删除节点的位置越靠后,效率越差,如果是remove(int index)操作,则删除节点的位置在两端的效率高,中部的效率差。

ArrayList的删除操作效率表现和插入类似,越往后,copy的数量越少,越快些。

上面说的是在大量数据下,数据量少的情况下,其实差别不大。随便用!(ps:ArrayList用的多点)。

队列操作

因为LinkedList实现了Deque接口,所以也就有了队列的操作。比如:

offer(E e)
poll()
peek()

等等,比较简单,就不说了,知道有这回事就行了。

扫码加入我的个人微信公众号:Android开发圈 ,一起学习Android知识!!
容器类源码解析系列(二)—— LinkedList 集合源码分析(最新版)

  相关解决方案