容器——2.Collection 子接口之 List

这篇具有很好参考价值的文章主要介绍了容器——2.Collection 子接口之 List。希望对大家有所帮助。如果存在错误或未考虑完全的地方,请大家不吝赐教,您也可以点击"举报违法"按钮提交疑问。

2.1. Arraylist 和 Vector 的区别?

  • ArrayListList 的主要实现类,底层使用 Object[ ]存储,适用于频繁的查找工作,线程不安全 ;
  • VectorList 的古老实现类,底层使用 Object[ ] 存储,线程安全的。

2.2. Arraylist 与 LinkedList 区别?

  1. 是否保证线程安全: ArrayListLinkedList 都是不同步的,也就是不保证线程安全;
  2. 底层数据结构: Arraylist 底层使用的是 Object 数组LinkedList 底层使用的是 双向链表 数据结构(JDK1.6 之前为循环链表,JDK1.7 取消了循环。注意双向链表和双向循环链表的区别,下面有介绍到!)
  3. 插入和删除是否受元素位置的影响:ArrayList 采用数组存储,所以插入和删除元素的时间复杂度受元素位置的影响。 比如:执行add(E e)方法的时候, ArrayList 会默认在将指定的元素追加到此列表的末尾,这种情况时间复杂度就是 O(1)。但是如果要在指定位置 i 插入和删除元素的话(add(int index, E element))时间复杂度就为 O(n-i)。因为在进行上述操作的时候集合中第 i 和第 i 个元素之后的(n-i)个元素都要执行向后位/向前移一位的操作。 ② LinkedList 采用链表存储,所以对于add(E e)方法的插入,删除元素时间复杂度不受元素位置的影响,近似 O(1),如果是要在指定位置i插入和删除元素的话((add(int index, E element)) 时间复杂度近似为o(n))因为需要先移动到指定位置再插入。
  4. 是否支持快速随机访问: LinkedList 不支持高效的随机元素访问,而 ArrayList 支持。快速随机访问就是通过元素的序号快速获取元素对象(对应于get(int index)方法)。
  5. 内存空间占用: ArrayList 的空 间浪费主要体现在在 list 列表的结尾会预留一定的容量空间,而 LinkedList 的空间花费则体现在它的每一个元素都需要消耗比 ArrayList 更多的空间(因为要存放直接后继和直接前驱以及数据)。

2.2.1. 补充内容:双向链表和双向循环链表

双向链表: 包含两个指针,一个 prev 指向前一个节点,一个 next 指向后一个节点。

另外推荐一篇把双向链表讲清楚的文章:https://juejin.im/post/5b5d1a9af265da0f47352f14

容器——2.Collection 子接口之 List,java笔记整理,list,数据结构
双向循环链表: 最后一个节点的 next 指向 head,而 head 的 prev 指向最后一个节点,构成一个环。

容器——2.Collection 子接口之 List,java笔记整理,list,数据结构

2.2.2. 补充内容:RandomAccess 接口

public interface RandomAccess {
}

查看源码我们发现实际上 RandomAccess 接口中什么都没有定义。所以,在我看来 RandomAccess 接口不过是一个标识罢了。标识什么? 标识实现这个接口的类具有随机访问功能。

binarySearch() 方法中,它要判断传入的 list 是否 RamdomAccess 的实例,如果是,调用indexedBinarySearch()方法,如果不是,那么调用iteratorBinarySearch()方法

public static <T>
    int binarySearch(List<? extends Comparable<? super T>> list, T key) {
        if (list instanceof RandomAccess || list.size()<BINARYSEARCH_THRESHOLD)
            return Collections.indexedBinarySearch(list, key);
        else
            return Collections.iteratorBinarySearch(list, key);
    }

