数据结构系列三：List+顺序表+ArrayList

一、List

（1）什么是List

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

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

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

（2）常见接口介绍

List中提供了好的方法，具体如下

（3）List的使用

注意：List是个接口，并不能直接用来实例化
如果要使用，必须去实例化List的实现类，在集合框架中，ArrayList和LinkedList都实现了List接口

public class demo1 {
    public static void main(String[] args) {
        ArrayList<String> arrayList = new ArrayList<>();
        List<String> list = new ArrayList<>();//推荐写法
    }
}

那么，如何使用呢？请大家跟着我的思路往下理解

二、顺序表与ArrayList

（1）线性表

若元素存在多个，则第一个元素无前驱，最后一个元素无后继，其他每一个元素都有一个前驱和一个后继，这就叫线性表

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

（2）顺序表

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

（3）顺序表常用方法的模拟实现

1.一些定义

import java.util.Arrays;

class MyArray{
    public int usedSize;
    public int[] elem;
    public static final int DEFAULT_SIZE = 2;
    public MyArray(){
        this.elem = new int[DEFAULT_SIZE];
    }
    public MyArray(int initCapacity){
        this.elem = new int[initCapacity];
    }

2.add(int data)新增元素，默认在数组最后新增

思路：首先判断当前数组存没存放满，如果存放满了，则需要扩容，没存放慢，即可直接存入

        public boolean isFull(){
        if(this.usedSize == this.elem.length){
            return true;
        }
        return false;
    }

    public void add(int data){
        if(isFull()){
            this.elem = Arrays.copyOf(this.elem,2*this.elem.length);
        }
        this.elem[this.usedSize] = data;
        usedSize++;
    }

3.add(int pos,int data)在pos位置插入元素

思路：首先判断当前pos位置的合法性，再判断数组存没存满，最后在pos位置存入数组

 public void add(int pos,int data){
        if(pos < 0 || pos > this.usedSize){
            throw new  PosOutOfBoundsException(pos + "位置不合法");
        }
        if(isFull()){
            this.elem = Arrays.copyOf(this.elem,2*this.elem.length);
        }
        for (int i = usedSize - 1; i >= pos ; i--) {
            this.elem[i+1] = this.elem[i];
        }
        this.elem[pos] = data;
        this.usedSize++;
    }

4.contains判断是否包含某个元素

public boolean contains(int data){
        for (int i = 0; i < this.usedSize; i++) {
            if(this.elem[i] == data){
                return true;
            }
        }
        return false;
    }

5.indexOf查找某个元素对应的位置

public int indexOf(int data){
        for (int i = 0; i < this.usedSize; i++) {
            if(this.elem[i] == data){
                return i;
            }
        }
        return -1;
    }

6.get获取pos位置的元素

思路：首先判断合法性，然后在返回对应的值

public int get(int pos){
        if(pos < 0 || pos >= this.usedSize){
            throw new PosOutOfBoundsException(pos + "位置不合法！");
        }
        return this.elem[pos];
    }

7.set给pos位置的元素设置为value

public void set(int pos,int value) {
        if (pos < 0 || pos >= this.usedSize) {
            throw new PosOutOfBoundsException(pos + "位置不合法！");
        }
        this.elem[pos] = value;
    }

8.删除第一次出现的关键字key

思路：先检查是否存在要删除的元素，然后在定位被删除元素位置，把后面的值依次覆盖

public void remove(int data){
        int index = indexOf(data);
        if(index == -1){
            System.out.println("没有这个数据");
            return;
        }
        for (int i = index; i < this.usedSize; i++) {
            this.elem[i] = this.elem[i+1];
        }
        this.usedSize--;
    }

9.获取顺序表长度

直接返回usedSize即可

public int size(){
        return usedSize;
    }

10.清空顺序表

public void clear(){
        this.usedSize = 0;
        //如果是引用类型
        /*for (int i = 0; i < this.usedSize; i++) {
            this.elem[i] = null;
        }
        this.elem[usedSize-1] = null;*/
    }

（4）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底层是一段连续的空间，并且可以动态扩容，是一个动态类型的顺序表

（5）ArrayList的构造

方法：

1. ArrayList()：无参构造
2. ArrayList(Collection<? extends E> c)：利用其他Collection构建ArrayList
3. ArrayList(int initialCapacity)：制定顺序表初始容量

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

public class demo1 {
    public static void main(String[] args) {
        //构造一个空的列表
        List<Integer> list = new ArrayList<>();
        
        //构造一个具有十个容量的列表
        List<Integer> list1 = new ArrayList<>(10);
        list1.add(1);
        list1.add(2);
        list1.add(3);
        //list.add("hello")//编译失败因为list1已经限定只能存储整型元素
        
        //list2构造好之后，于list1中元素一致
        ArrayList<Integer> list2 = new ArrayList<>(list1);
        
        //避免省略类型，否则任意类型的元素都可以放，使用时是一场灾难
        List list3 = new ArrayList();
        list3.add("1111");
        list3.add(123);
    }
}

ArrayList提供的方法比较多，大家使用的时候可以查看ArrayList的帮助文档
一般情况下，能够直接通过sout输出引用指向对象当中的内容的时候，此时一定重写了toString方法

（6）ArrayList的遍历

ArrayList可以使用三种方式遍历

import java.util.List;

public class demo3 {
    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.iterator();
        while (it.hasNext()){
            System.out.print(it.next() + " ");
        }
    }
}
//运行结果
1 2 3 4 5 
1 2 3 4 5 
1 2 3 4 5 
Process finished with exit code 0

注意：

1. ArrayList最常使用的遍历方式是for+下标以及foreach
2. 迭代器是设计模式的一种，后续容器接触多了在给大家介绍

（7）ArrayList的扩容机制

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

1. 首先检测是否真正需要扩容，如果是，调用grow准备扩容
2. 预估扩容的大小，初步预估按照1.5倍大小扩容，如果用户所需大小超过1.5倍大小，则按照用户所需大小扩容，真正扩容之前检测能否扩容成功，防止太大导致扩容失败
3. 使用copyOf进行扩容

（8）ArrayList的问题及思考

• 优点：可以通过下标进行随机访问
• 缺点：

1. 添加元素效率比较低
2. 往O下标插入元素，须移动后面所有的元素，那么时间复杂度就变高了
3. 删除的效率低，假设删除0下标的元素，也要移动后面的元素
4. 扩容的时候，假设长度为100，扩容新增一个元素第101个，要1.5倍扩容，扩容50个只放进去一个，存在浪费空间的情况

顺序表适合静态的数据进行查找和更新，不适合用来插入和删除数据，那么我们就要依赖链表来做