目录

1.线性表

2.顺序表

2.1 接口的实现

3. ArrayList简介

4. ArrayList使用

4.1 ArrayList的构造

4.2 ArrayList常见操作

4.3 ArrayList的遍历

4.4 ArrayList的扩容机制

5. ArrayList的具体使用

杨辉三角

6. ArrayList的问题及思考

---

1.线性表

线性表（linear list）是n个具有相同特性的数据元素的有限序列。 线性表是一种在实际中广泛使用的数据结构，常见的线性表：顺序表、链表、栈、队列...

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

若存在多个元素，则第一个元素无前驱，最后一个元素无后继。其他每一个元素都有且只有一个前驱和后继。

 

2.顺序表

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

顺序表：底层结构其实就是一个数组。

顺序表是使用数组来完成的一种结构。

提问：当前数组有多少个有效的数据？

答案：线性表得满足第一个无前驱，最后一个无后继，很明显3和8之间的元素不存在，所以就不是线性表，所以不能谈有效数据。

在线性表中存放数据不可以跳着放，该数据必须满足第一个无前驱，最后一个无后继，中间元素有且只有一个前驱和后继。

顺序表其实是拿 数组 实现的

2.1 接口的实现

模拟实现ArrayList，usedSize作用非常大，它与逻辑上的判断是有很大关系的

思路：

既然是模拟实现顺序表，顺序表的底层是个数组，所以我们可以创建一个MyArrayList类。

创建一个整型数组elem，

因为顺序表必须满足第一个无前驱，最后一个无后继，中间元素有且只能有一个前驱和后继，

所以顺序表必须顺着放元素，因此我们可以定义一个usedSize，来记录当前顺序表中的有效数据个数。

public class MyArrayList {
    private int[] elem;//用来存放数据元素
    private int usedSize;//代表当前顺序表中的有效数据个数

}

然后我们可以给它提供构造方法，也就是初始化数组。

public class MyArrayList {

    private int[] elem;//用来存放数据元素
    private int usedSize;//代表当前顺序表中的有效数据个数

    public MyArrayList() {
        this.elem = new int[10];
    }

}

但是直接初始化成10的话之后如果要修改就不是很方便，

所以我们可以定义一个常量，以这个常量来作为我们数组elem的初始容量大小。

public class MyArrayList {

    private int[] elem;//用来存放数据元素
    private int usedSize;//代表当前顺序表中的有效数据个数
    
    private static final int DEFAULT_SIZE = 10;

    public MyArrayList() {
        this.elem = new int[DEFAULT_SIZE];
    }

}

另外，如果用户要求指定的容量作为数组的大小，

那么我们也可以提供一个带有初始容量的构造方法。

public class MyArrayList {
    private int[] elem;//用来存放数据元素
    private int usedSize;//代表当前顺序表中的有效数据个数

    private static final int DEFAULT_SIZE = 10;

    public MyArrayList() {
        this.elem = new int[DEFAULT_SIZE];
    }

    //指定容量
    public MyArrayList(int initcapacity) {
        this.elem = new int[initcapacity];
    }
}

以下代码就是我们要实现的方法，可以复制到idea上编写

// 新增元素,默认在数组最后新增
public void add(int data) {

}

// 在 pos 位置新增元素
public void add(int pos, int data) {
 
}

// 判定是否包含某个元素
public boolean contains(int toFind) {
 return true; 
}

// 查找某个元素对应的位置
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() {
 
}

根据实现的难度，我们可以先实现display方法，这跟遍历数组没什么区别

代码如下：

    // 打印顺序表,实际上就是遍历数组
    public void display() {
        for (int i = 0; i < this.usedSize; i++) {
            System.out.print(this.elem[i] + " ");
        }
        System.out.println();
    }

 

然后我们再实现add方法，

    // 新增元素,默认在数组最后新增
    public void add(int data) {
        this.elem[this.usedSize] = data;
        this.usedSize++;

    }

一开始我是这么写的，但是有问题。

如果数组满了该怎么办？满了就放不下了，硬放就抛异常了

所以我们可以写一个方法，用来判断数组满没满。

这不是很简单？直接看当前长度是不是等于数组的长度就行

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

然后再来修改add，如果满了的话就扩容，没满就直接放元素。

    // 新增元素,默认在数组最后新增
    public void add(int data) {
        if (isFull()) {
            //满了就扩容
            this.elem = Arrays.copyOf(this.elem, 2 * this.elem.length);
        }
        this.elem[this.usedSize] = data;
        this.usedSize++;

    }