ArrayList 实现了 RandomAccess 接口, 而 LinkedList 没有实现。为什么呢?我觉得还是和底层数据结构有关!ArrayList 底层是数组,而 LinkedList 底层是链表。数组天然支持随机访问,时间复杂度为 O(1),所以称为快速随机访问。链表需要遍历到特定位置才能访问特定位置的元素,时间复杂度为 O(n),所以不支持快速随机访问。,ArrayList 实现了 RandomAccess 接口,就表明了他具有快速随机访问功能。 RandomAccess 接口只是标识,并不是说 ArrayList 实现 RandomAccess 接口才具有快速随机访问功能的!

2.3 ArrayList 的扩容机制

ArrayList 是基于数组实现的动态数组,它提供了一种可以动态增长和缩减的数组结构。在 ArrayList 中,当数组存储的元素个数达到上限时,会触发扩容操作,以保证其容量能够存储更多的元素。

ArrayList 扩容机制的主要过程:

  1. 在添加元素时,首先会判断数组是否已满。如果已满,则需要进行扩容操作;
  2. 扩容操作会创建一个新的大数组,并将原数组中的元素全部复制到新数组中;
  3. 新数组的长度通常是原数组长度的 1.5 倍(可以通过源码中的 DEFAULT_CAPACITY_INCREMENT = 12 和 DEFAULT_CAPACITY = 10 来了解扩容因子)。如果指定了初始化容量,那么新数组的长度就是指定的容量大小;
  4. 复制完元素后,会将指向原数组的引用更新为指向新数组的引用。

源码分析

private void grow(int minCapacity) {
    // 获取当前数组容量
    int oldCapacity = elementData.length;
    // 扩容因子,以 1.5 倍方式进行扩容
    int newCapacity = oldCapacity + (oldCapacity >> 1);
    // 如果新容量小于 minCapacity,则使用 minCapacity 作为新容量
    if (newCapacity - minCapacity < 0)
        newCapacity = minCapacity;
    // 如果新容量超出了最大容量,则抛出 OutOfMemoryError 异常
    if (newCapacity - MAX_ARRAY_SIZE > 0)
        newCapacity = hugeCapacity(minCapacity);
    // 复制旧数组中的元素到新数组中
    elementData = Arrays.copyOf(elementData, newCapacity);
}

由于每次扩容都需要重新进行数据复制,所以过于频繁的扩容操作会导致性能损失。为避免频繁的扩容操作,初始化 ArrayList 对象时可以指定其容量大小,或者使用 ensureCapacity(int minCapacity) 方法预先设置其容量大小,以提高效率。同时,在添加大量元素时,也可以使用 addAll(Collection<? extends E> c)addAll(int index, Collection<? extends E> c) 方法,一次性添加多个元素,以减少扩容操作的次数。文章来源地址https://www.toymoban.com/news/detail-633668.html

到了这里,关于容器——2.Collection 子接口之 List的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处: 如若内容造成侵权/违法违规/事实不符,请点击违法举报进行投诉反馈,一经查实,立即删除!

领支付宝红包 赞助服务器费用

