总结（一）ArrayList与LinkedList的优缺点，

来源： javaer 分享于 2019-05-31 点击 16817 次点评：137

总结（一）ArrayList与LinkedList的优缺点，

一丶ArrayList
ArrayList是动态扩展数组，底层是用数组实现，插入位置有三种情况，从首位插入，中间位置插入，尾部插入。线性表的插入删除操作都是通过移动来实现的，由于数组长度固定不变，插入数据时，需要一个新的数组。1.当添加数据是在首位插入时，先将新的数据放入到新的数组内，然后将原始数组中的数据复制到新的数组。
2.当数据插入的位置是中间位置时，先将插入位置前面的数据先放到新的数组里，再放新的数据，再复制旧的数据完成添加。3.数据尾部插入，由于不会影响其他元素，因此会直接插入到后面。
同样，删除按位置也有三种情况：1.从头部删除，删除头结点然后移动后面的数据
2.从中间指定位置删除，找到要删除数据的位置，删除后，后面的数据移动.3.从尾部删除：直接删除尾部数据完成删除操作。

二、LinkedList
LinkedList是双向链表的数据结构，底层是用链表实现，是由相互引用的节点组成的双向链表，当插入数据到某个位置时，这个数据会形成一个新的节点，然后改变链表中对应的两个节点的引用关系就可以完成插入。同样，删除数据时，删除对应节点的引用就可以完成删除操作

下面，展示ArrayList与LinkedList的增、删、查代码对比

添加数据操作

import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;

import org.junit.Test;

public class ListAddDemo {
    @Test
    public void ArrayListTailAddTest() {
        List<String> arrList = new ArrayList<String>();
        long startTime = System.currentTimeMillis();
        long startMemory = Runtime.getRuntime().freeMemory();
        for (int i = 0; i < 100000; i++) {
            arrList.add("Hello World!"); // 尾部插入
        }
        long endTime = System.currentTimeMillis();
        long endMemory = Runtime.getRuntime().freeMemory();
        System.out.println("ArrayList尾部添加十万个数据所花费的时间：" + (endTime - startTime) + "毫秒");
        System.out.println("ArrayList尾部添加操作消耗内存:" + (startMemory - endMemory)/1024 + "Kb");
    }

    @Test
    public void LinkedListAddTest() {
        List<String> lnkList = new LinkedList<String>();
        long startTime = System.currentTimeMillis();
        long startMemory = Runtime.getRuntime().freeMemory();
        for (int i = 0; i < 100000; i++) {
            lnkList.add("Hello World!");
        }
        long endTime = System.currentTimeMillis();
        long endMemory = Runtime.getRuntime().freeMemory();
        System.out.println("LinkedList添加十万个数据所花费的时间：" + (endTime - startTime) + "毫秒");
        System.out.println("LinkedList添加操作消耗内存:" + (startMemory - endMemory)/1024 + "Kb");
    }

    @Test
    public void ArrayListHeadAddTest() {
        List<String> arrList = new ArrayList<String>();
        long startTime = System.currentTimeMillis();
        long startMemory = Runtime.getRuntime().freeMemory();
        for (int i = 0; i < 100000; i++) {
            arrList.add(0, "Hello World!!");// 头部插入
        }
        long endTime = System.currentTimeMillis();
        long endMemory = Runtime.getRuntime().freeMemory();
        System.out.println("ArrayList头部添加十万个数据所花费的时间：" + (endTime - startTime) + "毫秒");
        System.out.println("ArrayList头部添加操作消耗内存:" + (startMemory - endMemory)/1024 + "Kb");
    }
}

测试结果

LinkedList添加十万个数据所花费的时间：5毫秒
LinkedList添加操作消耗内存:2662Kb
ArrayList头部添加十万个数据所花费的时间：1006毫秒
ArrayList头部添加操作消耗内存:880Kb
ArrayList尾部添加十万个数据所花费的时间：6毫秒
ArrayList尾部添加操作消耗内存:1201Kb

删除数据操作

import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;

import org.junit.Test;

public class ListDelDemo {
    @Test
    public void ArrayListHeadDelTest() {
        List<String> arrList = new ArrayList<String>();
        for (int i = 0; i < 100000; i++) {
            arrList.add("Hello World!!");
        }
        List<String> arrList2 = arrList;
        long startTime = System.currentTimeMillis();
        long startMemory = Runtime.getRuntime().freeMemory();
        for (int i = 0; i < arrList.size(); i++) {
            arrList2.remove(i); // 头部删除
            i--;
        }
        long endTime = System.currentTimeMillis();
        long endMemory = Runtime.getRuntime().freeMemory();
        System.out.println("ArrayList头部删除十万个数据所花费的时间：" + (endTime - startTime) + "毫秒");
        System.out.println("ArrayList头部删除操作消耗内存:" + (endMemory - startMemory) + "b");
    }

    @Test
    public void LinkedListDelTest() {
        List<String> lnklist = new LinkedList<String>();
        for (int i = 0; i < 100000; i++) {
            lnklist.add("Hello World!");
        }
        List<String> lnkList2 = lnklist;
        long startTime = System.currentTimeMillis();
        long startMemory = Runtime.getRuntime().freeMemory();
        for (int i = 0; i < lnklist.size(); i++) {
            lnkList2.remove(i);
            i--;
        }
        long endTime = System.currentTimeMillis();
        long endMemory = Runtime.getRuntime().freeMemory();
        System.out.println("LinkedList删除十万个数据所花费的时间：" + (endTime - startTime) + "毫秒");
        System.out.println("LinkedList删除操作消耗内存:" + (endMemory - startMemory) + "b");
    }

