ArrayList与LinkedList

ArrayList

ArrayList适合随机的查找与遍历,数据的插入和删除相对来说较低

• 内部基于数组实现
• 可对元素进行快速随机访问
• 每个元素之间不能由间隔,即数组的空间是连续的
• 当需要扩容时需要将原数组数据复制到新的存储空间
  • 若在中间插入元素时,需要对数组进行复制,移动操作,代价高

LinkedList

LinkedList的插入删除元素相对来说较高,随机查找效率低下

• 内部基于链表实现
• 可对头部和尾部快速操作
• 每个元素之间可能有间隔,即链表的空间是不连续的,位置是由每个元素自己维护的

用代码实验下来,总体来说ArrayList的效率总体高与LinkedList,这个实验结论与我们众所周知的概念是有很大的出入,我已经迷失了 希望以后有更加准确的结论吧

public class ListTest {
    static int count = 100000;
    static int extra = 2000;
    private static Set<Integer> randomList = new HashSet<>(extra);

    static {
        Random random = new Random();
        for(int i = 0; i < extra; i++) {
            randomList.add(random.nextInt(count));
        }
    }

    /**
     * 这里的一个测试颠覆了我对list的认知
     */
    public static void main(String[] args) {
        //数组集合
        List<String> arrayList = new ArrayList<>();
        //链表集合
        List<String> linkList = new LinkedList<>();
        insert(arrayList);
        insert(linkList);
        System.out.println();
        insert4Half(arrayList);
        insert4Half(linkList);
        System.out.println();
        random(arrayList);
        random(linkList);
        System.out.println();
        randomInsert(arrayList);
        randomInsert(linkList);
        System.out.println();
        randomRemove(arrayList);
        randomRemove(linkList);
        System.out.println();
    }

    private static void insert(List<String> list) {
        long start = System.currentTimeMillis();
        for(int i = 0; i < count; i++) {
            list.add("" + i);
        }
        long elapsed = System.currentTimeMillis() - start;
        String prefix = list.getClass().getSimpleName();
        System.out.print(" <---> " + String.join("", prefix, "顺序插入耗时ms:", String.valueOf(elapsed)));
    }

    private static void insert4Half(List<String> list) {
        long start = System.currentTimeMillis();
        for(int i = 0; i < extra; i++) {
            list.add(list.size() / 2, "bbb" + i);
        }
        long elapsed = System.currentTimeMillis() - start;
        String prefix = list.getClass().getSimpleName();
        System.out.print(" <---> " + String.join("", prefix, "中间插入耗时ms:", String.valueOf(elapsed)));
    }

    private static void iterate(List<String> list) {
        long start = System.currentTimeMillis();
        for(int i = 0; i < list.size(); i++) {
            list.get(i);
        }
        long elapsed = System.currentTimeMillis() - start;
        String prefix = list.getClass().getSimpleName();
        System.out.print(" <---> " + String.join("", prefix, "顺序遍历耗时ms:", String.valueOf(elapsed)));
    }

    private static void random(List<String> list) {
        long start = System.currentTimeMillis();
        for(Integer i : randomList) {
            list.get(i.intValue());
        }
        long elapsed = System.currentTimeMillis() - start;
        String prefix = list.getClass().getSimpleName();
        System.out.print(" <---> " + String.join("", prefix, "随机访问耗时ms:", String.valueOf(elapsed)));
    }

    private static void randomInsert(List<String> list) {
        long start = System.currentTimeMillis();
        for(Integer i : randomList) {
            list.add(i.intValue(), "aa" + i);
        }
        long elapsed = System.currentTimeMillis() - start;
        String prefix = list.getClass().getSimpleName();
        System.out.print(" <---> " + String.join("", prefix, "随机插入耗时ms:", String.valueOf(elapsed)));
    }

    private static void randomRemove(List<String> list) {
        long start = System.currentTimeMillis();
        for(Integer i : randomList) {
            list.remove(i.intValue());
        }
        long elapsed = System.currentTimeMillis() - start;
        String prefix = list.getClass().getSimpleName();
        System.out.print(" <---> " + String.join("", prefix, "随机删除耗时ms:", String.valueOf(elapsed)));
    }
}