然后再来写另外一个add，这个add与刚刚那个add构成了方法的重载。

 

在pos下标新增元素，是新增元素，那就不是覆盖原来的元素。

所以得先把pos及pos之后位置的元素挪到后面，然后再在pos位置新增这个元素

所以我们得先找到pos位置，然后挪元素。

但是又不能从pos位置开始挪，

在保持数组元素顺序不变的情况下，

如果把pos位置的元素挪到pos+1上，那pos+1的元素就被pos位置的元素给覆盖掉了。

所以，我们得从后面往前挪元素。

那就可以这么写，这次我学乖了，知道这个add肯定也一样，得判断满没满

 但是还是有问题，如果pos下标是-1，那不就下标不合法出错了吗？

所以一开始得判断pos是否合法，不合法就抛一个自定义异常，

告诉他你传的坐标有问题，合法才继续往下走。

那问题又来了，pos怎么样才算合法呢？

那么毋庸置疑的，pos小于0肯定不合法。那我们可以举个例子。

假设现在有四个有效数据。

 如果pos等于5，val等于188

那有效数据是多少？很明显，这个已经不能算顺序表了 ，因为188没有前驱。

前面已经说过了，除了首尾元素，其他元素有且只有一个前驱和一个后继，188都没有前驱，那数组就断了，不是线性表，那就更不可能是顺序表了，所以pos>usedSize是不合法的。

那放pos等于4可以吗?画个图就知道了。

嗯，很明显pos=4(pos==usedSize)的话是可以的。

所以pos不合法的情况就是pos<0 和 pos>usedSize

根据上面的信息， 所以我们就可以继续写add方法了。

不合法的话可以提示一下，然后直接return走人，这里我自定义了一个异常，然后提供了构造方法

public class PosOutOfBoundsException extends RuntimeException {
    public PosOutOfBoundsException() {
        
    }

    public PosOutOfBoundsException(String message) {
        super(message);
    }
}

// 在 pos 位置新增元素
    //1.挪数据  从后往前挪
    public void add(int pos, int data) {
        //必须判断pos是否合法
        //1 2 3 4 _
        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 = this.usedSize - 1; i >= pos; i--) {
            this.elem[i + 1] = this.elem[i];//把i下标的值赋给i+1
        }
        this.elem[pos] = data;
        this.usedSize++;
    }

然后我们顺着往下写contains方法。

这个很简单，直接遍历数组找是否等于toFind，等于就直接返回true，遍历完数组还没找到的话就直接返回false即可。

    // 判定是否包含某个元素
    // 如果此时找的是引用类型，就不能使用==，
    // 而是使用equals(返回布尔类型)或者compareTo(返回整型)
    public boolean contains(int toFind) {
        for (int i = 0; i < this.usedSize; i++) {
            if (this.elem[i] == toFind) {
                return true;
            }
        }
        return false;
    }

但是如果要找的是引用类型的话，那就不能使用==来判断了，因为==判断的是两个引用的地址

判断内容是否相同的话，应该使用equals或者compareTo方法。

那我们就继续往下写indexOf方法，

这个简单，直接遍历数组，看看是否和toFind相等就行

相等的话就返回下标，遍历完数组还没找到的话就返回-1，

和上面写的contains类似，那就直接复制粘贴一波，然后再修改修改。

    // 查找某个元素对应的位置
    public int indexOf(int toFind) {
        for (int i = 0; i < this.usedSize; i++) {
            if (this.elem[i] == toFind) {
                return i;
            }
        }
        return -1;
    }

继续写get方法，又看到pos，那这次也得检查pos是否合法，还是上面这张图

 pos<0肯定不合法，如果pos等于4(usedSize)呢？

得到4下标处的值，这不是扯淡吗？4下标都没有值。

所以很明显，pos>=usedSize也是不合法的。

那就可以这么写了：

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

继续往下写set方法，同样的，也要检查pos是否合法，将pos下标的值设为value，

就跟上面代码一样，pos<0肯定不合法，当pos=usedSize的时候，该下标处的值为空，所以不合法

 那就直接复制get方法，再修改一下，检查完pos之后，将pos下标的值设置为value即可

    // 给 pos 位置的元素设为 value [更新/覆盖]
    public void set(int pos, int value) {
        if (pos < 0 || pos >= usedSize) {
            throw new PosOutOfBoundsException(pos + " 位置不合法");
        }
        this.elem[pos] = value;
    }

