List的两种实现对比

作者: xiaoshua | 来源:发表于2016-04-03 00:13 被阅读1011次

    前言

    在日常的java开发中,我们经常用到各种集合类,而List是其中最常见的一种;以前我们在使用数组的时候,无论是c++或者java,都要指定它的大小;而List居然不用指定大小,太神奇了,接下来让我们仔细分析一下它们的实现

    LinkedList:

    1. 主要成员变量:
    transient int size = 0; //List长度
    transient Node<E> first;//头指针
    transient Node<E> last;//尾指针
    
    1. add方法(将元素放入List尾部):
    public boolean add(E e) {
        linkLast(e);
        return true;
    }
    

    再看linkLast方法:

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

    也就是说,每次添加一个节点到末尾时,都是新申请一个链表节点,然后再缝缝补补,把相关的链表指针接在一起;复杂度为O(1);

    再看看另外一个add方法:

    1. add(int index, E element)(将元素插入到某个下标位置):
    public void add(int index, E element) {
        checkPositionIndex(index);
    
        if (index == size)
            linkLast(element);
        else
            linkBefore(element, node(index));
    }
    

    <p>
    再看node()方法(找到下标对应的链表节点):

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

    其寻址复杂度是O(n)的,唯一的优化点就在于,看下标离头指针近还是离尾指针近,复杂度做了常数上的优化,从n下降到n/2, 但还是O(n);
    剩下的删查都涉及到寻址的时间损耗,复杂度也都是O(n),它们的实现都是类似的,就不赘诉了。

    小优化:其实如果我们自己实现一个LinkedList,完全可以把指针信息加在节点上,这样就可以避免一些寻址上的时间损耗了。

    ArrayList(与c++里的vector类似)

    1. 成员变量:
    transient Object[] elementData; // 存储元素的载体是数组
    private int size;//List当前长度
    
    1. 主构造方法:
    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);
        }
    }
    没有什么特别的,就是申请一个定长的数组
    
    1. add(E e)方法:
    public boolean add(E e) {
        ensureCapacityInternal(size + 1);  // Increments modCount!!
        elementData[size++] = e;
        return true;
    }
    

    第一行是确保数组载体容量足够,后边就是把下标为size+1的元素赋值成e;
    它调用了ensureCapacityInternal()方法:

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

    又调用了ensureExplicitCapacity()方法:

    private void ensureExplicitCapacity(int minCapacity) {
        modCount++;
    
        // overflow-conscious code
        if (minCapacity - elementData.length > 0)
            grow(minCapacity);
    }
    

    再看grow()方法:

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

    里边关键的一句代码就是:

    int newCapacity = oldCapacity + (oldCapacity >> 1);
    

    意思就是,新的数组容量变成原数组的大约1.5倍(看不懂的可以去了解一下位运算),新的数组申请内存之后,再把老的数组里的元素全copy到新数组就完成了;
    那么为什么每次容量不足的时候,要扩充到1.5倍呢?通过分析我们可以发现,每次扩充1.5倍容量,那么假设最后容量扩充为n,那么总体上的申请空间的数量近似于:f(n) = n + n * 2/3 + n * (2/3)^2 + n * (2/3)^3 + ... ,根据等比数列公式可以知道,这个表达式的值为: f(n) = 3 * n = O(n)
    采用倍增的方法扩容,优点在于总体的复杂度数量级是线性的,但是也不可避免的可能会有空间浪费;在最极端的情况下,会有接近1/3的空间是没有利用上的;因此,在List会很大,且能预先大致估算出List会有多大的前提下,为了减少系统的内存消耗和频繁GC,应尽量使用以下构造方法来申请List:

    public ArrayList(int initialCapacity);
    
    1. add(int index, E element)方法(将元素插入到指定下标):
    public void add(int index, E element) {
        rangeCheckForAdd(index);
    
        ensureCapacityInternal(size + 1);  // Increments modCount!!
        System.arraycopy(elementData, index, elementData, index + 1,
                         size - index);
        elementData[index] = element;
        size++;
    }
    

    跟add(E element)方法的最大的差别就在于,在赋值之前,要先把该下标以及后面的元素全都向后移一位,其复杂度为O(n);

    1. 接下来看get(int index)方法:
    public E get(int index) {
        rangeCheck(index);
    
        return elementData(index);
    }
    

    检查下标合法性,再调用elementData():

    E elementData(int index) {
        return (E) elementData[index];
    }
    

    直接是数组的根据下标随机访问的操作,复杂度是O(1),再强转成E类型就返回了;

    1. remove(int index)方法:
    public E remove(int index) {
        rangeCheck(index);
    
        modCount++;
        E oldValue = elementData(index);
    
        int numMoved = size - index - 1;
        if (numMoved > 0)
            System.arraycopy(elementData, index+1, elementData, index,
                             numMoved);
        elementData[--size] = null; // clear to let GC do its work
    
        return oldValue;
    }
    

    在删除指定下标的元素时,如果这个元素不是最后一个,那么要将后面的元素全部向前移一位,复杂度也是O(n), 另外还有一点就是,删除了这个元素之后,要把最大下标的那个元素赋值成null,方便系统进行GC(系统GC时,会根据对象是否被引用来判断对象是否可以回收)

    1. remove(Object o)方法:
    public boolean remove(Object o) {
        if (o == null) {
            for (int index = 0; index < size; index++)
                if (elementData[index] == null) {
                    fastRemove(index);
                    return true;
                }
        } else {
            for (int index = 0; index < size; index++)
                if (o.equals(elementData[index])) {
                    fastRemove(index);
                    return true;
                }
        }
        return false;
    }
    

    定位到元素位置复杂度为O(n), fastRemove(index)的复杂度也是O(n);
    另外,初看这段代码,感觉写得有点“啰嗦”,但实际上确实是有必要的:List元素允许为空,所以要特判该元素是否为空,为空时直接用==null来判断,而不为空时,才能调用equals方法进行比较,否则会有空指针异常;所以这段代码也是JDK严谨性的一种体现;

    1. 以下表格列出了两者在各种操作下的复杂度:

    | 操作\List实现类 | LinkedList | ArrayList |
    | ------------- |:-------------:| -----:|
    | add(E e) | O(1) | O(1) |
    | add(int index, E element) | O(n) | O(n) |
    | get(int index) | O(n) | O(1) |
    | remove(int index) | O(n) | O(n) |
    | remove(Object o) | O(n) | O(n) |

    从上表看,LinkedList几乎没有比ArrayList优越的地方;另外,LinkedList相比ArrayList没有0.5倍的空间浪费,但是其每个节点都有前后指针的内存占用,且每次新增一个元素时都要新申请一个Node,而ArrayList则是一次性批量申请;所以,当List长度比较大的时候,肯定是ArrayList效率比较高。
    如果说LinkedList有优点的话,可能就是它不需要申请连续的内存,所以建议大家除了极端情况,大部分时候都使用ArrayList。

    相关文章

      网友评论

        本文标题:List的两种实现对比

        本文链接:https://www.haomeiwen.com/subject/ydxulttx.html