当前位置：首页 > news >正文

【数据结构与算法】ArrayList与顺序表(上)

news 来源：原创 2024/5/20 2:41:39

🍗🍗hello，进来的小伙伴们，你们好呐！

🍔🍔系列专栏：【数据结构与算法】

🍼🍼作者简介：一名大三在读的科班Java小白，星夜漫长，你我同行！

🌯🌯本篇内容：初始ArrayList与顺序表，简单了解ArrayList的基本用法，入门顺序表！

🍤🍤给大家推荐一个超级好用的刷题网站——牛客网！

点击链接注册，开启刷题之路！

一、线性表

🍊线性表（linear list）是n个具有相同特性的数据元素的有限序列。线性表是一种在实际中广泛使用的数据结构，常见的线性表：顺序表、链表、栈、队列...
🍅线性表在逻辑上是线性结构，也就说是连续的一条直线。但是在物理结构上并不一定是连续的，线性表在物理上存储时，通常以数组和链式结构的形式存储。

二、ArrayList简介

1.集合框架图

🍜🍜我们可以发现，List是个接口，并不能直接用来实例化。
如果要使用，必须去实例化List的实现类。在集合框架中，ArrayList和LinkedList都实现了List接口，本篇我们主要介绍的是ArrayList。

🍚🍚结论：

1. ArrayList实现了RandomAccess接口，表明ArrayList支持随机访问。
2. ArrayList实现了Cloneable接口，表明ArrayList是可以clone的。
3. ArrayList实现了Serializable接口，表明ArrayList是支持序列化的。
4. 和Vector不同，ArrayList不是线程安全的，在单线程下可以使用，在多线程中可以选择Vector或者CopyOnWriteArrayList。
5. ArrayList底层是一段连续的空间，并且可以动态扩容，是一个动态类型的顺序表。

三、ArrayList使用

1、ArrayList三种方式构造

public class demo3 {
    public static void main(String[] args) {
        // 构造一个空的列表
        //当我们调用不带参数的构造方法的时候，只有第一次add的时候 才会分配大小为10的内存
        ArrayList<String> s1 = new ArrayList<>();
        s1.add("hello");
        s1.add("java");
        System.out.println(s1);


        //构造一个具有3个容量的顺序表
        ArrayList<Integer> n1 = new ArrayList<>(3);
        n1.add(666);
        n1.add(888);
        n1.add(999);
        System.out.println(n1);


        //ArrayList(Collection<? extends E> c) 大类实现Collection接口便可以传
        ArrayList<Integer> n2 = new ArrayList<>(n1);//把n1里面的元素放到n2里面
        System.out.println(n2);
    }
}

运行结果：

2、ArrayList的常见操作

ArrayList的操作方法还是蛮多的，这里我提供几个比较常用的使用方法，如果大家还想了解更多的操作方法可以在参考文档查找！

在线文档：

常用方法：

在线演示：

public class demo5 {
    public static void main(String[] args) {
        List<String> list = new ArrayList<>();
        list.add("hello java");
        list.add("BATJ");
        list.add("大厂!!!");
        System.out.println(list);
        
        // 获取list中有效元素个数
        System.out.println(list.size());
        
        // 获取和设置index位置上的元素，注意index必须介于[0, size)间
        System.out.println(list.get(1));
        list.set(1, "好好学习！！！");
        System.out.println(list.get(1));
        
        // 在list的index位置插入指定元素，index及后续的元素统一往后搬移一个位置
        list.add(1, "学好数据结构！");
        System.out.println(list);
        
        // 删除指定元素，找到了就删除，该元素之后的元素统一往前搬移一个位置
        list.remove("BATJ");
        System.out.println(list);
        
        
        // 删除list中index位置上的元素，注意index不要超过list中有效元素个数,否则会抛出下标越界异常
        list.remove(list.size()-1);
        System.out.println(list);
        
        // 检测list中是否包含指定元素，包含返回true，否则返回false
        if(list.contains("学好数据结构！")){
        list.add("学好算法！");
        }
        
        // 使用list中[0, 4)之间的元素构成一个新的ArrayList返回
        List<String> ret = list.subList(0, 4);
        System.out.println(ret);
        
    }
}

运行结果：

加上clear()方法后，我们在看运行结果：

运行结果：

3、 ArrayList的遍历

ArrayList 可以使用三方方式遍历：for循环+下标、foreach、使用迭代器。

public class Bianli {
    public static void main(String[] args) {
        ArrayList<Integer> c1 = new ArrayList<>();
        c1.add(1);
        c1.add(2);
        c1.add(3);
        c1.add(4);
        c1.add(5);
        for (int i = 0; i < c1.size(); i++) {//使用下标for遍历
            System.out.print(c1.get(i)+" ");
        }
        System.out.println();


        for (Integer s1:c1) {//使用foreach遍历
            System.out.print(s1+" ");
        }
        System.out.println();


        Iterator<Integer> it = c1.iterator();//使用迭代器遍历
        while (it.hasNext()){
            System.out.print(it.next()+" ");
        }
        System.out.println();
    }
}

运行结果：