我们发现，set方法的检查pos代码居然和get方法的一摸一样，那我们可以写一个方法，用来检查pos的，然后把set的检查pos的代码复制，然后粘到那个你新写的方法里头。

// 检查pos位置是否合法
    private void checkPos(int pos) {
        if (pos < 0 || pos >= usedSize) {
            throw new PosOutOfBoundsException(pos + " 位置不合法");
        }
    }

如果不是扔异常的话，就得把返回值设为boolean或者int，合法就返回true或者大于0的数字，不合法就返回false或者小于0的数字。

然后修改一下之前写过的set方法和get方法：

    // 获取 pos 位置的元素
    public int get(int pos) {
        checkPos(pos);
        return this.elem[pos];
    }

    // 给 pos 位置的元素设为 value [更新/覆盖]
    public void set(int pos, int value) {
        checkPos(pos);
        this.elem[pos] = value;
    }

    // 检查pos位置是否合法
    private void checkPos(int pos) {
        if (pos < 0 || pos >= usedSize) {
            throw new PosOutOfBoundsException(pos + " 位置不合法");
        }
    }

然后继续写remove(删除)方法，

既然是删除某个数，那肯定得先找出这个数，

那就可以利用之前写过的indexOf方法快速找出这个数的下标

依旧是得判断一下，如果等于-1，那就提示一下，然后return走人，

如果不是大于0，那就开始删除，也就是将后面的数据覆盖到前面来.

 

 根据上图，写代码就很简单了，

    //删除第一次出现的关键字key
    public void remove(int toRemove) {
        int index = indexOf(toRemove);
        if (index == -1) {
            System.out.println("没有这个数据！");
            return;
        }
        for (int i = index; i < this.usedSize - 1; i++) {
            this.elem[i] = this.elem[i + 1];//覆盖
        }
        //this.elem[this.usedSize - 1] = null;//引用类型
        this.usedSize--;
    }

然后我们再继续写size方法

这个很简单，直接返回usedSize就行。

    // 获取顺序表长度
    public int size() {
        return this.usedSize;
    }

继续写clear方法，这个直接把usedSize置为0，下次放数据就直接从0下标开始放。

如果是引用类型的话，就得走一步置一个null，

不然的话一直存着对象不放，就有可能造成内存泄漏

    // 清空顺序表
    public void clear() {
        //如果是引用类型，那么必须走一步就置空一个，不然会造成内存泄漏
        /*for (int i = 0; i < this.usedSize; i++) {
            this.elem[i] = null;
        }*/
        this.usedSize = 0;
    }

完整代码：

public class MyArrayList {
    private int[] elem;//用来存放数据元素
    private int usedSize;//代表当前顺序表中的有效数据个数

    private static final int DEFAULT_SIZE = 10;

    public MyArrayList() {
        this.elem = new int[DEFAULT_SIZE];
    }

    //指定容量
    public MyArrayList(int initcapacity) {
        this.elem = new int[initcapacity];
    }

    // 打印顺序表,实际上就是遍历数组
    public void display() {
        for (int i = 0; i < this.usedSize; i++) {
            System.out.print(this.elem[i] + " ");
        }
        System.out.println();
    }

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

    // 新增元素,默认在数组最后新增
    public void add(int data) {
        if (isFull()) {
            //满了就扩容
            this.elem = Arrays.copyOf(this.elem, 2 * this.elem.length);
        }
        this.elem[this.usedSize] = data;
        this.usedSize++;

    }

