目 录CONTENT

文章目录

java基础回顾--ArrayList和LinkedLIst异同

在水一方
2022-02-12 / 0 评论 / 0 点赞 / 414 阅读 / 1,956 字 / 正在检测是否收录...

在实际项目中集合的使用非常广泛,作为List接口下最常用的两个集合类,ArrayList和LinkedList两者之间异同是需要熟悉掌握,本小节对此部分知识点进行回顾

public class ArrayList<E> extends AbstractList<E>
        implements List<E>, RandomAccess, Cloneable, java.io.Serializable
{




public class LinkedList<E>
    extends AbstractSequentialList<E>
    implements List<E>, Deque<E>, Cloneable, java.io.Serializable
{

说明: Deque是队列的接口,RandomAccess接口是快速访问接口

相同点
ArrayList和LinkedLIst的方法都是不同步的,也就是两者都是线程不安全的

不同点:
1 **数据结构:**ArrayList底层采用的数组,LinkedList底层采用双向列表,

2 插入和删除是否受元素位置的影响: ① ArrayList 采用数组存储,所以插入和删除元素的时间复杂度受元素位置的影响。 比如:执行 add(E e) 方法的时候, ArrayList 会默认在将指定的元素追加到此列表的末尾,这种情况时间复杂度就是O(1)。但是如果要在指定位置 i 插入和删除元素的话( add(int index, E element) )时间复杂度就为 O(n-i)。因为在进行上述操作的时候集合中第 i 和第 i 个元素之后的(n-i)个元素都要执行向后位/向前移一位的操作。 ② LinkedList 采用链表存储,所以插入,删除元素时间复杂度不受元素位置的影响,都是近似 O(1)而数组为近似 O(n)

3 是否支持快速随机访问,ArrayList实现了RandomAccess接口,它支持快速随机访问,快速随机访问就是通过元素的序号快速获取元素对象(对应于 get(int index) 方法)。LinkedList有get(int index)方法,但是不支持高效的快速随机访问,LinkedList没有索引,因为它本质上是链表,只能从头依次开始查找,只能顺序访问

4 内存空间占用: ArrayList的空 间浪费主要体现在在list列表的结尾会预留一定的容量空间,而LinkedList的空间花费则体现在它的每一个元素都需要消耗比ArrayList更多的空间(因为要存放直接后继和直接前驱以及数
据)。

5 ArrayList的默认容量为10(private static final int DEFAULT_CAPACITY = 10;)
LinkedList:基于双向链表实现的,不需要指定初始容量

image.png

如何选择

如果涉及到"栈"、"队列"、"链表"等操作,应该考虑用List,具体的选择哪个List,根据下面的标准来取舍。
(01) 对于需要快速插入,删除元素,应该使用LinkedList。
(02) 对于需要快速随机访问元素,应该使用ArrayList

验证

新增元素的比较

@Test
    public void testTime(){
        LinkedList linkedList =new LinkedList<>();
        long time1 = System.currentTimeMillis();
        for(int i =0;i<100000;i++){
            linkedList.add(0,i);
        }
        long time2 = System.currentTimeMillis();
        long interval = time2 - time1;
        System.out.println("linkedList新增的时间差是:"+interval);

        ArrayList list =new ArrayList<>();
        long starttime = System.currentTimeMillis();
        for(int j =0;j<100000;j++){
            list.add(0, j);
        }
        long endTime = System.currentTimeMillis();
        long time = endTime - starttime;
        System.out.println("ArrayList新增元素中间的时间差为:"+time);
    }

打印结果:
linkedList新增的时间差是:12
ArrayList新增元素中间的时间差为:1538

扩展

List的框架图
List

可参考博客:
https://www.cnblogs.com/skywang12345/p/3308900.html

0

评论区