通过分析uml图和jdk源代码对LinkedList和ArrayList的区别进行验证分析

一.概述

最近想换新工作,之前面试了几个感觉双方都不怎么看得上对方,年龄也到了40岁的瓶颈了,又赶上快年底了,还是做些准备工作吧,工作不好找啊。
这不一准备就网上找资料了,偶然看到B站的《华为大牛透彻讲解Java面试100道必考题》蛮适合我的胃口,想想光看还不够深刻,得加深一下印象,于是乎就想来深挖了一下。
本文选取了ArrayList和LinkedList之间的区别这么一讲,来进行具体分析分析。

二.大神介绍

首先对大神对两者之间区别的介绍截图如下。
通过分析uml图和jdk源代码对LinkedList和ArrayList的区别进行验证分析
总结了下,大神主要讲了几点:

  1. 存储方式不同
    ArrayList:基于动态数组,连续内存存储。
    LinkedList:基于链表,可以存储在分散的内存中。
  2. 擅长操作
    ArrayList:适合下标访问(随机访问),尾插法并指定容量的插入。
    LinkedList:适合做数据插入及删除操作。
  3. 不擅长操作
    ArrayList: 超出长度的扩容,需要新建数组,然后老数据拷贝到新数组;不是尾部的插入,涉及数据元素的移动。
    LinkedList:不适合查下,不能用for循环,不要试图用indexOf返回元素索引。

三.UML分析

在IDEA中随便新建一个工程,找到External Libraries,找到其中的jdk,展开rt.jar,在java下的util中点鼠标右键,选择Diagrams->Show Diagram…选项。
通过分析uml图和jdk源代码对LinkedList和ArrayList的区别进行验证分析
选择Java Class Diagrams选项,则打开了java.util包的类图。
通过分析uml图和jdk源代码对LinkedList和ArrayList的区别进行验证分析
接下来再类图中选择其他跟本次不相关的内容,按delete删除掉,只保留List相关的内容,最后结果如下:
通过分析uml图和jdk源代码对LinkedList和ArrayList的区别进行验证分析
由改图可以先对两者的继承和实现情况进行分析。

  1. 首先两者都实现了List接口,List接口继承了Collection接口,Collection则继承了Iterable接口。
  2. ArrayList还继承了RandomAccess接口,但是打开RandomAccess接口的内容发现,该接口为空,未实现任何内容,我们暂时先不管。
package java.util;

public interface RandomAccess {
}

两者都继承了AbstractList类,不同的是LinkedList是通过AbstractSequentialList来继承AbstractList,ArrayList直接继承至AbstractList。
对AbstractSequentialList 和LinkedList的比较分析。

  • AbstractSequentialList共实现了get、set、add、remove 、addAll、Iterator六个方法和定义了listIterator一个抽象方法。
  • LinkedList对AbstractSequentialList实现的方法都进行了重写。

四.源码分析

本节内容根据参考大神的介绍,从源码中进行不同点进行分析。

(一) 存储方式

1.分析ArrayList为数组存储

查看ArrayList可以看到如下代码:

/**
     * Constructs an empty list with the specified initial capacity.
     *
     * @param  initialCapacity  the initial capacity of the list
     * @throws IllegalArgumentException if the specified initial capacity
     *         is negative
     */
    public ArrayList(int initialCapacity) {
        if (initialCapacity > 0) {
            this.elementData = new Object[initialCapacity];
        } else if (initialCapacity == 0) {
            this.elementData = EMPTY_ELEMENTDATA;
        } else {
            throw new IllegalArgumentException("Illegal Capacity: "+
                                               initialCapacity);
        }
    }
    /**
     * Constructs an empty list with an initial capacity of ten.
     */
    public ArrayList() {
        this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA;
    }

    /**
     * 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 ArrayList(Collection<? extends E> c) {
        elementData = c.toArray();
        if ((size = elementData.length) != 0) {
            // c.toArray might (incorrectly) not return Object[] (see 6260652)
            if (elementData.getClass() != Object[].class)
                elementData = Arrays.copyOf(elementData, size, Object[].class);
        } else {
            // replace with empty array.
            this.elementData = EMPTY_ELEMENTDATA;
        }
    }

从中可以看到ArrayList在创造的时候根据不同的参数去初始化 elementData 这个成员变量。
而elementData在代码中定位的为一个Object数据。

    /**
     * The array buffer into which the elements of the ArrayList are stored.
     * The capacity of the ArrayList is the length of this array buffer. Any
     * empty ArrayList with elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA
     * will be expanded to DEFAULT_CAPACITY when the first element is added.
     */
    transient Object[] elementData; // non-private to simplify nested class access

查看对elementData的注释同样可以看出,elementData这个是ArrayList 用来存储元素的一个数组。ArrayList 的容量为elementData的长度。
由此可见ArrayList存储的内容确实是为数组。

2. 分析ArrayList为动态数组