    // 在 pos 位置新增元素
    //1.挪数据  从后往前挪
    public void add(int pos, int data) {
        //必须判断pos是否合法
        //1 2 3 4 _
        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 = this.usedSize - 1; i >= pos; i--) {
            this.elem[i + 1] = this.elem[i];//把i下标的值赋给i+1
        }
        this.elem[pos] = data;
        this.usedSize++;
    }

    // 判定是否包含某个元素
    // 如果此时找的是引用类型，就不能使用==，
    // 而是使用equals(返回布尔类型)或者compareTo(返回整型)
    public boolean contains(int toFind) {
        for (int i = 0; i < this.usedSize; i++) {
            if (this.elem[i] == toFind) {
                return true;
            }
        }
        return false;
    }

    // 查找某个元素对应的位置
    public int indexOf(int toFind) {
        for (int i = 0; i < this.usedSize; i++) {
            if (this.elem[i] == toFind) {
                return i;
            }
        }
        return -1;
    }

    // 获取 pos 位置的元素
    public int get(int pos) {
        checkPos(pos);
        return this.elem[pos];
    }

    // 给 pos 位置的元素设为 value [更新/覆盖]
    public void set(int pos, int value) {
        checkPos(pos);
        this.elem[pos] = value;
    }

    // 检查pos位置是否合法
    private void checkPos(int pos) {
        if (pos < 0 || pos >= usedSize) {
            throw new PosOutOfBoundsException(pos + " 位置不合法");
        }
    }

    //删除第一次出现的关键字key
    public void remove(int toRemove) {
        int index = indexOf(toRemove);
        if (index == -1) {
            System.out.println("没有这个数据！");
            return;
        }
        for (int i = index; i < this.usedSize - 1; i++) {
            this.elem[i] = this.elem[i + 1];
        }
        //this.elem[this.usedSize - 1] = null;//引用类型
        this.usedSize--;
    }

    // 获取顺序表长度
    public int size() {
        return this.usedSize;
    }

    // 清空顺序表
    public void clear() {
        //如果是引用类型，那么必须走一步就置空一个，不然会造成内存泄漏
        /*for (int i = 0; i < this.usedSize; i++) {
            this.elem[i] = null;
        }*/
        this.usedSize = 0;
    }

}

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

 

4. ArrayList使用

4.1 ArrayList的构造

演示： 

给指定容量

使用演示： 

list2会把list1的数据拷贝放到list2里面来起来

三个构造方法：

 

4.2 ArrayList常见操作

ArrayList虽然提供的方法比较多，但是常用方法如下所示，需要用到其他方法时，自行查看ArrayList的帮助文档。

 方法演示：

 

将0下标的值更新为99 

 

注意： 

说明：list3只是将list2的1下标的地址给存了起来，所以改变list3会影响list2

一般情况下，能够通过sout直接输出引用对象的内容的话，就一定重写了toString方法

 

4.3 ArrayList的遍历

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

使用size()，可以获取当前顺序表的元素个数

 

迭代器的使用和Scanner的使用有点像，使用前也要导包

上面两种写法没什么区别，只是名字不同，只是ListIterator是专门用来遍历线性表的，而另一个是通用的罢了

注意：

1. ArrayList最长使用的遍历方式是：for循环+下标 以及 foreach

2. 迭代器是设计模式的一种

 

4.4 ArrayList的扩容机制

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

结论：

当我们调用不带参数的构造方法的时候，默认在第一次add的时候才会分配大小为10的内存。

扩容是按照1.5倍的方式进行扩容的。

【总结】

1. 检测是否真正需要扩容，如果是调用grow准备扩容

2. 预估需要库容的大小

• 初步预估按照1.5倍大小扩容
• 如果用户所需大小超过预估1.5倍大小，则按照用户所需大小扩容
• 真正扩容之前检测是否能扩容成功，防止太大导致扩容失败

3. 使用copyOf进行扩容

5. ArrayList的具体使用

杨辉三角

杨辉三角: 

class Solution {
    public List<List<Integer>> generate(int numRows) {
        List<List<Integer>> ans = new ArrayList<>();
        List<Integer> ret = new ArrayList<>();
        ret.add(1);
        ans.add(ret);
        //上面代码完成第一行
        for (int i = 1; i < numRows; i++) {
            List<Integer> curRow = new ArrayList<>();
            curRow.add(1);//每一行的第一个

            //处理每一行的中间
            //1
            //1 1
            //1 2 1
            //1 3 3 1
            //1 4 6 4 1
            //前一行
            List<Integer> prevRow = ans.get(i - 1);
            for (int j = 1; j < i; j++) {
                int x = prevRow.get(j - 1) + prevRow.get(j);
                curRow.add(x);
            }

            curRow.add(1);//每一行的最后一个
            ans.add(curRow);
        }
        return ans;
    }
}

6. ArrayList的问题及思考

1. ArrayList底层使用连续的空间，任意位置插入或删除元素时，需要将该位置后序元素整体往前或者往后搬移，故时间复杂度为O(N)

2. 增容需要申请新空间，拷贝数据，释放旧空间。会有不小的消耗。

3. 增容一般是呈2倍的增长，势必会有一定的空间浪费。例如当前容量为100，满了以后增容到200，我们再继续插入了5个数据，后面没有数据插入了，那么就浪费了95个数据空间。

顺序表适合 静态的数据 进行查找和更新

不适合用来插入和删除数据