JoJo的个人博客

记录精彩的程序人生

目录
LinkedList和ArrayList
/  

LinkedList和ArrayList

ArrayList

ArrayList是集合的一种实现,实现了接口ListList接口继承了Collection接口。Collection是所有集合类的父类

扩容机制

  • 把原来的数组复制到另一个内存空间更大的数组中,容量为原来的1.5

  • 把新元素添加到扩容以后的数组中

添加元素

  • 判断有没有越界

  • 判断需不需要扩容

  • 使用System.arraycopyindex位置及后面的元素都后移一位

  • 将添加的元素放在index位置,size++

删除元素

  • 记录删除位置元素,最后返回
  • 待删除位置后面的元素都前移一位
  • 数组最后一位元素置nullsize++

LinkedList

双向链表,有头尾指针,实现了ListDeque接口,可以作为栈和队列使用

添加、删除和查询元素

通过index找到待插入结点的前一个结点,如果index小于size的一半就从首节点开始遍历,如果index大于或等于size的一半,就从尾节点开始遍历

如果是首尾结点会很高效

ArrayList 和 LinkedList 区别

  • ArrayList查询速度快

  • LinkedList用于实现栈,队列,双端队列的数据结构,效率更加

  • 增删操作时,谁效率高有争议,LinkedList需要遍历需要索引位置,而ArrayList需要移动操作元素后面所有元素的位置

  • 空间开销,ArrayList是动态数据,扩容时按照1.5倍容量扩容,会预留一些空间,LinkList需要存储结点和前后结点的指针

  • 时间复杂度

    • ArrayList 是线性表(数组)

      • get() 直接读取第几个下标,复杂度 O(1)
      • add(E) 添加元素,直接在后面添加,复杂度O(1)
      • add(index, E)添加元素,在第几个元素后面插入,后面的元素需要向后移动,复杂度O(n)
      • remove()删除元素,后面的元素需要逐个移动,复杂度O(n)
    • LinkedList是链表的操作

      • get()获取第几个元素,依次遍历,复杂度O(n)
      • add(E), addFirst(E) 添加到首尾,复杂度O(1)
      • add(index, E) 添加第几个元素后,需要先查找到第几个元素,直接指针指向操作,复杂度O(n)
      • removeadd一样


标题:LinkedList和ArrayList
作者:SunnySky
地址:https://www.tianyang.pub/articles/2020/06/03/1591162336464.html

评论