查看ArrayList的Add方法

    /**
     * Appends the specified element to the end of this list.
     *
     * @param e element to be appended to this list
     * @return <tt>true</tt> (as specified by {@link Collection#add})
     */
    public boolean add(E e) {
        ensureCapacityInternal(size + 1);  // Increments modCount!!
        elementData[size++] = e;
        return true;
    }

查看ensureCapacityInternal

    private void ensureCapacityInternal(int minCapacity) {
        if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {
            minCapacity = Math.max(DEFAULT_CAPACITY, minCapacity);
        }

        ensureExplicitCapacity(minCapacity);
    }
        private void ensureExplicitCapacity(int minCapacity) {
        modCount++;

        // overflow-conscious code
        if (minCapacity - elementData.length > 0)
            grow(minCapacity);
    }

最后跟踪到grow函数。

    /**
     * Increases the capacity to ensure that it can hold at least the
     * number of elements specified by the minimum capacity argument.
     *
     * @param minCapacity the desired minimum capacity
     */
    private void grow(int minCapacity) {
        // overflow-conscious code
        int oldCapacity = elementData.length;
        int newCapacity = oldCapacity + (oldCapacity >> 1);
        if (newCapacity - minCapacity < 0)
            newCapacity = minCapacity;
        if (newCapacity - MAX_ARRAY_SIZE > 0)
            newCapacity = hugeCapacity(minCapacity);
        // minCapacity is usually close to size, so this is a win:
        elementData = Arrays.copyOf(elementData, newCapacity);
    }

可以看到ArrayList会在插入新数据时,如果原数组长度不够,则会扩容数组长度。

3.LinkedList

同样查看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);
    }

由于无参的构造函数内无代码,我们看另一构造函数对其中addAll©进行分析。

/**
     * Inserts all of the elements in the specified collection into this
     * list, starting at the specified position.  Shifts the element
     * currently at that position (if any) and any subsequent elements to
     * the right (increases their indices).  The new elements will appear
     * in the list in the order that they are returned by the
     * specified collection's iterator.
     *
     * @param index index at which to insert the first element
     *              from the specified collection
     * @param c collection containing elements to be added to this list
     * @return {@code true} if this list changed as a result of the call
     * @throws IndexOutOfBoundsException {@inheritDoc}
     * @throws NullPointerException if the specified collection is null
     */
    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;
    }

查看到其中的核心内容是对Collection参数的内容进行遍历,依次建立Node,然后通过node的next和prev进行上下元素之间的关联。
其中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;
      }
  }

其中有三个参数,item为元素自己,next指向下一元素,prev指向上一元素。
由此可见LinkedList存储的内容为链表。

(二) 擅长操作

1. ArrayList访问

查看ArrayList的get方法。两步操作,首先检查下标是否超出,超出直接返回该下标数据。

    /**
     * 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) {
        rangeCheck(index);

        return elementData(index);
    }

查看add代码,如果ArrayList的容量足够,add直接在尾部进行插入。因此容量足够的尾插法效率非常高。

    /**
     * Appends the specified element to the end of this list.
     *
     * @param e element to be appended to this list
     * @return <tt>true</tt> (as specified by {@link Collection#add})
     */
    public boolean add(E e) {
        ensureCapacityInternal(size + 1);  // Increments modCount!!
        elementData[size++] = e;
        return true;
    }

2.LinkedList

查看Add方法

   /**
     * Inserts the specified element at the specified position in this list.
     * Shifts the element currently at that position (if any) and any
     * subsequent elements to the right (adds one to their indices).
     *
     * @param index index at which the specified element is to be inserted
     * @param element element to be inserted
     * @throws IndexOutOfBoundsException {@inheritDoc}
     */
    public void add(int index, E element) {
        checkPositionIndex(index);

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

看里面两个函数,linkLast(链接到最后)、linkBefore(链接到之前),从函数的意思就觉得非常高效,实际的过程中,也可以出操作的过程为新建了一个node对象,然后进行相关赋值。

    /**
     * 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++;
    }

(三) 不擅长操作

1.ArrayList 超长扩容。

可以查看 “分析ArrayList为动态数组”部分的内容,ArrayList在插入的过程中,如果长度超过设定长度时,需要进行扩容(扩容的过程为新建一新数组,然后把老数组复制到新数组)。如果不是尾部插入还需要进行元素的移动。

2. LinkedList

不适合for循环,查看get(i)->node(index)方法,发现每次get的过程中都需要对链表的内容进行遍历。因此如果对LinkedList进行for循环,那么遍历的次数那是相当的多。

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

不要试图用indexOf返回元素索引,同样查看代码也可以看出LinkedList的indexOf函数也需要对链表进行遍历操作。

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

四、结束语

通过以上几个轮次的分析,对于LinkedList和ArrayList总数也有了一定的认识,之后写代码的时候也会多注意,不再一上来就用LinkedList或上来就ArrayList,要根据实际的需求来进行统筹的安排。

上一篇:Linux usb 6. HC/UDC 测试


下一篇:C# 随机生成验证码