    @Test
    public void ArrayListDelTailTest() {
        List<String> arrList = new ArrayList<String>();
        for (int i = 0; i < 100000; i++) {
            arrList.add(0, "Hello World!!");// 头部插入
        }
        List<String> arrList2 = arrList;
        long startTime = System.currentTimeMillis();
        long startMemory = Runtime.getRuntime().freeMemory();
        for (int i = arrList.size() - 1; i >= 0; i--) {
            arrList2.remove(i); // 尾部删除
        }
        long endTime = System.currentTimeMillis();
        long endMemory = Runtime.getRuntime().freeMemory();
        System.out.println("ArrayList尾部删除十万个数据所花费的时间：" + (endTime - startTime) + "毫秒");
        System.out.println("ArrayList尾部删除操作消耗内存:" + (endMemory - startMemory) + "b");
    }

}

测试结果

ArrayList头部删除十万个数据所花费的时间：997毫秒
ArrayList头部删除操作消耗内存:0b
ArrayList尾部删除十万个数据所花费的时间：3毫秒
ArrayList尾部删除操作消耗内存:0b
LinkedList删除十万个数据所花费的时间：5毫秒
LinkedList删除操作消耗内存:0b

查询数据操作

import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;

import org.junit.Test;

public class ListQueryDemo {
    @Test
    public void ArrayQueryTest(){
        List<String> arrList=new ArrayList<String>();
        for(int i=0;i<100000;i++){
            arrList.add("Hello World!");
        }
        long startTime=System.currentTimeMillis();
        long startMemory=Runtime.getRuntime().freeMemory();
        for(int j=0;j<arrList.size();j++){
            int list=arrList.indexOf(j);
        }
        long endTime=System.currentTimeMillis();
        long endMemory=Runtime.getRuntime().freeMemory();
        System.out.println("ArrayList查询操作消耗时间:"+(endTime-startTime)+"毫秒");
        System.out.println("ArrayList查询操作消耗内存:"+(startMemory-endMemory)/1024+"Kb");
    }

    @Test
    public void LinkedQueryTest(){
        List<String> lnkList=new LinkedList<String>();
        for(int i=0;i<100000;i++){
            lnkList.add("Hello World!");
        }
        long startTime=System.currentTimeMillis();
        long startMemory=Runtime.getRuntime().freeMemory();
        for(int j=0;j<lnkList.size();j++){
            int list=lnkList.indexOf(j);
        }
        long endTime=System.currentTimeMillis();
        long endMemory=Runtime.getRuntime().freeMemory();
        System.out.println("LinkedList查询操作消耗时间:"+(endTime-startTime)+"毫秒");
        System.out.println("LinkedList查询操作消耗内存:"+(startMemory-endMemory)/1024+"Kb");
    }

}

测试结果

ArrayList查询操作消耗时间:6074毫秒
ArrayList查询操作消耗内存:665Kb
LinkedList查询操作消耗时间:26755毫秒
LinkedList查询操作消耗内存:1996Kb

有一个值得思考的问题

当ArrayList通过foreach循环遍历删除时会出错

import java.util.ArrayList;

public class ListDelTest {
    public static void main(String[] args) {
        ArrayList<String> arrList = new ArrayList<String>();
        for (int i = 0; i < 100000; i++) {
            arrList.add("Hello World!");
        }
        ArrayList<String> arrList2 = arrList;
        long startTime = System.currentTimeMillis();
        long startMemory = Runtime.getRuntime().freeMemory();
        for (String a : arrList) {
            arrList2.remove(a);
        }
        long endTime = System.currentTimeMillis();
        long endMemory = Runtime.getRuntime().freeMemory();
        System.out.println("ArrayList删除十万个数据所花费的时间：" + (endTime - startTime) + "毫秒");
        System.out.println("ArrayList删除操作消耗内存:" + (endMemory - startMemory) + "b");
    }
}

找到报错的源码：

  public E next() {
            checkForComodification();
            int i = cursor;
            if (i >= size)
                throw new NoSuchElementException();
            Object[] elementData = ArrayList.this.elementData;
            if (i >= elementData.length)
                throw new ConcurrentModificationException();
            cursor = i + 1;
            return (E) elementData[lastRet = i];
        }

  final void checkForComodification() {
            if (modCount != expectedModCount)
                throw new ConcurrentModificationException();
        }

究其原因：foreach循环会根据list创建iterator对象，然后使用iterator进行遍历，在遍历过程中,List修改了元素，进行了remove操作，List中modCount会发生改变，而生成iterator时会保留一个参数expectedModCount,当这个参数与modCount不一致时会抛出异常。
下面给出ArrayList里remove()方法源码，

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

从源码中可以发现，进行remove操作时，modCount会+1，而exceptedModCount没有发生改变，从而出现错误。查看源码时，细心一点会发现Iterator中也有一个remove()方法

public void remove() {
            if (lastRet < 0)
                throw new IllegalStateException();
            checkForComodification();

            try {
                ArrayList.this.remove(lastRet);
                cursor = lastRet;
                lastRet = -1;
                expectedModCount = modCount;
            } catch (IndexOutOfBoundsException ex) {
                throw new ConcurrentModificationException();
            }
        }

可以看出，Iterator多了一个操作，exceptedModCount=modCount;从而不会出错。
因此，使用迭代器遍历进行删除操作时，使用迭代器里的remove()方法，就不会出现错误。

总结

ArrayList的优点在于可以顺序存储，随机存取,数据元素与位置相关联，因此查找效率高，索引遍历快，尾部插入与删除的速度与LinkedList的速相差无几。
缺点：线程不安全，插入与删除慢，需要通过移动元素来实现，因此效率低。
LinkedList的优点在于删除和添加数据所消耗的资源较少，且比ArrayList效率高。
缺点：线程不安全，查找消耗的资源大，效率低，不能随机访问。

总结（一）ArrayList与LinkedList的优缺点，