ArrayList与LinkedList大比拼之add和remove，

ArrayList与LinkedList大比拼之add和remove，

ArrayList与LinkedList大比拼之add和remove






各大公司的Java面试都会考到一些java源码的问题，这个系列我将一一为大家剖析
各种java重要的源码


ArrayList与LinkedList是经常会进行比较的2个类，因为他们都实现了List类
本质上讲，他们底层存储方式是不一样的

private transient Object[] elementData;

这个是ArrayList的底层存储方式，是一个对象数组
而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;
        }
    }

这就是LinkedList的一个内部类，也是它的存储方式,其实LinkedList的存储方式就是一个双向链表
所以下面所说的区别，其实也就是数据结构是顺序存储结构和链式存储结构的区别
先看添加,add方法
ArrayList:

public boolean add(E e) {
        ensureCapacityInternal(size + 1);  // Increments modCount!!
        elementData[size++] = e;
        return true;
    }
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++;
    }

ArrayList重载的这2种add方法，其中都调用了ensureCapacityInternal(size + 1);这个方法一直查看调用，会发现这个方法其实
就是新创建一个长度为size+1的数组，然后将现在数组的值拷贝上去，如果是add(E e)，拷贝完成后将e放到最后即可，如果是
add(int index, E element),则需要再进行一次拷贝，建index以及之后的元素后移一位，然后再讲元素放到index位置即完成，补充
一句这里的拷贝都是native层实现。
LinkedList:

public boolean add(E e) {
        linkLast(e);
        return true;
    }
public void add(int index, E element) {
        checkPositionIndex(index);


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

可以看到当添加到末尾的时候都调用了linkLast(e);方法

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

其实就是新建一个Node然后放到最后，如果不是添加到末尾的时候先调用node(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;
        }
    }

这里的查找也做了一定的优化，判断这个节点是离头近还是离尾近，然后调用linkBefore方法插入

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

再看删除,remove方法
ArrayList:

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

如果要按照索引删除，先copy(删除索引位置元素,并调整后面元素位置)，然后将最后一个元素置空，方便GC回收
modCount++;是因为modCount是记录这个ArrayList对象的修改次数
如果要按照元素删除的话，其实是先找到索引然后调用fastRemove()

private void fastRemove(int index) {
        modCount++;
        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
    }

这个方法其实和按照索引删除基本一样，只不过少了个索引的越界检查，因为这个是查找到的
LinkedList:

public E remove() {
        return removeFirst();
    }
public E remove(int index) {
        checkElementIndex(index);
        return unlink(node(index));
    }
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;
    }

如果是直接删除，调用removeFirst方法

public E removeFirst() {
        final Node<E> f = first;
        if (f == null)
            throw new NoSuchElementException();
        return unlinkFirst(f);
    }

LinkedList默认是删除第一个元素
如果是按照索引删除，先运用node()找到这个元素，前面已经介绍过了，然后调用unlink()方法，

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

如果是按照元素删除，则是先找到那个元素，然后还是调用unlink()方法


总结：1.总体来看ArrayList和LinkedList的add和remove方法，LinkedList要更加简单一点，效率也更快，原因还
是因为，存储结构的不同
 2.还有就是会发现一个我们没有见过的属性modCount，记录修改次数，这个属性有什么用呢，后边慢慢给大家讲
 3.对了，补充一点，查看继承关系，会发现，ArrayList是继承了AbstractList，AbstractList才实现了List,而
LinkedList是直接实现了List,所以LinkedList可以说是ArrayList的叔叔
 
 
 下一篇将详细解析ArrayList和LinkedList的查询和修改