LinkedList源码分析

Android 71 2017-11-08 17:58

java中的数据结构源码分析的系列文章:
ArrayList源码分析
LinkedList源码分析

一、简述

上篇已经分析了基于数组实现数据存储的ArrayList(线性表),而本篇的主角是LinkedList,这个使用了链表实现数据存储的集合,它的增、删、查、改方式又会是怎样的呢?下面就开始对LinkedList的源码进行分析吧。

二、分析

List

在分析LinkedList之前,还是先瞄一眼List接口,虽然前篇已经看过一遍了,但为了明确下文的分析方向,还是先把List接口中的几个增删改查方法再列一次。

public interface List<E> extends Collection<E> {
    boolean add(E e);
    void add(int index, E element);
    boolean remove(Object o);
    E remove(int index);
    E set(int index, E element);
    E get(int index);
    ...
}

LinkedList

1、成员变量

public class LinkedList<E> extends AbstractSequentialList<E> implements List<E>, Deque<E>, Cloneable, java.io.Serializable{
    transient int size = 0;
    transient Node<E> first;
    transient Node<E> last;
    ...
}
  • size:数组元素个数
  • first:头节点
  • last:尾节点

LinkedList的成员变量很少,就上面那3个,其中first和last都是Node类型(即节点类型),用来表示链表的头和尾,这跟ArrayList就存在着本质的区别了。

要注意:

first和last仅仅只是节点而已,跟数据元素没有关系,可以认为就是2个额外的"指针",分别指着链表的头和尾。

2、构造函数

1)LinkedList

public LinkedList() {
}

LinkedList的构造函数有2个,以平时最常用的构造函数为例,发现该构造函数什么事都没做。

2)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;
    }
}

再来看看这个节点类型的类结构,它描述了一个带有两个箭头的数据节点,也就是说LinkedList是双向链表。

为什么Node这个类是静态的?答案是:这跟内存泄露有关,Node类是在LinkedList类中的,也就是一个内部类,若不使用static修饰,那么Node就是一个普通的内部类,在java中,一个普通内部类在实例化之后,默认会持有外部类的引用,这就有可能造成内存泄露。但使用static修饰过的内部类(称为静态内部类),就不会有这种问题,在Android中,有很多这样的情况,如Handler的使用。好像扯远了~

好了,那下面就看看LinkedList是怎么进行增、删、改、查的。

3、增

1)add(E e)

public boolean add(E e) {
    linkLast(e);
    return true;
}
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++;
}

因为LinkedList是链表结构,所以每添加一个元素就是让这个元素链接到链表的尾部。

add(E e)的核心是linkLast()方法,它对元素进行了真正添加操作,分为以下几个步骤:

  1. 先让此时集合中的尾节点(即last"指针"指向的节点)赋给变量 l 。
  2. 然后,创建一个新节点,结合Node的构造函数,我们可以知道,在创建新节点(newNode)的同时,newNode的prev指向了l(即之前集合中的尾节点),变量 l 就是newNode的前驱节点了,newNode的后继节点为null。
  3. 再将last指向newNode,也就是说newNode成为该链表新的末尾节点。
  4. 接着,判断变量 l 是否为null,若是null,说明之前集合中没有元素(此时newNode是集合中唯一一个元素),则将first指向newNode,也就是说此时的newNode既是头节点又是尾节点(要知道,这时newNode中的prev和next均是null,但被first和last同时指向);

    若变量 l 不是null,说明之前集合中已经存在了至少一个元素,则让之前集合中的尾节点(即变量 l )的next指向newNode。(结合步骤2,此时的newNode与newNode的前驱节点 l 已经是相互指向了)
  5. 最后,跟ArrayList一样,让记录集合长度的size加1。

通过对add(E e)方法的分析,我们也知道了,原来LinkedList中的元素就是一个个的节点(Node),而真正的数据则存放在Node之中(数据被Node的item所引用)。

2)add(int index, E element)

public void add(int index, E element) {
    checkPositionIndex(index);

    if (index == size)
        linkLast(element);
    else
        linkBefore(element, node(index));
}

该add方法将添加集合元素分为2种情况,一种是在集合尾部添加,另一种是在集合中间或头部添加,因为第一种情况也是调用linkLast()方法,这里不再啰嗦,我们看看第二种情况,分析linkBefore(E e, Node<E> 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;
    else
        pred.next = newNode;
    size++;
    modCount++;
}

