前言—-list

         在集合框架中,List是一个接口,继承自Collection。Collection也是一个接口,该接口规范后序容器中常用的一些方法,具体如下所示:

                

        Iterable也是一个接口,表示实现接口的类是可以逐个元素进行遍历的,具体如下: 

             

        从数据结构的角度来看,List就是一个线性,即n个具有相同类型元素有限序列,在该序列可以执行增删 改查以及变量操作。 

        要知道List是个接口,并不能直接用来实例化。 如果要使用,必须去实例化List的实现类。在集合框架中,ArrayList和LinkedList都实现了List接口,具体使用参考下文。

1.线性

        线性表(linear list)是n个具有相同特性数据元素有限序列

        线性表是一种在实际中广泛使用数据结构,常见的线性表:顺序表、链表、栈、队列线性表在逻辑上是线性结构,也就说是连续的一条直线。但是在物理结构上并不一定是连续的,线性表在物理上存储时,通常以数组和链式结构的形式存储

2.顺序表

        顺序表是用一段物理地址连续存储单元依次存储数据元素线性结构,一般情况下采用数组存储。在数组上完成数据的增删查改。

3. ArrayList简介

        在集合框架中, ArrayList 是一个普通的类,实现了 List 接口,具体框架图如下:

                       

【说明】

        1. ArrayList是以泛型方式实现的,使用时必须要先实例

        2. ArrayList实现了RandomAccess接口,表明ArrayList支持随机访问 

        3. ArrayList 实现了 Cloneable 接口,表明 ArrayList 是可以 clone
        4. ArrayList 实现了 Serializable 接口,表明 ArrayList 是支持序列化
        5. 和 Vector 不同, ArrayList 不是线程安全的,在单线程下可以使用,在多线程中可以选择 Vector 或者 CopyOnWriteArrayList
        6. ArrayList 底层是一段连续的空间,并且可以动态扩容,是一个动态类型的顺序表(物理地址连续存储单元依次存储数据元素线性结构

3.1 ArrayList的构造

        1ArrayList()—>空参构造

 public static void main(String[] args) {
       ArrayList<Integer&gt; arrayList = new ArrayList<&gt;();
       arrayList.add(2023);
       arrayList.add(11);
       arrayList.add(28);
    }

        底层代码逻辑

 

        2.2ArrayList(Collection<? extends E&gt; c)——–>利用其他 Collection 构建 ArrayList

        <? extends E>——————————>
        该语句规定了ArrayList类的类型上界,即被用来存储arraylist类中数组空间elementdata里的元素的类型上限是E,后面定义要被装载的元素类型必须是E本身或者E的子类。 

public static void main(String[] args) {
       ArrayList<Integer> list = new ArrayList<>();
       list.add(-1);
       list.add(100);
       list.add(200);
       ArrayList<Number> list12 = new ArrayList<>(list);
       list12.add(-100);
       System.out.println(list12);
    }

        代码执行结果如下图所示: 

 

        我们构造的list(1、实现了 collection接口,能够支持一些规范容器操作;2、是支持小于等于interger类数据的存储),可以传递到list12里(1、list12实现了collection接口,2、它支持的数据类型<=number,已知interger< number)

        2.3ArrayList(int initialCapacity)—–>指定顺序表初始容量

 public static void main(String[] args) {
        ArrayList<Integer> arrayList = new ArrayList<>(2);
        arrayList.add(100);
        arrayList.add(200);
    }

源码分析: 

           

 all in all:

3.2 ArrayList常见操作

        一般来说常见的方法如下图所示:

        下面来对一些较为重要的方法通过源代码来进行分析

        1.boolean add(E e) ——>尾插 e

       

        首先arraylist底层设置,默认容量为10;

        当我们执行完成以上代码的第一句时,虽然我们有默认为10的存储空间,但是当前却没有给顺序表list分配;当执行完第二句(即第一句add语句)时,我们才会分配一个容量为10的空间给list;

        当我们一直执行add操作,为了确保一直有存储空间来存储数据,在每一次add语句执行添加元素之前,语句会提前检查剩余的容量是否足够,当容量不足以存储数据时,会提前对空间容量进行扩容,且扩容是在前一个容量的数量上乘以1.5(即1.5倍扩容)

        具体如下图展示

        小结:
        1. 检测是否真正需要扩容之后,最后是通过调用 grow 进行扩容
        2. 预估需要库容的大小 初步预估按照1.5 倍大小扩容
(1、初步预估按照1.5倍大小扩容 ;2、如果用户所需大小超过预估1.5倍大小,则按照用户所需大小扩容;3、 真正扩容之前检测是否能扩容成功,防止太大导致扩容失败)
        3. 也可以使调用copyOf 方法进行扩容

        2. void add(int index, E element)

        在 list 的 index 位置插入指定元素, index 及后续的元素统一往后移动一个位置,下图为底层原码:

         3.List<E> subList(int fromIndex, int toIndex) —->

        理解:使用list中[0, 4)之间的元素构成一个新的SubList返回,但是和ArrayList共用一个elementData数组;Sub:截取产生的list,不是新产生的,而是直接将原来list相对应位置地址传递到新的list当中。

 public static void main(String[] args) {
        ArrayList<Integer> arraylist = new ArrayList<>();
        arraylist.add(2023);
        arraylist.add(11);
        arraylist.add(28);
        List<Integer> sub = arraylist.subList(1, 3);
        System.out.println(sub);
        sub.set(0,100000);
        System.out.println(sub);
        System.out.println(arraylist);
    }

        运行结果展示: 

 

        该操作构成一个新的list返回,但是和arrayList共用一个数组,不会产生一个新的对象,所以在新list上进行修改数值时,由于指向的部分引用相同,会导致就list的数值也会发生变化。 如下下图分析所示:

 

3.3 ArrayList的遍历

        ArrayList 可以使用三方方式遍历for循环foreach使用迭代 

public static void main(String[] args) {
List<Integer> list = new ArrayList<>();
list.add(1);
list.add(2);
list.add(3);
list.add(4);
list.add(5);
// 使用下标+for遍历
for (int i = 0; i < list.size(); i++) {
System.out.print(list.get(i) + " ");
}
System.out.println();
// 借助foreach遍历
for (Integer integer : list) {
System.out.print(integer + " ");
}
System.out.println();
Iterator<Integer> it = list.listIterator();
while(it.hasNext()){
System.out.print(it.next() + " ");
}
System.out.println();
}

        关于迭代器:

4. ArrayList的优缺点

        由于其底层是一段连续空间,当在ArrayList任意位置插入或者删除元素时,就需要后序元素整体往前或者往后搬移,时间复杂度为O(n),效率比较低,因此ArrayList不适合做任意位置插入删除比较多的场景,下面是详细的总结

缺点:

  1. 插入数据必须移动其他数据,最坏情况下,就是插入到0位置,时间复杂度O(N);
  2. 删除数据必须移动其他数据,最坏情况下,就是删除0位置,时间复杂度O(N)
  3. 扩容之后有可能浪费空间(扩容之后结果我们只使用一两个空间)。

优点:

  1. 给定下标情况下进行查找的时候,时间复杂度O(1);

        注意:顺序表适合给定下标查找的情况。

ps:本次内容就到这里了,如果对你有帮助的话,还请一键三连哦!!!

原文地址:https://blog.csdn.net/2202_76101487/article/details/134664709

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。

如若转载,请注明出处:http://www.7code.cn/show_5491.html

如若内容造成侵权/违法违规/事实不符,请联系代码007邮箱:suwngjj01@126.com进行投诉反馈,一经查实,立即删除

发表回复

您的邮箱地址不会被公开。 必填项已用 * 标注