【数据结构】初识集合&深入剖析顺序表(Arraylist)

简介: Java集合框架主要由接口、实现类及迭代器组成,包括Collection和Map两大类。Collection涵盖List(有序、可重复)、Set(无序、不可重复),Map则由键值对构成。集合通过接口定义基本操作,具体实现由各类如ArrayList、HashSet等提供。迭代器允许遍历集合而不暴露其实现细节。List系列集合元素有序且可重复,Set系列元素无序且不可重复。集合遍历可通过迭代器、增强for循环、普通for循环及Lambda表达式实现,各有适用场景。其中ArrayList实现了动态数组功能,可根据需求自动调整大小。

集合体系结构

Java集合框架主要由以下几个部分组成:

接口:这是集合框架的基础,定义了各种集合的基本操作,如添加、删除、查找等。主要的接口有Collection、List、Set、Queue、Map等。
实现类:这些类实现了集合框架中的接口,提供了具体的集合实现。例如,ArrayList、LinkedList实现了List接口,HashSet、TreeSet实现了Set接口,HashMap、TreeMap实现了Map接口等。
迭代器:迭代器(Iterator)允许程序员遍历集合中的元素,而无需了解集合底层的实现细节

同时,集合在Java中确实分为单列集合(Collection)和双列集合(Map)两大类,单列集合就是下图中左边的部分,每次存储一个元素,双列集合是由键(key)和值(value)组成的集合,也称为键值对集合

List系列集合:添加的元素是有序的,可重复,有索引的
Set系列集合:添加的元素是无序的,不重复,无索引的
由于这个特性,在添加元素时List系列集合允许元素重复,add返回值为true,set系列集合不允许元素重复,元素重复时add返回值为false


Collection是所有单列集合的父类接口,也就是它的功能所有的单列集合都可以用

contains方法底层是依赖equals方法进行判断的,所以,如果集合中存储的类型是自定义类型,就要重写equals方法,否则会直接调用Object类的equals方法

集合的遍历

迭代器


就相当于c语言中的指针,通过迭代器就可以实现集合的遍历

public static void main(String[] args) {
        Collection<String> c = new ArrayList<>();
        c.add("hello");
        c.add("world");
        Iterator<String> it = c.iterator();
        while(it.hasNext()){
            System.out.println(it.next());
        }
    }

注意:
如果已经遍历完最后一个元素,再强行往后遍历就会报错

迭代器遍历完毕,指针不会复位,如果要再遍历一遍,就要重新创建迭代器对象
循环中只能用一次next方法
迭代器遍历时,不会能用集合中的方法进行增加或者删除

增强for遍历

增强for底层就是迭代器,是为了简化迭代器的代码而出现的,所有的单列集合和数组才能用增强for来遍历
格式:
for(元素类型 变量名 :数组或集合){
}

public static void main(String[] args) {
        Collection<String> c = new ArrayList<>();
        c.add("aa");
        c.add("bb");
        c.add("cc");
        for(String s:c){
            System.out.print(s + " ");
        }
    }

注意:修改增强for中的变量,不会修改集合中的数据

public static void main(String[] args) {
        Collection<String> c = new ArrayList<>();
        c.add("aa");
        c.add("bb");
        c.add("cc");
        for(String s:c){
            s = "dd";
        }
        System.out.println(c);
    }

运行结果依然是之前集合中的内容

lambda表达式

lambda通过调用forEach方法实现的,先用匿名内部类的形式来实现一下

c.forEach(new Consumer<String>() {
            @Override
            public void accept(String s) {
                System.out.println(s);
            }
        });

在此基础上就可以修改为lambda表达式

c.forEach((s)-> {System.out.println(s);});

此时,s的小括号和执行语句中的{}和;都可以进行省略

c.forEach(s-> System.out.println(s));

List接口中的增删查改

由于List接口继承了Collection接口,所以Collection中的方法List都可以使用,同时List还有特有的方法

