底层实现和树的关系

概述

java中常用的list有LinkedList、ArrayList，他们的区别是底层的数据存储，对于LinkedList而言，底层采用的是链表，而对于 ArrayList而言，底层采用的是数组，链表的特点是能够很方便的使用内存碎片，并且加入、删除元素的过程由于仅仅需要改动指针， 因此是常量级别的响应时间，而对于数组而言，其底层的存储空间要求是连续的，因此需要分配大量的连续空间，不过因为其内存空间 连续的特点，我们可以以常量的访问时间获取元素，不过当我们针对ArrayList中的元素进行增加或者删除的时候，需要移动大量的 元素，因此当数据结构有变化的时候其操作的效率是比较低的，而数组的特点则是可以以常量的

详解

先来看一下LinkedList，其类图如下所示：

我们先来看一下该类上面的注释：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
/**
 * Doubly-linked list implementation of the {@code List} and {@code Deque}
 * interfaces.  Implements all optional list operations, and permits all
 * elements (including {@code null}).
 *
 * <p>All of the operations perform as could be expected for a doubly-linked
 * list.  Operations that index into the list will traverse the list from
 * the beginning or the end, whichever is closer to the specified index.
 *
 * <p><strong>Note that this implementation is not synchronized.</strong>
 * If multiple threads access a linked list concurrently, and at least
 * one of the threads modifies the list structurally, it <i>must</i> be
 * synchronized externally.  (A structural modification is any operation
 * that adds or deletes one or more elements; merely setting the value of
 * an element is not a structural modification.)  This is typically
 * accomplished by synchronizing on some object that naturally
 * encapsulates the list.
 *
 * If no such object exists, the list should be "wrapped" using the
 * {@link Collections#synchronizedList Collections.synchronizedList}
 * method.  This is best done at creation time, to prevent accidental
 * unsynchronized access to the list:<pre>
 *   List list = Collections.synchronizedList(new LinkedList(...));</pre>
 *
 * <p>The iterators returned by this class's {@code iterator} and
 * {@code listIterator} methods are <i>fail-fast</i>: if the list is
 * structurally modified at any time after the iterator is created, in
 * any way except through the Iterator's own {@code remove} or
 * {@code add} methods, the iterator will throw a {@link
 * ConcurrentModificationException}.  Thus, in the face of concurrent
 * modification, the iterator fails quickly and cleanly, rather than
 * risking arbitrary, non-deterministic behavior at an undetermined
 * time in the future.
 *
 * <p>Note that the fail-fast behavior of an iterator cannot be guaranteed
 * as it is, generally speaking, impossible to make any hard guarantees in the
 * presence of unsynchronized concurrent modification.  Fail-fast iterators
 * throw {@code ConcurrentModificationException} on a best-effort basis.
 * Therefore, it would be wrong to write a program that depended on this
 * exception for its correctness:   <i>the fail-fast behavior of iterators
 * should be used only to detect bugs.</i>

上面大概意思是说：

  • linkedList同时实现了List和Deque接口，并且允许List中的元素为null
  • 由于实现了一个双端队列的接口，当我们获取List中的某个元素的时候，其真实的操作是会选择性的选择队头或者队尾的元素作为起始节点。
  • LinkedList所有的操作都是线程非安全的，因此在存在多个线程并发的访问List的时候，我们需要通过外部的锁对象来保证并发访问的安全性， 或者通过Collections.synchronizedList来保障
  • 提供了fail-fast的机制，当我们的List在对应的iterator创建好之后，如果我们不是通过iterator对应的add或者remove方法改变了数据的话，当我们发现 List的结构发生了变化，说明可能是存在其他的线程操作了这个List，这个时候我们会抛出ConcurrentModificationException来终止当前的操作。 （如果我创建了iterator不用，我又通过add方法修改数据结构会抛出异常么？同一个线程的情况下。怎么样解决这个问题？）

java的集合中大量的使用了模版模式，也就是将公共的实现放到抽象类中（如有必要，提供默认的实现），针对不同的特性在子类中提供覆盖的 能力。

来看一下LinkedList类的成员变量：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
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;

对应的Node的定义如下：

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

由Node的定义我们也可以看出LinkedList是一个双向链表。

查看一下LinkeList继承的AbstractSequentialList的抽象类可以知道，我们的LinkedList只需要实现listIterator和size方法就可以了。 我们首先看一下AbstractSequentialList中方法listIterator被用到的地方可以看到如下代码：

1
2
3
4
5
6
7
public E get(int index) {
    try {
        return listIterator(index).next();
    } catch (NoSuchElementException exc) {
        throw new IndexOutOfBoundsException("Index: "+index);
    }
}

也即是当我们尝试获取某个位置的对象的时候就会调用listIterator方法，next方法会返回下一个元素并返回前一个游标（或者说指针），这里不是太清楚下一个元素指代的是哪一个元素， 因为按理说下表应该就是从0开始的（TODO）

续接上文，我们跟进一下在linkedList中listIterator的实现是什么样子的：

1
2
3
4
public ListIterator<E> listIterator(int index) {
    checkPositionIndex(index);
    return new ListItr(index);
}

第一步是针对查询的元素进行的合法性校验，后面会返回一个ListItr对象，该对象实现了ListIterator接口。不过很遗憾上面get方法被LinkedList给重写掉了，重写的方法如下：

1
2
3
4
public E get(int index) {
    checkElementIndex(index);
    return node(index).item;
}

这里最终会调用如下方法：

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

这个方法中我们可以看到，当我们获取某一个下标的数据的时候，LinkedList首先会判断该下标是离头节点近呢还是离尾节点近， 并根据这个条件选择从队头或者是队尾访问元素。

小结