往LinkedList集合中间或头部添加元素分为以下几个步骤:

  1. 先调用node(int index)方法得到指定位置的元素节点,也就是linkBefore()方法中的形参 succ。
  2. 然后,通过succ.prevt得到succ的前一个元素pred。(此时拿到了第index个元素succ,和第index-1个元素pred)
  3. 再创建一个新节点newNode,newNode的prev指向了pred,newNode的next指向了succ。(即newNode往succ和pred的中间插入,并单向与它们分别建立联系,eg:pred ← newNode → succ
  4. 再让succ的prev指向newNode。(succ与跟newNode建立联系了,此时succ与newNode是双向关联,eg:pred ← newNode ⇋ succ)。
  5. 接着,判断pred是否为null,若是null,说明之前succ是集合中的第一个元素(即index值为0),现在newNode跑到了succ前面,所以只需要将first指向newNode(eg:first ⇌ newNode ⇋ succ);

    若pred不为null,则将pred的next指向newNode。(这时pred也主动与newNode建立联系了,此时pred与newNode也是双向关联,eg:pred ⇌ newNode ⇋ succ
  6. 最后,让记录集合长度的size加1。

对于链表的操作还是有些复杂的,特别是这种双向链表,不过仔细理解下,也不是什么问题(看不懂的可以边看步骤边动手画一画)。到这里,对于LinkedList的第一个添加方法就分析完了。

下面是对node(int index)方法的分析:

这也是LinkedList获取元素的核心方法,相当重要,因为后面会出现很多次,这里就顺带先分析一下了。

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

  细看node(int index)方法中的代码逻辑,可以看到,它是通过遍历的方式,将集合中的元素一个个拿出来,再通过该元素的prev或next拿到下一个遍历的元素,经过index次循环后,最终才拿到了index对应的元素。

  跟ArrayList相比,因为ArrayList底层是数组实现,拥有下标这个特性,在获取元素时,不需要对集合进行遍历,所以查找某个元素会特别快(在数据量特别多的情况下,ArrayList和LinkedList在效率上的差别就相当明显了)。

  不过,LinkedList对元素的获取还是做了一定优化的,它对index与集合长度的一半做比较,来确定是在集合的前半段还是后半段进行查找。

4、删

1)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) {
        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;
}

在remove(int index)这个方法中,先通过index和node(int index)拿到了要被删除的元素x,然后调用了unlink(Node<E> x)方法将其删除,自然,LinkedList删除元素的核心方法就是unlink(Node<E> x),删除操作分以下几个步骤:

  1. 通过要删除的元素x拿到它的前驱节点prev和后继节点next。
    LinkedList源码分析-JEESNS

  2. 若前驱节点prev为null,说明x是集合中的首个元素,直接将first指向后继节点next即可;
    LinkedList源码分析-JEESNS


    若不为null,则让前驱节点prev的next指向后继节点next,再将x的prev置空。(这时prev与x的关联就解除了,并与next建立了联系)。
    LinkedList源码分析-JEESNS


  3. 若后继节点next为null,说明x是集合中的最后一个元素,直接将last指向前驱节点prev即可;(下图分别对应步骤2中的两种情况)
    LinkedList源码分析-JEESNS


    若不为null,则让后继节点next的prev指向前驱节点prev,再将x的next置空。(这时next与x的关联就解除了,并与prev建立了联系)。
    LinkedList源码分析-JEESNS

  4. 最后,让记录集合长度的size减1。

2)remove(Object o)

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

remove(Object o)这个删除元素的方法的形参o是数据本身,而不是LinkedList集合中的元素(节点),所以需要先通过节点遍历的方式,找到o数据对应的元素,然后再调用unlink(Node<E> x)方法将其删除,关于unlink(Node<E> x)的分析在第一个删除方法中已经提到了,可往回再看看。

5、查 & 改

LinkedList集合对数据的获取与修改均通过node(int index)方法来执行往后的操作,关于node(int index)方法的分析也已经在第一个添加方法的时候已经提过,这里也就不再啰嗦了。

1)set(int index, E element)

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

2)get(int index)

public E get(int index) {
    checkElementIndex(index);
    return node(index).item;
}

三、总结

  1. LinkedList是基于链表实现的,并且是双向链表。
  2. LinkedList中的元素就是一个个的节点,而真正的数据则存放在Node之中。
  3. LinkedList通过遍历的方式获取集合中的元素,效率比ArrayList低。
文章评论