相关文章

  • 【Java基础教程】(四十八)集合体系篇 · 上:全面解析 Collection、List、Set常用子接口及集合元素迭代遍历方式~【文末送书】

    掌握 Java 设置类集的主要目的以及核心接口的使用; 掌握 Collection 接口的作用及主要操作方法; 掌握 Collection 子接口 List、Set 的区别及常用子类的使用; 掌握 Map 接口的定义及使用; 掌握集合的4种输出操作语法结构; 掌握 Properties类的使用 ; 了解类集工具类 Collections 的作

    2024年02月15日
    浏览(54)
  • java -- 简单的数据结构、List接口和Collections类

    数据结构 : 数据用什么样的方式组合在一起。 数据存储的常用结构有:栈、队列、数组、链表 栈: stack ,又称堆栈,它是运算受限的线性表,其限制是仅允许在标的一端进行插入和删除操作,不允许在其他任何位置进行添加、查找、删除等操作。 采用该结构的集合,对元素

    2023年04月10日
    浏览(48)
  • 第12章_集合框架(Collection接口,Iterator接口,List,Set,Map,Collections工具类)

    1.1 生活中的容器 1.2 数组的特点与弊端 一方面,面向对象语言对事物的体现都是以对象的形式,为了方便对多个对象的操作,就要对对象进行存储。 另一方面,使用数组存储对象方面具有 一些弊端 ,而Java 集合就像一种容器,可以 动态地 把多个对象的引用放入容器中。 数

    2024年01月25日
    浏览(43)
  • Java基础六 - Collection集合List、Set、Queue,Map

    1. List - ArrayList、LinkedList、Vector ArrayList         2. LinkedList         3. Vector         4. 常见使用方法 2. Set - HashSet、LinkedHashSet、TreeSet 1. HashSet 2. LinkedHashSet 3. TreeSet 4. 常用方法 3. Map - HashMap、TreeMap、LinkedHashMap、Hashtable 1. HashMap 2. LinkedHashMap 3. TreeMap 4. Hashtable 5.

    2024年02月14日
    浏览(47)
  • 从零开始学习 Java:简单易懂的入门指南之Collection集合及list集合(二十一)

    1.1数组和集合的区别 相同点 都是容器,可以存储多个数据 不同点 数组的长度是不可变的,集合的长度是可变的 数组可以存基本数据类型和引用数据类型 集合只能存引用数据类型,如果要存基本数据类型,需要存对应的包装类 1.2集合类体系结构 1.3Collection 集合概述和使用 Collec

    2024年02月10日
    浏览(39)
  • 【c++】 list容器的基本操作与接口

    List容器是一个双向链表。 采用动态存储分配,不会造成内存浪费和溢出 链表执行插入和删除操作十分方便,修改指针即可,不需要移动大量元素 链表灵活,但是空间和时间额外耗费较大 list构造函数 list数据元素插入和删除操作 list大小操作 list赋值操作 l ist数据的存取 li

    2024年02月17日
    浏览(48)
  • <C++> list容器本质|常用接口|自定义排序规则

    ✅作者简介:热爱后端语言的大学生,CSDN内容合伙人 ✨精品专栏:C++面向对象 🔥系列专栏:C++泛型编程 🔥前言 今天把 list 容器的基本操作、常用接口做一个系统的整理,结合具体案例熟悉自定义内部排序方法的使用。 list 与 vector 是STL中最常用的两个容器,如果对vector

    2024年02月01日
    浏览(45)
  • 【数据结构】 List与顺序表及接口的实现

    在集合框架中, List是一个接口,继承自Collection。 Collection也是一个接口,该接口中规范了后序容器中常用的一些方法,具体如下所示: Iterable也是一个接口,表示实现该接口的类是可以逐个元素进行遍历的,具体如下: List 的官方文档 站在数据结构的角度来看, List就是一

    2024年02月12日
    浏览(38)
  • 【数据结构】_4.List接口实现类LinkedList与链表

    目录 1.链表的结构与特点 1.1 链表的结构: 1.2 链表的特点: 2. 不带头单链表的模拟实现 3. 单链表OJ 3.1 题目1:移除链表元素:  3.2 题目2:反转一个单链表 3.3 题目3:返回链表的中间结点 3.4 题目4:链表的倒数第k个结点 3.5 题目5:合并两个有序链表 3.6 题目6:链表的回文结构

    2024年02月15日
    浏览(44)
  • Java 集合 - List 接口

    在 Java 中, java.util.List 接口是 Java 集合框架中的一个接口,它继承自 Collection 接口,是单列集合的一个重要分支。List 接口的常见实现类包括 ArrayList 、 LinkedList 和 Vector 。 List 接口特点如下: 有序性 : List 中的元素是按照插入顺序排序的,因此可以很容易地遍历 List 中的元

    2024年02月07日
    浏览(60)

觉得文章有用就打赏一下文章作者

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

请作者喝杯咖啡吧~博客赞助

支付宝扫一扫领取红包,优惠每天领

二维码1

领取红包

二维码2

领红包