技术成就梦想

代码如诗

原 Jdk1.8 Collections Framework源码解析(2)-LinkedList 灯-塔

2017年8月31日 Java 0

ArrayList的插入和删除元素的操作会花费线性时间,那么有没有插入和删除元素比较省时的集合呢,看下LinkedList这个实现。 老样子,先看看它实现了那些接口。

public class LinkedList<E>
    extends AbstractSequentialList<E>
    implements List<E>, Deque<E>, Cloneable, java.io.Serializable

之前看过的接口不看了。先看下java.util.Deque。

public interface Deque<E> extends Queue<E>  

这个接口扩展了java.util.Queue,Queue也是Java Collections Framework中一个重要的接口,它表示了队列。当然队列本身也属于集合(java.util.Collection是更高层次的抽象)。

public interface Queue<E> extends Collection<E>{  
    boolean add(E e);  
    boolean offer(E e);  
    E remove();  
    E poll();  
    E element();  
    E peek();  
} 

Queue提供了添加、删除和获取元素的方法,每种方法提供2个版本。如添加元素,add和offer都可以完成这个操作,区别在于add方法如果添加失败会抛出异常,而offer方法则会返回false。Queue接口只提供队列的抽象概念,但并没有定义元素的操作顺序。其实现可以提供先入先出或者先入后出(栈)这样的性质。

大概了解了java.util.Queue后继续看java.util.Deque。

public interface Deque<E> extends Queue<E> {  
    void addFirst(E e);  
    void addLast(E e);  
    boolean offerFirst(E e);  
    boolean offerLast(E e);  
    E removeFirst();  
    E removeLast();  
    E pollFirst();  
    E pollLast();  
    E getFirst();  
    E getLast();  
    E peekFirst();  
    E peekLast();  
    boolean removeFirstOccurrence(Object o);  
    boolean removeLastOccurrence(Object o);  
    void push(E e);  
    E pop();  
    Iterator<E> descendingIterator();  
}

像Queue接口一样,Deque也对这些操作方法提供了2个版本。

接下来看一下java.util.AbstractSequentialList这个抽象类,这个类的作用和java.util.AbstractList作用一样,提供一些“骨架”实现。区别在于这个类提供了“按次序访问”的基础,而AbstractList提供了“自由访问”的基础。也就是说,如果我们要实现一个基于链表的集合的话,可以继承这个类;要实现基于数组的集合的话,就继承AbstractList类。

在看LinkedList的源代码之前,还是先思考一下,如果自己实现LinkedList要怎么做?

思考中……

既然是链表,那么内部一定会有一个“链”,而“链”是由“环”组成,说明内部会有“环”这样的概念。每个环都和下一个环相扣,有两个特殊的环,首环和尾环。首先,没有任意一环的下一环是首环,尾环没有下一环;然后,首环和尾环上是不携带数据的(当然普通环也是可以保存null元素滴)。如果再从代码上考虑一下,每一个环都有下一个环的引用,这样可以构成一个链。但每个环也可以即有上一个环的引用,又有下一个环的引用,也可以构成链。它们有什么区别呢?其实这就是所谓的单向链表和双向链表,java.util.LinkedList内部使用双向链表实现。那可以使用单向链表实现吗?那就试试吧。 这个不放参考一些之前《算法4》的一个实现。 通过查看OpenJDK的源码我们可是可以,对比不同JDK版本,的实现。

看来一下,LinkedList 类开头的注释,大概是这样说的, LinkedList 是基于 List 的一个双向链表实现的一个数据结构。

Doubly-linked list implementation of the {@code List} and {@code Deque} interfaces. Implements all optional list operations, and permits all elements (including {@code null}).

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;

通过上面的源码,我们看到,做为双向链表实现,必然会有一个 头指针 first 和 尾指针last , 通过用双向链表,整个链表的数据结构在遍历的时候就会有所选择的,从头遍历还是从尾部遍历,这样就会加快效率,但是它是如何知道是什么时候该是从头遍历,什么时候该从尾部遍历呢?

看看,链表的数据结构,非常简单。

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

我们在看看LikedList 的 的添加操作:

    /**
     * Links e as first element.
     */
    private void linkFirst(E e) {
        final Node<E> f = first;
        final Node<E> newNode = new Node<>(null, e, f);
        first = newNode;
        if (f == null)
            last = newNode;
        else
            f.prev = newNode;
        size++;
        modCount++;
    }

    /**
     * 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;
        else
            l.next = newNode;
        size++;
        modCount++;
    }

    /**
     * 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;
        else
            pred.next = newNode;
        size++;
        modCount++;
    }

元素数据的查询,主要是通过下面的2个方法来实现的:

   /**
     * Returns the index of the first occurrence of the specified element
     * in this list, or -1 if this list does not contain the element.
     * More formally, returns the lowest index {@code i} such that
     * <tt>(o==null&nbsp;?&nbsp;get(i)==null&nbsp;:&nbsp;o.equals(get(i)))</tt>,
     * or -1 if there is no such index.
     *
     * @param o element to search for
     * @return the index of the first occurrence of the specified element in
     *         this list, or -1 if this list does not contain the element
     */
    public int indexOf(Object o) {
        int index = 0;
        if (o == null) {
            for (Node<E> x = first; x != null; x = x.next) {
                if (x.item == null)
                    return index;
                index++;
            }
        } else {
            for (Node<E> x = first; x != null; x = x.next) {
                if (o.equals(x.item))
                    return index;
                index++;
            }
        }
        return -1;
    }

    /**
     * Returns the index of the last occurrence of the specified element
     * in this list, or -1 if this list does not contain the element.
     * More formally, returns the highest index {@code i} such that
     * <tt>(o==null&nbsp;?&nbsp;get(i)==null&nbsp;:&nbsp;o.equals(get(i)))</tt>,
     * or -1 if there is no such index.
     *
     * @param o element to search for
     * @return the index of the last occurrence of the specified element in
     *         this list, or -1 if this list does not contain the element
     */
    public int lastIndexOf(Object o) {
        int index = size;
        if (o == null) {
            for (Node<E> x = last; x != null; x = x.prev) {
                index--;
                if (x.item == null)
                    return index;
            }
        } else {
            for (Node<E> x = last; x != null; x = x.prev) {
                index--;
                if (o.equals(x.item))
                    return index;
            }
        }
        return -1;
    }

LikedList 默认是从头部开始查询,同时也提供了从尾部查询的方法。