当前位置: 首页 > article >正文

【八股文】ArrayList和LinkedList的区别

先讲讲两者是如何实现的

ArrayList

public class ArrayList<E> extends AbstractList<E>
        implements List<E>, RandomAccess, Cloneable, java.io.Serializable
{
    
    transient Object[] elementData; 

    private int size;
}

 通过源码可以看出,ArrayList实现是基于数组实现的

LinkedList

public class LinkedList<E>
    extends AbstractSequentialList<E>
    implements List<E>, Deque<E>, Cloneable, java.io.Serializable
{
    transient int size = 0;

    /**
     * Pointer to first node.
     */
    transient Node<E> first;

    /**
     * Pointer to last node.
     */
    transient Node<E> last;
}

private static class Node<E> {
        E item;
        Node<E> next;
        Node<E> prev;
}

 通过源码可以看出,LinkedList实现是基于双向链表的数据结构。

使用双向链表而不使用单链表是为了能支持反向遍历,快速删除尾部元素

接下来,我们分析下不同操作的情况下,它两的差异

列表头部插入

ArrayList每次头插都需要移动所有元素, 时间复杂度O(n^2)

LinkedList只需要修改指针,时间复杂度O(n)

随机访问

ArrayList直接通过索引计算内存地址,时间复杂度O(1)

LinkedList需要从头节点开始遍历,时间复杂度O(n)

空间复杂度对比

LinkedList比ArrayList多占用数倍的空间,因为LinkedList要多存前后指针等信息

总结

 最后留两个问题给大家思考下

//list是linkedlist
for(int i=0; i<list.size(); i++){
    System.out.println(list.get(i));
}
for(String s : list){
    if(s.equals("bug")){
        list.remove(s);
    }
}

上述代码有啥问题?


http://www.kler.cn/a/586942.html

相关文章:

  • 【Python 语法】排序算法
  • 个人博客系统测试报告
  • C++程序设计语言笔记——抽象机制:模板
  • eclipse-mosquitt之docker部署安装与使用
  • 现在有分段、句子数量可能不一致的中英文文本,如何用python实现中英文对照翻译(即每行英文对应相应的中文)
  • MySQL事务及索引复习笔记
  • Qt从入门到入土(十) -数据库操作--SQLITE
  • JAVA EE(10)——线程安全——synchronized JUC(java.util.concurrent) 的常见类 线程安全的集合类
  • 机器学习编译器(二)
  • Java中的访问修饰符有哪些
  • Swagger 从 .NET 9 中删除:有哪些替代方案
  • 洛谷 P4933 大师
  • LRU(最近最少使用)算法实现
  • 探索Maas平台与阿里 QWQ 技术:AI调参的魔法世界
  • 车载软件刷写工具vFlash --- 自动化接口(Automation API)应用简介
  • 德语A1学习
  • 批量ip反查域名工具
  • 删除有序数组中的重复项(26)
  • [网络] 网络基础概念--socket编程预备
  • Ubuntu 24 常用命令方法