[数据结构与算法]ArrayList和LinkedList

ArrayList和LinkedList

•  List ：有序可重复
  

•  存入顺序和去除顺序是一致
  

• ArrayList：底层是数组，查询和更改效率极高，添加和删除效率较低
  

•  LinkedList：底层是双向链表，查询效率较低，添加删除效率较高
  

public static void main(String[] args) {
        //底层是Object[]数组，也就意味着只能保存引用类型
        //但是由于基本类型会自动装箱为包装类类型，所以导致Object[] 数组什么都能放
        List list = new ArrayList();
        //add(E e):将元素添加到泪飙的尾部
        list.add(11);
        //add(int index,E e):将元素添加到列表的指定位置
        list.add(0, 22);
        //ArrayList覆写了toString方法，所以打印结果不是内存地址 二十里面的数据[22,11]
        System.out.println(list);
        // set(int index, E element):替换指定位置上的元素
        list.set(1, 33);
        System.out.println(list);
        //get(int index):根据索引获取对应的元素
        System.out.println(list.get(1));
        //remove(int index)：根据索引删除元素
        list.remove(1);
        //remove(Object obj):根据指定元素
        //应该手动吧22封装到Integer类型中
        list.remove(new Integer(22));
        System.out.println(list);

        list.add(1);
        list.add(2);
        list.add(3);
        list.add(4);
        //迭代器
        Iterator it = list.iterator();
        while (it.hasNext()) {
            System.out.println(it.next());
        }

        //forEach
        for (Object object : list) {
            System.out.println(object);
        }

        //for
        for (int i = 0; i < list.size(); i++) {
            System.out.println(list.get(i));
        }
    }

•  LinkedList：底层是双向链表
  

•  链表的节点 有三个部分构成：1添加的元素，2下一个节点的引用了，3上一个节点的引用
  

•  链表数据结构，在内存中储存也不是连续的，所以没有固定的下标，因此查询效率低
  

•  因为内存空间不是连续的，只是能找到下一个节点，因此添加和删除就变得容易
  

public static void main(String[] args) {
        LinkedList linkedList = new LinkedList();
        //尾部添加 成功返回true
        linkedList.add(1);
        //头部添加
        linkedList.push(2);
        //尾部
        linkedList.addLast(3);
        //首部 成功返回true
        linkedList.addFirst(4);
        //首部
        linkedList.offerFirst(5);
        //尾部
        linkedList.offerLast(6);
        System.out.println(linkedList);
        //本质调用 都是linkLast 和linkFirst，所以他们没有区别，主要解决命名习惯问题
        System.out.println(linkedList.getLast());
        System.out.println(linkedList.getFirst());
        //根据下标获取,只不过这个下标决定的是虚幻的次数，模拟出来下标获取数据而已
        //和数组的下标是两回事，因为链表是没有下标的
        System.out.println(linkedList.get(3));
        //改，设置对应下标的数据
        linkedList.set(1, 2);
        //根据索引删除
        linkedList.remove(1);
        //根据对象删除
        linkedList.remove(new Integer(2));
        //获取首元素，并把它删除
        linkedList.poll();
        //获取最后一个并删除
        linkedList.pop();
    }

• 使用ArrayList和LinkedList分别初始化1000w条数据 并 随机查询 测试性能数据
  ArrayList初始化完成100000条数据耗时5
  LinkedList初始化完成100000条数据耗时6
  ArrayList查询 27601 对应的值为27601
  ArrayList查询完成：27601 条数数据耗时0
  LinkedList查询 27601 对应的值为27601
  LinkedList查询完成：27601 条数数据耗时1
  ArrayList删除完成: 100000 条数据耗时 228
  LinkedList删除完成：100000 条数据耗时1755

• 数据分析：查询一定是数组快，但是结果有时候显示添加和删除也是数组快
  

•  因为数组的自动扩容机制，1.5倍增长，导致添加好多数据，才需要创建一个数组对象进行扩容
  

•  ，而删除元素后，容量并没有更改变小
  

•  而链表 每次添加都需要创建新的节点对象，而删除也是需要重新指向节点引用
  

• 总结：

•  插入位置的选取对LinkedList影响很大，一直向后面添加，ArrayList会比LinkedList快，因为ArrayList有自动扩容
  

•  所以对于LinkedList是添加，但是对于ArrayList来说，只是向已有空间中赋值，也就等于是更改操作，而数组查询和更改效率是比较高的
  

•  都说数组比链表添加删除慢，是因为链表进行添加删除的时候，只需要引用指向即可，而数组需要数据移动位置
  

•  所以如果想前边添加数据，则链表快很多
  

private static ArrayList arrayList;
    private static LinkedList linkedList;
    private static int size = 100000;

    public static void main(String[] args) {
        initArrayList();
        initLinkedList();

        Random random = new Random();
        int index = random.nextInt(size);
        getArrayList(index);
        getLinkedList(index);

        removeArrayList();
        removeLinkedList();
    }

    //初始化
    public static void initArrayList() {
        long startTime = System.currentTimeMillis();
        arrayList = new ArrayList();
        for (int i = 0; i < size; i++) {
            arrayList.add(i);
        }
        long endTime = System.currentTimeMillis();
        System.out.println("ArrayList初始化完成" + size + "条数据耗时" + (endTime - startTime));
    }

    public static void initLinkedList() {
        long startTime = System.currentTimeMillis();
        linkedList = new LinkedList();
        for (int i = 0; i < size; i++) {
            linkedList.add(i);
        }
        long endTime = System.currentTimeMillis();
        System.out.println("LinkedList初始化完成" + size + "条数据耗时" + (endTime - startTime));
    }

    //随机查询
    public static void getArrayList(int index) {
        long startTime = System.currentTimeMillis();
        System.out.println("ArrayList查询 " + index + " 对应的值为" + arrayList.get(index));
        long endTime = System.currentTimeMillis();
        System.out.println("ArrayList查询完成：" + index + " 条数数据耗时" + (endTime - startTime));
    }

    public static void getLinkedList(int index) {
        long startTime = System.currentTimeMillis();
        System.out.println("LinkedList查询 " + index + " 对应的值为" + linkedList.get(index));
        long endTime = System.currentTimeMillis();
        System.out.println("LinkedList查询完成：" + index + " 条数数据耗时" + (endTime - startTime));
    }

    public static void removeArrayList() {
        long startTime = System.currentTimeMillis();
        for (int i = 0; i < arrayList.size(); i++) {
            arrayList.remove(i);
        }
        long endTime = System.currentTimeMillis();
        System.out.println("ArrayList删除完成: " + size + " 条数据耗时 " + (endTime - startTime));
    }

    public static void removeLinkedList() {
        long startTime = System.currentTimeMillis();
        for (int i = 0; i < linkedList.size(); i++) {
            linkedList.remove(i);
        }
        long endTime = System.currentTimeMillis();
        System.out.println("LinkedList删除完成：" + size + " 条数据耗时" + (endTime - startTime));
    }