public class ListDemo {
    public static void main(String[] args) {
        //通过实现类ArrayList创建List
        List<Integer> list = new ArrayList<>();
        // 添加元素
        list.add(1);
        list.add(2);
        list.add(3);
        list.add(4);
        //删除1索引元素
        list.remove(1);
        Integer i = Integer.valueOf(1);
        //删除目标元素1
        list.remove(i);
        System.out.println(list);
        //修改目标元素
        list.set(0, 10);
        //获取目标元素
        int l = list.get(1);
        System.out.println(l);
    }
}

在删除元素的时候需要注意,如果是Integer类型的元素,传参之后就会区分不清是索引还是目标元素,就需要通过创建对象的方式,传入Integer类型的对象,以此和索引进行区分

List的5种遍历

public class ListDemo {
    public static void main(String[] args) {
        //通过实现类ArrayList创建List
        List<Integer> list = new ArrayList<>();
        // 添加元素
        list.add(1);
        list.add(2);
        list.add(3);
        //迭代器
        Iterator<Integer> it = list.iterator();
        while (it.hasNext()){
            System.out.print(it.next() + " ");
        }
        //增强for
        for(Integer i1:list){
            System.out.println(i1);
        }
        //lambda表达
        list.forEach((s)-> System.out.print(s + " "));
        //普通for循环
        for (int j = 0; j < list.size(); j++) {
            System.out.println(list.get(j));
        }
        //列表迭代器
        ListIterator<Integer> it2 = list.listIterator();
        while(it2.hasNext()){
            System.out.println(it2.next());
        }
    }
}

列表迭代器ListIterator接口继承了Iterator接口,因此ListIterator拥有Iterator的所有方法,并在此基础上增加了额外的功能。

使用列表迭代器进行遍历时,如果用到了添加元素的操作,应该通过迭代器的对象去调用add方法,用List的对象去调用就会报错

ListIterator<Integer> it2 = list.listIterator();
        while (it2.hasNext()) {
            System.out.println(it2.next());
            it2.add(100);
            list.add(101);//报错
        }

适用场景:
迭代器遍历:在遍历过程中需要删除元素
列表迭代器:在遍历过程中需要添加元素
增强for,lambda表达式:只作遍历使用
普通for:遍历时需要操作索引

ArrayList详解

ArrayList是一个广泛使用的集合类,它实现了List接口,提供了动态数组的功能,与普通的数组不同,ArrayList能够自动调整其大小以容纳新的元素。

ArrayList的创建

集合和数组的对比:
集合的长度可变,数组的长度固定
数组可以存基本数据类型和引用数据类型,集合只能存储引用数据类型,如果要存基本数据类型就需要将其转换为对应的包装类
创建ArrayList的对象时,是通过泛型来规定存储的类型

ArrayList<Integer> arrayList = new ArrayList<>();

ArrayList的增删查改

ArrayList实现了List接口,所以List中的方法也可以使用

public class ArrayListExample {
    public static void main(String[] args) {
        // 创建一个ArrayList实例
        ArrayList<String> list = new ArrayList<>();
        // 添加元素
        list.add("Apple");
        list.add("Banana");
        list.add("Orange");
        // 打印ArrayList
        System.out.println("ArrayList: " + list);
        // 访问元素
        String fruit = list.get(1);
        System.out.println("访问第二个元素: " + fruit);
        // 修改元素
        list.set(1, "Mango");
        System.out.println("修改后的ArrayList: " + list);
        // 删除元素
        list.remove(2);
        System.out.println("删除元素后的ArrayList: " + list);
        // 获取大小
        int size = list.size();
        System.out.println("ArrayList的大小: " + size);
        // 遍历ArrayList
        System.out.print("遍历ArrayList: ");
        for (String item : list) {
            System.out.print(item + " ");
        }
    }
}

ArrayList的遍历

ArrayList也有非常多中遍历方式

ArrayList<Integer> arrayList = new ArrayList<>();
        arrayList.add(1);
        arrayList.add(2);
        arrayList.add(3);
        //增强for
        for (Integer integer : arrayList) {
            System.out.println(integer);
        }
        //普通for
        for(int j = 0;j < arrayList.size();j++){
            System.out.println(arrayList.get(j));
        }
        //迭代器
        Iterator<Integer> it3 = arrayList.iterator();
        while (it.hasNext()) {
            System.out.println(it3.next());
        }
        //列表迭代器
        ListIterator<Integer> it4 = arrayList.listIterator();
        while (it3.hasNext()) {
            System.out.println(it4.next());
        }
        //lambda表达式
        list.forEach(s -> System.out.print(s + " "));

