ArrayList与顺序表

1.线性表(linear list) 是n个具有相同特性的数据元素的有序数列.线性表是一种在实际中广泛使用的数据结构,常见的线性表:顺序表,链表,栈,队列...

线性表在逻辑上是线性结构的,也就是说是一条连续的直线.但是在物理结构上并不一定是连续的,线性表在物理上存储时,通常以数组和链式结构的形式储存

2.顺序表

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

2.1接口的实现

public class SeqList {
    private int[] array;
    private int size;
    //默认构造方法
    public SeqList(){
    }
    //把顺序表的底层容量设为initcapacity
    SeqList(int initcapacity){
    }
    //新增加元素,默认在数组最后新增元素
    public void add(int data){
    }
    //在指定位置(pos) 位置新增元素
    public void add(int pos,int data){
    }
    //判断是否包含某个元素,如果包含这个元素就返回true,否则就返回false
    public boolean contains(int toFind){
        return true;
    }
    //查找某个元素对应的位置,如果找到对应元素,就返回其元素的下标,如果没有找到元素,就返回-1;
    public int indexOf(int toFind){
        return -1;
    }
    //获取pos的位置的元素
    public int get(int pos){
        return -1;
    }
    //给pos的位置的元素设为 value
    public void set(int pos,int value){
    }
    //删除第一次出现的关键字key
    public void remove(int toRemove){
    }
    //获取顺序表的长度
    public int size(){
        return 0;
    }
    //清空顺序表
    public void clear(){
    }
    //打印顺序表
    public void display(){}
}

ArrayList简介

在集合框架中,ArrayList是一个普通的类,实现了List接口

说明:

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

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

ArraList实现了Cloneable接口,表明ArrayList是可以clone的

ArrayList实现了Serialiable接口,表明ArrayList是支持序列化的

ArrayList底层是一段连续的空间,并且可以动态扩容,是一个动态类型的顺序表

4.ArrayList的使用

4.1ArrayList的构造

import java.util.ArrayList;
import java.util.List;

public class Main {
    public static void main(String[] args) {
        //ArrayList 创建,推荐写法
        //构造一个空的列表
        List<Integer> list1 = new ArrayList<>();
        //构造一个具有10个容量的列表
        List<Integer> list2 = new ArrayList<>(10);
        list2.add(1);
        list2.add(2);
        list2.add(3);
        //类型不匹配发生报错
//        list2.add("hello");
        //如果我们要输入类似 list2.add("hello")这样的类型的内容,是不允许的.
        //我们在前面已经限定了泛型的类型是 Integer,类型不匹配就会报错.
        //我们可以通过创建 String 类型的 ArrayList 来存储 String 类型的数据
        List<String> list3 = new ArrayList<>();
        list3.add("hello");
        list3.add("world");
        //打印输出的内容是以数组的形式打印出来的
        System.out.println(list2);
        //我们在创建泛型的时候应该去避免出现,不指定存放元素类型这样的写法.
        //这样会导致顺序表中存放的内容的数据类型不明确,容易出现错误
    }
}

4.2ArrayList常见的操作方法

import java.util.ArrayList;
import java.util.InputMismatchException;
import java.util.List;
import java.util.Scanner;

public class Main2 {
    public static void main(String[] args) {
        //创建了一个存放 String 类型的 ArrayList
        List<String> list = new ArrayList<String>();
        //我们向 ArrayList 中添加元素
        list.add("JavaSE");
        list.add("JavaWeb");
        list.add("JavaEE");
        list.add("JVM");
        list.add("测试");
        //先打印一下 ArrayList 查看一下里面的元素
        System.out.println(list);
        //我们下面使用不同的方法
        //获取 list 中的有效元素的个数
        System.out.println(list.size());
        //获取和设置 index 位置上的元素,注意的是 index 必须要介于[0,size)之间
        //简单的获取的 index 位置上的元素
        System.out.println(list.get(1));
        //我们可以加上一些判断,来确保发生数组越界的情况发生
        //通过try{} 来抛出异常
//        Scanner scanner = new Scanner(System.in);
//        System.out.println("请输入要获取的 index 位置:");
//        int index = scanner.nextInt();
//        try{
//            if(index < 0 || index > list.size() - 1){
//                //通过 throw 来抛出异常
//                throw new InputMismatchException();
//            }
//            System.out.println(list.get(index));
//        }//通过 catch{}来捕获异常并处理异常
//        catch (InputMismatchException e){
//            System.out.println("输入的 index 位置,发生数组越界的情况发生");
//        }
        //我们通过 set() 方法来修改 index 位置上的元素
        list.set(1,"Java数据结构");
        //修改完毕后我们再次进行一次打印
        System.out.println(list);
        //删除自定元素,如果我们找到就删除,把该元素之后的元素同一向前搬移一个单位
        list.remove("JVM");
        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("测试");
        }
        //查找指定元素第一次出现的位置:indexOf() 从前向后找,lastIndexOf() 从后向前找
        list.add("JavaSE");
        System.out.println(list.indexOf("JavaSE"));
        System.out.println(list.lastIndexOf("JavaSE"));
        //使用 list 中[0,4)之间的元素构成一个新的SubList返回,但是和ArrayList共用一个elementData数组
//        List<String> ret = new list.subList(0,4);
        //清空数组
        list.clear();
        System.out.println(list);
        System.out.println(list.size());
    }
}

4.3ArrayList的遍历

ArrayList可以使用三种方式进行遍历: for循环 + 下标,foreach,使用,迭代器

import java.util.ArrayList;
import java.util.Iterator;
import java.util.List;

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

注意的是:

ArrayList最常用的遍历的方式是:for循环+下标 以及foreach

2.迭代器是设计模式的一种方式,在后面才会使用

4.4ArrayList的扩容机制

ArrayList是一个动态类型的顺序表,即:在插入元素的过程中会自动扩容