arraylist和linklist区别分别有哪些?

TheDisguiser 2020-05-24 20:15:23 java常见问答 7652

在java有着ArrayListLinkedList两个集合,相信小伙伴们经常会用到,但它们其实区别蛮大的,你知道它们有哪些区别吗?快跟小编来了解了解吧。

一、ArrayList是数组实现的集合操作,而LinkedList是链表实现的集合操作

二、只是用List集合中的get()方法根据索引取数据的时候,ArrayList的时间复杂度为“O(1)”,而LinkedList的时间复杂度为“O(n)”(n为集合的长度)

三、ArrayList在使用的时候默认的初始化数组的长度为10,如果空间不足则会采用2倍的形式进行容量的扩充,如果保存大数据的时候有可能造成垃圾的产生以及性能的下降,这个时候就可以用LinkedList子类保存.

ArrayList优点:查找数组元素效率高。

ArrayList因为底层是数组,根据下标或者遍历查找元素的速度很快。而数据的增删其实是新建了一个数组,所以增删效率低。

LinkList优点:数据增删效率高。

LinkList底层是是链表,每个链子里包含last(上一个链子的地址),value(存放的值),和next(下一个链子的地址)。想要查找一个元素,需要从头开始遍历,所以查找效率低。而增删只要动上一个链子的next和下一个链子的last地址就能实现,所以增删效率高。

时间复杂度区别

假设我们有两个很大的列表,它们里面的元素已经排好序了,这两个列表分别是ArrayList类型和LinkedList类型的,现在我们对这两个列表来进行二分查找(binary search),比较它们的查找速度。

例:

运行结果:

package com.demo;
import java.util.ArrayList;
import java.util.Collections;
import java.util.LinkedList;
import java.util.List;
public class Demo1
{
    static List < Integer > array = new ArrayList < Integer > ();
    static List < Integer > linked = new LinkedList < Integer > ();
    public static void main(String[] args)
    {
        for (int i = 0; i < 10000; i++)
        {
            array.add(i);
            linked.add(i);
        }
        System.out.println("ArrayList访问消耗的时间:" + getTime(array));
        System.out.println("LinkedList访问消耗的时间:" + getTime(linked));
    }
    public static long getTime(List list)
    {
        long time = System.currentTimeMillis();
        for (int i = 0; i < 10000; i++)
        {
            int index = Collections.binarySearch(list, list.get(i));
            if (index != i)
            {
                System.out.println("ERROR!");
            }
        }
        return System.currentTimeMillis() - time;
    }
}

ArrayList访问消耗的时间:10

LinkedList访问消耗的时间:383

可以看到,对于随机访问,ArrayList的访问速度更快。

ArrayList和LinkedList的插入数据耗时:

package com.demo;
import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;
public class Demo2
{
    static List < Integer > array = new ArrayList < Integer > ();
    static List < Integer > linked = new LinkedList < Integer > ();
    public static void main(String[] args)
    {
        for (int i = 0; i < 10000; i++)
        {
            array.add(i);
            linked.add(i);
        }
        System.out.println("ArrayList插入消耗的时间:" + insertTime(array));
        System.out.println("LinkedList插入消耗的时间:" + insertTime(linked));
    }
    public static long insertTime(List list)
    {
        long time = System.currentTimeMillis();
        for (int i = 100; i < 10000; i++)
        {
            list.add(10, i); // 在索引为10的位置插入i
        }
        return System.currentTimeMillis() - time;
    }
}

运行结果:

ArrayList插入消耗的时间:31

LinkedList插入消耗的时间:4

可以看到,对于插入操作而言,LinkedList的速度更快。

以上就是本文的全部内容,想要了解更多相关java入门知识,就请一直关注本站吧。

推荐阅读:

arraylist和vector的区别是什么?主要区别有哪些?java

为什么要复制ArrayList扩容?有何作用?

java数组转list该怎么转型?java数组是什么?