ArrayList的底层原理

利用空参构造创建的集合,在底层会创建一个默认长度为0的数组
添加第一个元素时,底层会创建一个新的长度为10的数组
存满时会扩容1.5倍

如果一次添加多个元素,1.5倍还放不下,新创建的数组的长度以实际为准

相关文章
|
1月前
|
存储 编译器 C语言
数据结构-顺序表详解(看这篇就足够了,哈哈哈)
数据结构-顺序表详解(看这篇就足够了,哈哈哈)
49 2
|
14天前
|
存储 Java 索引
Java中的数据结构:ArrayList和LinkedList的比较
【10月更文挑战第28天】在Java编程世界中,数据结构是构建复杂程序的基石。本文将深入探讨两种常用的数据结构:ArrayList和LinkedList,通过直观的比喻和实例分析,揭示它们各自的优势与局限,帮助你在面对不同的编程挑战时做出明智的选择。
|
17天前
|
存储 算法 安全
2024重生之回溯数据结构与算法系列学习之顺序表【无论是王道考研人还真爱粉都能包会的;不然别给我家鸽鸽丢脸好嘛?】
顺序表的定义和基本操作之插入;删除;按值查找;按位查找等具体详解步骤以及举例说明
|
17天前
|
存储 C语言
【数据结构】顺序表(c语言实现)(附源码)
本文介绍了线性表和顺序表的基本概念及其实现。线性表是一种有限序列,常见的线性表有顺序表、链表、栈、队列等。顺序表是一种基于连续内存地址存储数据的数据结构,其底层逻辑是数组。文章详细讲解了静态顺序表和动态顺序表的区别,并重点介绍了动态顺序表的实现,包括初始化、销毁、打印、增删查改等操作。最后,文章总结了顺序表的时间复杂度和局限性,并预告了后续关于链表的内容。
49 3
|
17天前
|
算法 安全 NoSQL
2024重生之回溯数据结构与算法系列学习之顺序表习题精讲【无论是王道考研人还真爱粉都能包会的;不然别给我家鸽鸽丢脸好嘛?】
顺序表的定义和基本操作之插入;删除;按值查找;按位查找习题精讲等具体详解步骤以及举例说明
|
1月前
|
Java C++ 索引
让星星⭐月亮告诉你,LinkedList和ArrayList底层数据结构及方法源码说明
`LinkedList` 和 `ArrayList` 是 Java 中两种常见的列表实现。`LinkedList` 基于双向链表,适合频繁的插入和删除操作,但按索引访问元素效率较低。`ArrayList` 基于动态数组,支持快速随机访问,但在中间位置插入或删除元素时性能较差。两者均实现了 `List` 接口,`LinkedList` 还额外实现了 `Deque` 接口,提供了更多队列操作。
23 3
|
1月前
|
存储 缓存 索引
从底层数据结构和CPU缓存两方面剖析LinkedList的查询效率为什么比ArrayList低
本文详细对比了ArrayList和LinkedList的查询效率,从底层数据结构和CPU缓存两个方面进行分析。ArrayList基于动态数组,支持随机访问,查询时间复杂度为O(1),且CPU缓存对其友好;而LinkedList基于双向链表,需要逐个节点遍历,查询时间复杂度为O(n),且CPU缓存对其帮助不大。文章还探讨了CPU缓存对数组增删操作的影响,指出缓存主要作用于读取而非修改。通过这些分析,加深了对这两种数据结构的理解。
35 2
|
1月前
|
存储 Java
数据结构第二篇【关于java线性表(顺序表)的基本操作】
数据结构第二篇【关于java线性表(顺序表)的基本操作】
30 6
|
1月前
|
设计模式 安全 容器
数据结构第一篇【探究List和ArrayList之间的奥秘 】
数据结构第一篇【探究List和ArrayList之间的奥秘 】
23 5
|
30天前
|
存储
数据结构(顺序表)
数据结构(顺序表)
23 0

热门文章

最新文章